patternMinor
CFLs are inherently unambiguous?
Viewed 0 times
arecflsinherentlyunambiguous
Problem
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?
Do we have any CFLs are inherently unambiguous? if so, can you please give me an example?
Solution
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.
Context
StackExchange Computer Science Q#92122, answer score: 4
Revisions (0)
No revisions yet.