Question

4. (Non-CFLs) Prove that the following languages are not context-free.

(b) The following language over the alphabet {a, b, c}:

B = {aⁱx | i ≥ 0, x ∈ {b, c}^* , and if i = 1 then x = ww for some string w}.

(Careful: B satisfies the pumping lemma for CFLs! Make sure you understand why, but you don’t need to write it down.)

Answer 1

If you take   i=1    x= aww , It is not CFL .

Example L = { WW | W belongs to {a, b}* } is not context free.

One might think to draw a non-deterministic push down automaton, but it will not help as first symbol will be at

bottom of the stack and when the second W starts, we will not be able to compare it with the bottom of stack.

Because CFL is accept by PDA(push down automata)   and PDA use stack .

stack can accept W W^r   where   W^r is reverse/palindrome of W , but not WW.

-> Stack is LIFO(last in first out ) means what's we push in stack , we pop out reverse of it .

And ww is a subset of B(B=aix i>=0 as given in question) . So if subset is not CFL , then its superset also not CFL.