4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you tried finding an unambiguous grammar for $a^nb^n$? $\endgroup$ – greybeard Sep 16 at 6:58
12
$\begingroup$

The following grammar is unambiguous yet generates a non-regular language: $$ S \to aSb \mid \epsilon $$

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ As a side note, this works for every $a,b \in \Sigma$ where $a \neq b$. A very notable example would be the language of matched parenthesis $(^n)^n$. $\endgroup$ – Polygnome Sep 15 at 22:53
  • $\begingroup$ It's been some time since my theory courses. Is this the trivial PDA? $\endgroup$ – chrylis -cautiouslyoptimistic- Sep 16 at 6:10
  • 1
    $\begingroup$ This is a context-free grammar, not a push down automaton. $\endgroup$ – Yuval Filmus Sep 16 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.