patternMinor
Unambiguous but nondeterministic context-free language?
Viewed 0 times
freebutunambiguouslanguagenondeterministiccontext
Problem
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
However, they never give an example. Is there a short, simple example of a context-free language that is
- unambiguous
- but nondeterministic
Solution
$\{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\}$
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\}$
Context
StackExchange Computer Science Q#42904, answer score: 6
Revisions (0)
No revisions yet.