Ambiguous Grammar / Ambiguous Languages:
A CFG is said to be ambiguous if and only if it contains more than one derivation trees for same string.
- Definition of Ambiguous Grammar: Let G = (N,T, P, S ) be a CFG. A string w ∈ L(G) is said to be “ambiguously derivable “if there are two or more different derivation trees for that string in G.
- Definition of Ambiguous Grammar: A CFG given by G = (N, T, P, S) is said to be “ambiguous” if there exists at least one string in L(G) which is ambiguously derivable. Otherwise it is unambiguous.
Ambiguity is a property of a grammar, and it is usually, but not always possible to find an equivalent unambiguous grammar.
An “inherantly ambiguous language” is a language for which no unambiguous grammar exists.
Show that the grammar G with production
S → a | aAb | abSb
A → aAAb | bS
S ⟹ abSb ( ∵ S → abSb)
⟹ abab (∵ S → a)
S ⟹ aAb ( ∵ S → aAb)
⟹ abSb (∵ A → bS)
⟹ abab (∵ S → a)
Since ‘abab’ has two different derivations, the grammar G is ambiguous.
Proof of CFG is ambiguous or not by using parse tree solved example:
Consider the grammar G with production:
S → aSS
S → b
The parse trees are as follows.
Top down Parsing: Sequence of rules are applied in a leftmost derivation in Top down parsing.
Bottom-up Parsing: Sequence of rules are applied in a rightmost derivation in Bottom-up parsing.
Hence it is ambiguous because it consist more than one parse tree for a string w of L(G). To understand the parsing, A grammar can be used in two ways:
- Using the grammar to generate strings of the language.
- Using the grammar to recognize the strings.
“Parsing” a string is finding a derivation (or a derivation tree) for that string.
Parsing a string is like recognizing a string. The only realistic way to recognize a string of a context-free grammar is to parse it.