Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Beweis einer Regulären Sprache

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Mathematik für Informatiker » Beweis einer Regulären Sprache « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Christoph
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 29. April, 2001 - 21:21:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Michael
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 02. Mai, 2001 - 00:45:   Beitrag drucken

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.

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page