Hilfe bei definieren eines Endlichen Automaten

[Rah2k]

Hallo,

ich habe etwas Probleme ein Zustandsdiagramm/Zustandstabelle aus einer gegebenen Sprache zu erstellen. Beispiel aus unserem Skript:

Aufgabe:

START = ( „0“, A ) | ( „1“, B ) ;

A = ( „1“, B ) | epsilon ;

B = ( „0“, A ) | epsilon ;

Definieren Sie den endlichen Automaten zur Erkennung dieser Sprache. Erstellen Sie das entsprechende Zustandsdiagramm.

 

Lösung:

Im Anhang

 

Wie muss ich das "," die "()" und "|" deuten beim erstellen des Diagramms? Und warum kann ich von S1/S2 nur mit 0 bzw. 1 zum Zustand S3?

Evtl. kann mir jemand die Lösung zu der Aufgabe verständlich erklären?  

 

Danke vorab!

[Decius]

START = ( „0“, A ) | ( „1“, B ) ;
A = ( „1“, B ) | epsilon ;
B = ( „0“, A ) | epsilon ;

Du musst das so lesen:

Du fängst bei START an.  In diesem Zustand kannst du eine 0 oder eine 1 lesen. Wenn du eine 0 liest, wechselst du in den Zustand A, liest du eine 1, wechselst du in den Zustand B. Wenn du jetzt in A oder B bist, musst du entsprechend die Zeile von A oder B lesen usw....

Die Lösung ist der Automat, der diese Sprache exakt abbildet. Sprich alle Übergänge in dem Automaten sind geprägt durch die drei definierten Sprachregeln. Es kann hier keine Übergänge geben, welche die Sprache verletzten würden. Beispiel: Es kann keinen Übergang geben, der wieder zurück zum START, im Automat als s0, führt. Gibt es auch nicht.

[Rah2k]

Danke dir! 

Mein Interpretationsfehler lag darin, dass man bei START 0 oder A lesen kann.

D.h. nach dem Komma wird einfach nur der erreichte Zustand beschrieben. Manchmal sieht man den Wald vor lauter Bäumen nicht

[SaJu]

Das Epsilon ist übrigens die leere Menge. Das heißt, wenn da die leere Menge möglich ist (= keine Eingabe), bleibst Du dann in diesem Knoten. Der Endknoten mit einem zusätzlichen Kreis markiert, so dass man erkennen kann, was der Endknoten ist.

Bearbeitet 15. Dezember 2018 von SaJu