Grammar Ambiguity-
Before you go through this article, make sure that you have gone through the previous article on Ambiguous Grammar.
- There exists no algorithm to check whether any given grammar is ambiguous or not.
- This general decision problem is undecidable-
“Whether a grammar is ambiguous or not?”
- This is because it can be shown that this problem is equivalent to Post Correspondence Problem.
General Approach To Check Grammar Ambiguity-
To check whether a given grammar is ambiguous or not, we follow the following steps-
Step-01:
We try finding a string from the Language of Grammar such that for the string there exists more than one-
- parse tree
- or derivation tree
- or syntax tree
- or leftmost derivation
- or rightmost derivation
Step-02:
If there exists at least one such string, then the grammar is ambiguous otherwise unambiguous.
PROBLEMS BASED ON CHECKING WHETHER GRAMMAR IS AMBIGUOUS-
Problem-01:
Check whether the given grammar is ambiguous or not-
S → SS
S → a
S → b
Solution-
Let us consider a string w generated by the given grammar-
w = abba
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.
Problem-02:
Check whether the given grammar is ambiguous or not-
S → A / B
A → aAb / ab
B → abB / ∈
Solution-
Let us consider a string w generated by the given grammar-
w = ab
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.
Problem-03:
Check whether the given grammar is ambiguous or not-
S → AB / C
A → aAb / ab
B → cBd / cd
C → aCd / aDd
D → bDc / bc
Solution-
Let us consider a string w generated by the given grammar-
w = aabbccdd
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.
Problem-04:
Check whether the given grammar is ambiguous or not-
S → AB / aaB
A → a / Aa
B → b
Solution-
Let us consider a string w generated by the given grammar-
w = aab
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.
Problem-05:
Check whether the given grammar is ambiguous or not-
S → a / abSb / aAb
A → bS / aAAb
Solution-
Let us consider a string w generated by the given grammar-
w = abababb
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.
Problem-06:
Check whether the given grammar is ambiguous or not-
E → E + T / T
T → T x F / F
F → id
Solution-
- There exists no string belonging to the language of grammar which has more than one parse tree.
- Since a unique parse tree exists for all the strings, therefore the given grammar is unambiguous.
Problem-07:
Check whether the given grammar is ambiguous or not-
S → aSbS / bSaS / ∈
Solution-
Let us consider a string w generated by the given grammar-
w = abab
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous.
Problem-08:
Check whether the given grammar is ambiguous or not-
R → R + R / R . R / R* / a / b
Solution-
Let us consider a string w generated by the given grammar-
w = ab + a
Now, let us draw parse trees for this string w.
Since two different parse trees exist for string w, therefore the given grammar is ambiguous
Comments