Awesome q2a theme
0 votes
8 views
Consider the Language:
L = {$a^{n}b^{n}c^{k}$, n,k ≥ 1} ⋃ {$a^{n}b^{k}c^{k}$, n,k≥ 1}
Which is True?
(a) All the Grammars generating L will be ambiguous.
(b) There exists a G which is unambiguous.
(c) Language L is unambiguous
(d) None of the above
in Theory of Computation by (281 points)
reshown by | 8 views
0
is this question your self doubt ? i seen somewhere it

1 Answer

0 votes
A context free language is called ambiguous if there is no unambiguous grammar to define that language

L = L1 union L2

L1 = {a^n b^n c^k, n,k ≥ 1} = { abc,aabbc,aabbcc, aaabbbcc, ………….}

L2 = { a^nb^kc^k , n,k > =1} = { abc,abbcc, aabbcc, aabbbccc ……. }

L = { abc, aabbc, abbcc, aabbcc, aaabbbcc, aabbbccc …………… }

U can generate aabbc only by L1 or abbcc only by L2. Thus there exist :
Let there exist a grammar G1 that generates aabbc :
G1 :
S → aSbA | ab
A → cA | c


Let there be another grammar G2 that generates abbcc :
G2 :
S → AbSc | bc

A → aA | a

But u can see that both G1 and G2 generate aabbcc.

So, there are 2 parse trees for the same string. So, both the grammars are ambiguous.

So, it is option A.
by (1.6k points)
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
932 questions
596 answers
1,885 comments
81,474 users