2
$\begingroup$

As reading the textbook of Introduction to the theory of computation_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does not exist an ambiguous CFG that generates L.

Do we have any CFLs are inherently unambiguous? if so, can you please give me an example?

$\endgroup$
4
$\begingroup$

Every non-empty context-free language has an ambiguous grammar. Indeed, take any context-free grammar for the language, and add to it the production $S \to S$ (if it is not already there), where $S$ is the start symbol. Every word in the language has infinitely many derivations, since given a derivation, we can always come up with a longer one by adding an application of the rule $S \to S$ at the very beginning.

$\endgroup$

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.