Is every unambiguous grammar regular?
-
29-09-2020 - |
Frage
While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I prove that this is/isn't true?
Lösung
The following grammar is unambiguous yet generates a non-regular language: $$ S \to aSb \mid \epsilon $$
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange