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$
1
  • $\begingroup$ Have you tried finding an unambiguous grammar for $a^nb^n$? $\endgroup$ – greybeard Sep 16 '20 at 6:58
12
$\begingroup$

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

$\endgroup$
3
  • 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 '20 at 22:53
  • $\begingroup$ It's been some time since my theory courses. Is this the trivial PDA? $\endgroup$ – chrylis -cautiouslyoptimistic- Sep 16 '20 at 6:10
  • 1
    $\begingroup$ This is a context-free grammar, not a push down automaton. $\endgroup$ – Yuval Filmus Sep 16 '20 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.