HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

CFLs are inherently unambiguous?

Submitted by: @import:stackexchange-cs··
0
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?

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.