2
$\begingroup$

Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, unambiguous context-free languages may still be nondeterministic.

However, they never give an example. Is there a short, simple example of a context-free language that is

  • unambiguous
  • but nondeterministic
$\endgroup$
5
$\begingroup$

$\{ww^R\mid w\in\{a,b\}^∗\}$ should do the job. The rest is up to you regarding proofs, such as providing an unambiguous grammar.

From Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL? Third answer by Google.

Another one found similarly at Non-Deterministic CFLs: $\{x^ny^n \;\mid\; n \geq 0\} \cup \{x^ny^{2n} \;\mid\; n \geq 0\}$

$\endgroup$
  • $\begingroup$ So the language $ww^R$ does not have deterministic grammar? That's very interesting (so yacc shouldn't be able to parse it?) $\endgroup$ – ithisa May 27 '15 at 1:04
  • $\begingroup$ @user54609 AFAIK, Yacc will parse a lot of languages that are not deterministic, or grammars that are not LR(k). It makes choices, when it has to (with consequences you may guess). But I am not a big Yacc user, so you should rather check the Yacc literature,. $\endgroup$ – babou May 27 '15 at 7:45
  • $\begingroup$ I rather meant "parse without complaining about shift/reduce conflicts". $\endgroup$ – ithisa May 27 '15 at 19:30

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.