Kann es in einer kontextfreien Grammatik "tote Zustände" geben?

Kann eine kontextfreie Grammatik "tote Zustände" von einem Automaten enthalten, wie z

G = ({ein, b, c}, {EIN, B, C}, {EIN \to ein B, B \to b, B \to C, C \to c C}, EIN) ?

$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$

Die Produktionsregeln und werden für immer wiederholt und erzeugen niemals ein Wort. Ist dies erlaubt oder MÜSSEN Produktionsregeln irgendwann mit einem Terminal enden? $B\to C$ $C\to cC$

context-free automata formal-grammars r3r57
quelle

Antworten:

Kontextfreie Grammatiken dürfen unproduktive Regeln enthalten . Dies wird akzeptiert, da jede CFG die gleiche Sprache wie eine richtige CFG erzeugt, die keine unproduktiven Regeln, keine Leerstring-Produktionen und keine Zyklen enthält. Man kann also mit Sicherheit davon ausgehen, dass ein CFG einwandfrei ist, ohne an Allgemeinheit zu verlieren.

ilke444
quelle

Nicht ganz: Richtige CFGs müssen zwei weitere Anforderungen erfüllen. Also würde ich das umformulieren.

Reinierpost

@reinierpost: Ich denke, es gibt Klassen von CFGs, die unproduktive Regeln verbieten, aber immer noch nicht korrekte CFGs enthalten. Ich denke, die Neuformulierung könnte so einfach sein wie: "Es sei denn, es handelt sich zum Beispiel um"

mhelvens

Ich meine, nicht jede CFG ohne unproduktive Regeln ist korrekt, was Ihrer Aussage widerspricht. Aber die Definition von richtigen CFGs, indem sie unproduktive Regeln explizit ausschließt, macht deutlich, dass diese in beliebigen CFGs möglich sind, so würde ich das schreiben.

Reinierpost

Vielen Dank für Ihre Verbesserungen. Ich wollte damit sagen, dass es Unterklassen von CFGs gibt, die solche Regeln nicht enthalten dürfen.

ilke444

Gibt es ein richtiges CFG, das keine unproduktiven Regeln, keine leeren String-Produktionen und keine Zyklen enthält, die dieselbe Sprache erzeugen wie ({a}, {A}, {A-> epsilon}, A)? Ich mag den ersten Satz. Vielleicht sollte der zweite Satz lauten: "Dies liegt daran, dass die Definition von CFGs eine endliche Folge von Terminals und Nicht-Terminals als linke Seite einer Produktion zulässt."

Theodore Norvell

Ja natürlich. Jede NFA kann als CFG geschrieben werden. Und das Bauen eines DFA mit einem "toten Zustand" (der Begriff, der mir beigebracht wurde, ist "sink") ist trivial.

G = ({ein}, {EIN}, {EIN \to EIN}, EIN)

$G = (\{a\}, \{A\}, \{A\to A\},A)$

{a}

$\{a\}$

$\epsilon$

David
quelle