Question

[4 points) Prove that the following language over = {a,b,c} is not context free: Li = {w/w has equal numbers of a, b, c's}.

Answer 1

Solution

Let "A" as a language over {a,b,c} with equal number of a,b,c's

Let "B" is {aⁱb^jc^k | i,j,k>=0} or a*b*c* that is regular

As we know the intersection of a context free language & regular language is context free(1st fact)

If "A" were context free then A∩B will be also context free

but A B equals {aⁿ bⁿ cⁿ | n>=0}

that is not context free(2nd fact) &

It follows that "A" is not context free

---

all the best