Pushdown automata are similar to NFAs, but in addition have a stack. That stack

Question

Pushdown automata are similar to NFAs, but in addition have a stack. That stack lets them accept a much broader set of languages than NFAs. Here, we'll consider what happens if we give a PDA 2 stacks instead. This means, at each step we can either pop from both stacks, push to both stacks, pop from one and push to the other, push to one and leave the other unchanged, etc. Build a 2-stack PDA of this sort that will accept the language a^nb^nc^n - since that language is not context-free, this means that 2-stack PDAs can be built to accept a wider range of language than normal PDAs.

Explanation / Answer

I am not sure how you are supposed to represent push operation into two stacks, so am generalizing the algorithm using Natural Language. I believe that you can represent it in your assignment well.

First, we are at state 1 and when we encounter a in the input tape we push a stack symbol, let it be X in both the stacks.

Then when we encounter b in the input string we move to state 2 and pop a single stack symbol from the first stack. We remain in state 2 until we encounter first c in the input string.

Then when we encounter c in the input string we move to state 3 and pop a single stack symbol from the second stack. We remain in state 3 till end of string is reached.

After completion, we accept the string if both the stacks are empty.

NOTE:
We cannot encounter c while in state 1,

We cannot encounter a while in state 2,

We cannot encounter a,b while in state 3,

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.