CS402 GDB Solution Feb 2015

GDB Topic:

Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine while dealing Context Free Languages (CFG)? Justify your point of view with logical reasons in either case.

Solution:  Yes it is true, Turing machines are more powerful than PDAs. The easiest example would be to show that Turing machines can describe Context Sensitive Languages.

One Turing machine is more powerful than one pushdown automaton — that is a fundamental theorem of automata theory and can be proved in a number of ways. For example, the halting problem for TMs is undecidable — there is no program (or other TM) that will always give a correct yes-or-no answer to the question: will this TM on this input halt. But for PDAs, the halting problem is solvable. So the models have inherently different power, the TM model has more power than the PDA model, but also “suffers” for it.

But two pushdown automata “working together” can simulate a Turing machine. We just have to specify what we mean by two PDAs working together — they are both connected to the input string and each can work with its stack independently of the other. Their finite state controls are also connected, or equivalently, merged into a single finite-state control.

The proof of that goes roughly that each of the PDAs can simulate half of the TM’s tape, that is, the part of the TMs tape starting at the home square and going out indefinitely to the left or right. The details can get a bit messy, but the basic idea is simple. The top of the “left” pushdown store represents the current head square of the TM and the bottom represents the leftmost active square of the TM’s tape; similarly for the “right” pushdown store. As for moves, for example, when the TM moves one square to the left, the simulating combo of PDAs pops a symbol from the right pushdown store and pushes it onto the top of the left pushdown store. When the TM rewrites the symbol under its head, the left pda pops its top symbol (the prior value) and pushes back another symbol (the new value).

So the combo of two PDAs working this way has exactly the same power as TMs, and the halting problem for the combo is also undecidable.