Aufgabe 49
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
TM in äquivalente Grammatik übersetzen
Beim Überführen einer TM M in eine Grammatik möchte man ja die Berechnung von M rückwärts vollziehen.
Sagen wir, es gibt nur einen Endzustand [m]q_acc[/m] von M, den man über den Delta-Übergang [m]delta(q_0, U) = (q_acc, V, R)[/m] erreicht.
Dann würde man nach dem Schema [m]a’ q’ → q a[/m] dies in die Produktionsregel [m]V q_acc → q_0 U[/m] überführen.
Für den Start gibt es diese beiden Regeln.
[m]Startsymbol S → |> q_acc
q_acc → |> q_acc B[/m]
Dann käme man von S zu q_acc und kann endlos viele B’s erzeugen, aber wie geht es weiter? Es fehlt ja das V, um die Produktionsregel anwenden zu können 
Schau dir mal die letzten paar Schritte der TM an. Für w = 0011 hört die TM mit XXYYYq_5 auf. Also musst du das Verfahren aus der VL ein wenig umändern, sodass nicht Blanks erzeugt werden, sondern X und Y.
Dann kannst du mit einer Regel für Yq_5 weitermachen, die beim “Umschreiben” der Delta-Tabelle hoffentlich herausgekommen ist.
So weit war ich auch, aber jetzt muss man doch die Grammatik kontextfrei machen, damit man sie auf Chomsky-Normalform bringen kann. Wie stellt man das an?
Edit: Hätte ich genauer gelesen, wäre mir aufgefallen, dass da Chomsky-0 steht und nicht Chomsky-Normalform.