Konvertieren einer kontextfreien Grammatik in einen PDA

Konvertieren einer kontextfreien Grammatik in einen PDA - ist meine Lösung korrekt?

Ich überprüfe meine Halbzeit und wollte dies posten, um zu sehen, ob jemand Fehler erkennen kann. Ich soll einen PDA machen, der diese CFG erkennt:

$\qquad\begin{align} S &\to R1R1R1 \\ R &\to 0R \mid 1R \mid \varepsilon \end{align}$

Hier ist meine Lösung; Mir ist bewusst, dass ich vergessen habe, den zweiten Kreis um meinen akzeptierenden Zustand zu ziehen.

Geben Sie hier die Bildbeschreibung ein

formal-languages automata context-free pushdown-automata Raphael
quelle

In Ihrem Kurs wird wahrscheinlich der (einfache) Standardübersetzungsalgorithmus erwähnt. Haben Sie versucht, es anzuwenden? (Auch ist das Bild schwer zu entziffern.) Welches ist angeblich der Endzustand sein? Schließlich funktionieren Fragen mit dem Titel "Meine Antwort überprüfen" bei SE nicht so gut (für den Fall, dass die Antwort ein langweiliges "Ja, keine Fehler" ist.

Raphael

Das Auschecken dieser Frage könnte helfen.

Luke Mathieson

Antworten:

Nicht , dass die Sprache erkennen einfach eine beliebige Zeichenfolge in Das hat mindestens drei s drin? $\{0,1\}^*$ $1$

Wenn ja, brauchen Sie nur einen regulären endlichen deterministischen Automaten, der bis zu drei zählen kann, um ihn zu erkennen.

endlicher Automat, der bis drei zählt

Dies liegt daran, dass ich nicht in der Stimmung bin, eine direkte Übersetzung dieser Grammatik vorzunehmen, wenn Sie dies wirklich überprüfen wollten: P.

Hugomg
quelle