Ambiguity in Context-Free Grammars - Automata Theory

What is Ambiguity in Context-Free Grammars?

While if a context free grammar G consists multiple derivation tree for some string w ∈ L(G), then it is called an ambiguous grammar. You can find multiple right-most or left-most derivations for some string generated from that grammar.

Problem

Now check following grammar G with production rules −

X → X+X | X*X |X| a

is ambiguous or not.

Solution

Let’s check out the derivation tree for the string "a+a*a". As it includes two leftmost derivations.

Derivation 1 − X → X+X → a +X → a+ X*X → a+a*X → a+a*a

Parse tree 1 −

parse_tree1

Derivation 2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

Parse tree 2 −

parse_tree2

If the two parse trees exists for a single string "a+a*a", then the grammar G is ambiguous.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics