CODEWITHSUNDEEP
computationpushdown-automatonautomata-theoryjflap
NeoR
NeoR

Reputation: 353

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.

Upvotes: 1

Views: 19122

Answers (2)

Patrick87
Patrick87

Reputation: 28312

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.

Upvotes: 1

Ami Tavory
Ami Tavory

Reputation: 76366

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

  • uvnwxny 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.

Upvotes: 1

Related Questions