Ambiguous Grammar definition and solved examples

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.

1. 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.
2. 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.

Solved Example:

Show that the grammar G with production

S → a | aAb | abSb
A → aAAb | bS

is ambiguous.

Solution:

        S ⟹ abSb          ( ∵ S → abSb)
⟹ abab           (∵ S → a)

Similarly,

        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:

1. Using the grammar to generate strings of the language.
2. 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.