Automaten angeben

vip*r

Hi Leute!

Ich soll einen deterministischen endlichen Automaten für die Sprache L={0101} über Σ_Bool angeben.

Ich hab mir nun gedacht, ich geb erst einen nichtdeterministischen endlichen Automaten an und wandle den dann mit der Potenzmengenkonstruktion in einen NEA um. Ich hab euch hier mal ein Bild meines DEAs gemacht. http://www.fotos-hochladen.net/view/1wdqaeomlxj.jpg Denkt ihr, stimmt der so?

knivil

Es sollte trivial sein einen endlichen Automaten fuer eine endliche Menge an Woertern anzugeben. In deinem Fall enthaelt die Menge anscheinend nur ein Wort "0101". Ein Umweg ueber NEA ist Bullshit. Du hast nicht ueber das Problem nachgedacht. Und: dein Automat ist falsch. Auch ist der angegebene Automat kein DEA wie im Bild gezeigt.

vip*r

Hm, du hast wohl Recht. Den Umweg über einen NEA ist wirklich schlecht. Hier mein neuer Versuch, der übrigens der erste Versuch war, mir aber etwas zu trivial erschien.

Was ich mir dabei aber auch nicht richtig vorstellen kann, ist, wenn als erstes Zeichen eine 1 kommt. Der Automat verlangt aber dann eigentlich eine 0. Was macht der Auomat dann? Wartet der auf das nächste Zeichen, oder kackt er ab?

http://s14.directupload.net/file/d/2868/2b3zdcke_jpg.htm

EDIT: Halt! Die Eigenschleife bei q4 ist überflüssig. Die muss weg. Der Automat soll ja nur 0101 erkennen. Der letzte Zustand muss akzept. sein. Das fehlt auch noch.

EDIT2: Hier dann der richtige Graph: http://s1.directupload.net/file/d/2868/gtyivca4_jpg.htm

knivil

vip@r schrieb:

EDIT2: Hier dann der richtige Graph: http://s1.directupload.net/file/d/2868/gtyivca4_jpg.htm

Ja, aber ueberpruefe nochmals die Aufgabenstellung ob die Sprache wirklich nur aus einem Wort bestehen soll.

vip*r

Hier der gesamte Aufgabentext:

Zeichnen Sie einen Transitionsgraph für einen deterministischen endlichen deterministischen Automaten, welcher die folgende Sprache über Σ_Bool erkennt: L = {0101}

Und dann noch eine Teilaufgabe: Geben sie für den Automaten auch eine formale Beschreibung an.

Da weiß ich aber nicht was damit gemeint ist...

EDIT: Ich hab nachgelesen und bin für formale Beschreibung auf das hier gekommen:

M = {Q,Σ,δ,q₀,F} = {{q₀,q₁,q₂,q₃,q₄},{0,1},δ,q₀,{q₄}}

Das Wichtigste, die Zustandsübergangsfunktion, hast du aber nicht angegeben. Abgesehen davon ist ein Automat formal ein Tupel, keine Menge.

Und:

Was macht der Auomat dann? Wartet der auf das nächste Zeichen, oder kackt er ab?

Das ist im Allgemeinen schlicht nicht definiert (deswegen finden theoretische Informatiker partielle Funktionen auch so toll). Wird oft dargestellt als $\perp$ (sprich: undefiniert, Bottom).

vip*r

Das hier die Zustandsübergangsfunktion δ nicht definiert ist, ist mir heute auch aufgefallen. Was muss man dazu alles machen? Könnte da von euch vielleicht noch jemand ein paar Worte drüber verlieren?

Ich hab's dann mal so versucht: δ={((q0,0),q1),((q0,1),DS),((q1,1),q2),((q1,0),DS),((q2,0),q3),((q2,1),DS),((q3,1),q4),((q3,0),DS),((q4,0),DS),((q4,1),DS)}

Stimmt das so?

Zitat: "Abgesehen davon ist ein Automat formal ein Tupel, keine Menge."

Was ist da dann nun falsch? Soll ich die geschweiften Klammern, sprich Mengenklammern, zu runde Klammern verändern?

Was muss man dazu alles machen?

Bei deinem Versuch hast du nun aber eben alle Übergänge definiert. Das, was bei dir nach DS geht (ein Zustand (?), der nicht in der Zustandsmenge ist und deswegen deiner obigen Definition widerspricht), ist einfach undefiniert. Das bedeutet ja gerade, es nicht zu definieren, was du aber trotzdem tust. Sieht aber ansonsten ok aus.

Was ist da dann nun falsch? Soll ich die geschweiften Klammern, sprich Mengenklammern, zu runde Klammern verändern?

Ja. Hat zum Beispiel den Sinn, dass bei deiner Definition keine Zuordnung der Komponenten geschehen kann, weil die Reihenfolge vertauschbar ist, d.h. es könnte auch ∑ = {q0,q1,q2,q3,q4} sein.