How do you show that the language L= { $ a^nb^nc^na^kb^lc^m : k,l,m,n >0 $ } is not a cfg?

111 Views Asked by At

I understand how for the language $ a^nb^nc^n $ it is a straightforward application of the pumping lemma, but the part after that seems to exclude the possibility of using the pumping lemma. I would like to know whether there is some way of using any closure property to do the same. Also is there some stronger version of the pumping lemma where it could be applied to some subset of the string rather than the entire string? I mean if we could just apply the pumping lemma on the $ a^nb^nc^n $ out of the $ a^nb^nc^na^kb^lc^m $ ?

1

There are 1 best solutions below

8
On BEST ANSWER

HINT: If $p$ is the pumping length, apply the pumping lemma to the word $a^pb^pc^pabc$ and pump down.