Question

Betrachten Sie den DFA M = (Σ,Z,δ,z0,F) mit Σ = {0,1},Z = {z0,z1,z2,z3,z4}, F = {z4} und δ wie folgt:

δ  z0   z1  z2   z3   z4

0  z1  z3   z1   z4   z4

1  z2  z3   z2    z4  z3

Zeichnen Sie den Zustandsgraphen von M.

Wenden Sie die erweiterte Überführungsfunktion schrittweise auf das Wort w1 = 1101101 an. Begründen Sie mit Hilfe Ihres Ergebnisses, ob M das Wort w1 akzeptiert oder nicht.

Ist die Überführungsfunktion δ total? Begründen Sie.

Konstruieren Sie eine Grammtik G vom Typ 3, sodass L(G) = L(M) gilt.

Geben Sie einen Syntaxbaum für die Ableitung des Wortes w2 = 00000 in ihrer kon- struierten Grammatik G an.

Answer 1

Genieße diese Antwort mit Vorsicht. Ich weiß  nicht, ob ich die Überführungsfunktion richtig verstanden habe, da wir nicht mit Zahlen arbeiten und nicht in einer Tabelle.

Wenn ich es richtig verstanden habe,  ist dies der Zustandsgraph. Das Wort wird nicht akzeptiert. Da der z4 unser Endzustand ist aber durch die 1, kommen wir zu z3 ( hier q3 ). Entschuldige, falls es komplett falsch ist.

Aber mein Tipp: Wenn es geht, zeichne den DFA einfach und gehe durch die Zustände, welche das Wort durchläuft. Die Erklärung könnte folgendes aussehen: δ(z0, 1) = Z2 usw.


Btw. normalerweise gehört vor der z0 ein Pfeil als Indikator, dass dies der Startpunkt ist. Beim genutzten Programm war dies nicht möglich, daher bitte nicht vergessen, wie auch der Endzustand, den ich über den Pfeil schrieb, da es keine andere Weise gab.

Comments

Ich weiß  nicht, ob ich die Überführungsfunktion richtig verstanden habe, da wir nicht mit Zahlen arbeiten und nicht in einer Tabelle.

Die Überführungsfunktion hast Du richtig verstanden ;-) So bringen wir das unseren Studenten auch bei :-) Gute Antwort!

---

Da der z4 unser Endzustand ist aber durch die 1, kommen wir zu z3 ( hier q3 ). Entschuldige, falls es komplett falsch ist.

Jetzt weiß ich, wo vermutlich Dein Denkfehler ist. Der Endzustand (passender finde ich den Ausdruck "akzeptierender Zustand") kann auch verlassen werden. Er sagt nur aus, dass man hier terminieren kann, aber nicht muss.

---

Danke für die Korrektur/Ergänzung. Genau den letzten Satz wollte ich damit aussagen :) Da ist Endzustand bissle blöd.