11 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

reshown | 11 views
0
is this question your self doubt ? i seen somewhere it

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)