Ist jede eindeutige Grammatik regelmäßig?

Sep 15 2020

Bei der Suche nach einer Antwort auf diese Frage stellte ich fest, dass es für jede reguläre Sprache eine eindeutige Grammatik gibt. Aber gibt es für jede eindeutige Grammatik eine reguläre Sprache? Wie kann ich beweisen, dass dies wahr ist / nicht wahr ist?

Antworten

12 YuvalFilmus Sep 15 2020 at 18:14

Die folgende Grammatik ist eindeutig, erzeugt jedoch eine nicht reguläre Sprache: $$ S \to aSb \mid \epsilon $$