computationpushdown-automatonautomata-theoryjflap

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


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.


Solution

  • 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:

    1. Enqueue as as long as you see as, until you see a b.
    2. Dequeue as and enqueue bs as long as you see bs, until you see a c
    3. Dequeue bs as long as you see cs.
    4. Accept if you end this process with no additional input and an empty queue.

    Two-stack PDA:

    1. Use the first stack to make sure a^n b^n by pushing a when you see an a and popping a when you see a b;
    2. Use the second stack to make sure b^n c^n by pushing b when you see a b and popping b when you see a c;
    3. Accept if both stacks are empty at the end of this process.

    Turing machine:

    1. Ensure a^n ... c^n by replacing each a with A and erasing a matching c;
    2. Ensure A^n b^n by erasing matching pairs of A and b;
    3. Accept if at the end of this process you have no more A and no more b, i.e., the tape has been completely cleared.