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.
As Ami Tavory points out, there is no PDA for this language because this language is not context-free. It is easy to recognize this language if you use a queue instead of a stack, use two stacks, or use a Turing machine (all equivalent).
Queue machine:
a
s as long as you see a
s, until you see a b
.a
s and enqueue b
s as long as you see b
s, until you see a c
b
s as long as you see c
s.Two-stack PDA:
a^n b^n
by pushing a
when you see an a
and popping a
when you see a b
;b^n c^n
by pushing b
when you see a b
and popping b
when you see a c
;Turing machine:
a^n ... c^n
by replacing each a
with A
and erasing a matching c
;A^n b^n
by erasing matching pairs of A
and b
;A
and no more b
, i.e., the tape has been completely cleared.