PushDown Automaton (PDA) for L={a^(n)b^(n)c^(n)|n>=1}

Question

I am on a fool's errand trying to construct a Pushdown automaton for the non-context-free language L={a^(n)b^(n)c^(n)|n>=1} and thought of two approaches.

First approach:-

I thought that for every 'a' in string I will push 3 'a' into the stack and for every 'b' in the string, I will pop 2 'a' from the stack now for every 'c' in the string I will still have 1 'a' in the stack.

Problem with the First approach:- the language generated becomes something like this L={a^(p)b^(m)c^(n)| p>=1 and could not determine how m and n can be defined}

Second approach:-

We know that L={ a^(n)b^(m)c^(m)d^(n) | n>=0 } is a context-free language and L={ wxw | w∈(a,b)* } is also context-free language.

So, I thought L={ a^(n)b^(m)b^(m)c^(n) | n>=1 and m=floor((n+1)/2) }

Problem with the Second approach:- don't know if we can calculate floor(n+1/2) in the PDA without disturbing the elements of the stack.

Please help in determining how m and n can be defined in the first approach and how can I find floor((n+1)/2) in the PDA.

JFLAP files available for both if needed.

Answer 1

One reason you've not managed to construct a pushdown automaton for this language, is because there isn't any. The Bar Hillel pumping lemma shows this.

To outline the proof, suppose it can be done. Then, for some p, each string larger than p can be partitioned to uvwxy, s.t.,

• |vwx| < p

• |vx| > 1

• uvⁿwxⁿy is also accepted by the automaton, for any n.

The first rule implies that vwx can't span the three regions, only at most two (for large enough strings). The second and third rules now imply that you can pump so that the un-spanned region is smaller than the at least one of the other regions.