3
$\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
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\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\}$

Improve this answer
$\endgroup$
3
  • 1
    $\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
    Commented May 27, 2015 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
    Commented May 27, 2015 at 7:45
  • $\begingroup$ I rather meant "parse without complaining about shift/reduce conflicts". $\endgroup$
    – ithisa
    Commented May 27, 2015 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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