Ich habe eine FA zu definieren, indem diese Grammatik:Regeln zum Konvertieren eines CFG zu einem NDPA?
S -> aSb
S -> c
S -> dA
A -> Sd
Wie kann ich die erste Regel und die letzten verwalten? Für den zweiten muss ich einen anderen Zustand (den letzten) schaffen und S und diesen neuen Zustand verbinden. Für die dritte stattdessen, ich denke, ich muss den Zustand "A" erstellen und es mit S verbinden, indem Sie "d" übergeben.
Es gibt Algorithmen, die Sie verwenden können, um einen PDA von einem CFG zu erhalten: schauen Sie sich zum Beispiel in Top-Down- und Bottom-Up-Parser um. Was ich für den üblichen Beweis halte, dass PDAs Sprachen akzeptieren, die von CFGs generiert werden, und umgekehrt, verwendet eine solche Konstruktion.
Eine Alternative ist es, die von der Grammatik erzeugte Sprache zu verstehen und einen PDA dafür direkt zu entwerfen. Dies ist weniger mechanisch, hat aber das Potenzial, einen präziseren PDA zu liefern. Wenn Sie diesen Weg gehen wollen, können wir zunächst die Grammatik vereinfachen, indem die Nicht-Terminal A Anerkennung sicher durch die RHS der einzige Produktion für sie ersetzt werden kann:
S -> aSb
S -> c
S -> dSd // removed A -> Sd and replaced here
Wie funktioniert diese Grammatik arbeiten?
c in der Mitte von der 2. Produktion;d s auf der linken und rechten Seite der c;a s auf der linken Seite passend b s auf der rechten Seite c.Ein PDA ist wie folgt arbeiten:
a s und d s, bis Sie einen c sehen. Schieben Sie alles auf den Stapel, während Sie gehen. Wenn Sie eine c sehen, gehen Sie zum nächsten Zustand, aber drücken Sie nicht die c.b s und d s, knallend a s und d s vom Stapel, bis:
Hier ist eine Übergangstabelle:
q s x q' s'
------------------------------
q0 a,d,Z a q0 aa,ad,aZ
q0 a,d,Z d q0 da,dd,dZ
q0 a,d,Z c q1 a,d,Z
q1 a b q1 -
q1 d d q1 -
Wenn wir in q1 durch leere Stapel akzeptieren, diese Übergänge genug sind. Wenn wir akzeptieren möchten, dass der Stack leer oder der Status akzeptiert wird, können wir einen Übergang wie f(q1, Z, -) = (q2, Z) hinzufügen und q2 akzeptieren; der PDA würde dort nichtdeterministisch übergehen und würde abstürzen, wenn die Eingabe nicht auch erschöpft wäre.
Der Titel Ihrer Frage zeigt an, dass Sie ein LLG haben, aber Sie nicht sicherlich. Was fragst du?Fragen Sie, wie man einen endlichen Automaten für diese Grammatik herstellt? Diese Grammatik ist nicht regelmäßig. –
Hallo, ich dachte, das war eine linke lineare Grammatik wegen der letzten Regel. Wie gehe ich vor, um den FA zu erstellen? –
Nein, ein LLG ist einer, in dem _alle_ Regeln, nicht nur eine, ein einzelnes Nicht-Terminal auf der linken Seite haben. Sie können mit dieser Grammatik keinen FA erstellen. Die Grammatik ist nicht regulär (wegen der ersten Regel). Kein FA existiert. Sie können jedoch ein NDPA erstellen, da die Sprache definitiv kontextfrei ist. Wo hast du dieses Problem? –