Define CFG. When a CFG is called an ‘ambiguous CFG’?
What is CFG
-
A context free grammar (CFG) is a 4-tuple G = (V,Σ,S,P) where,
-
V is finite set of non terminals,
-
Σ is disjoint finite set of terminals,
-
S is an element of V and it’s a start symbol,
-
P is a finite set of productions of the form A -> α where A∈V and α ∈ (V ∪ Σ)^*.
When is a CFG called Ambiguous CFG
-
A CFG is said to ambiguous if there exists more than one derivation tree for the given input string i.e.,
-
more than one LeftMost Derivation Tree (LMDT) or RightMost Derivation Tree (RMDT).
