Autor |
Beitrag |
Christoph
| Veröffentlicht am Sonntag, den 29. April, 2001 - 21:21: |
|
Kann mir jemand einen tip geben ,wie ich folgendes Problem angehen kann ? Beweisen Sie, daß für alle ganzen Zahlen b,q,r Element aus No (Nat. Zahlen + 0) mit b >= 2, r > 0 und 0 =< q =< r-1 gilt. Die Sprache: A := {w | [w]b mod r = q} über dem Alphabet Sigma={0,1...b-1} ist reglär. Dabei bezeichnet [w]b Element aus N die durch das Wort w = wn, ..., w2, w1 zur Basis b dargestellte Zahl, d.h. [w]b = Summe(i=1 bis n) wi*b^(i-1) Also auf gut Deutsch: w ist ein Wort, daß von einem DEA erkannt werden kann, oder nicht. Die Zeichen des Wortes müssen natürlich aus dem Alphabet sein. D.h. 0 <= wi < b Der Betrag der Zahl w kann beliebig groß sein, da die maximale Länge des Wortes nicht festgelegt ist. Und weiters: w ist eine Aneinanderreihung von Zeichen aus dem Alphabet z.B. für b=2 0001001010 (einfache dualzahl) für b=16 kriegt man die Hex-Darstellung, nur, daß keine Buchstaben,sondern die Zahlen 10-15 als Ziffern verwendet werden. b,q und r können beliebig aus den natürlichen Zahlen gewählt werden. Ist b festgelegt, so ist hiermit auch das Alphabet bestimmt, aus dessen Zeichen sich die Wörter zusammensetzen. DIE FRAGE ist nur: Wie kann ich so einen DEA konstruieren um zu beweisen das A regulär ist, bzw. gibt es eine andere Möglichkeit dies nachzuweisen. Danke, Christoph. |
Michael
| Veröffentlicht am Mittwoch, den 02. Mai, 2001 - 00:45: |
|
Ich möchte diese Lösung im Namen von SpockGeiger posten und Ihm herzlich für Seine Unterstützung danken! Es ist wirklich gut erklärt und vielleicht können wir uns ja wieder mal mit einer Frage an Dich wenden. Lösung: Die Idee ist folgende: Man nehme für jeden möglichen Rest einen Zustand, also Zustände 0 bis r-1. Jetzt müssen wir uns überlegen, wie sich die Zahl jeweils verändert, während man sie von vorne nach hinten liest. Hat man einen Teil gelesen, und ist der Wert dieses Teils x, und ist das nächste eingelesene Zeichen c, so ist die neue Zahl gleich bx+c. Jetzt machen wir es so, dass der Automat immer in dem Zustand ist, welchen Rest die bis dahin eingelesene Zahl hat. Also beginnen wir um Zustand 0. Sind wir in einem Zustand q, so ist der Folgezustand bei Zeichen c gleich (qb+c)mod r, da man ja zum Glück mit Resten rechnen kann. Als den akzeptierenden Zustand brauchen wir nur noch den Zustand zu markieren, der den richtigen Rest darstellt. Dankend an SpockGeiger. |
|