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

7

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:

SR1R1R1R0R1Rε

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

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:

8

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