How do you suggest I go about proving this:

Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine.

The best I can come up with is that since TMs are equivalent to computers, where as PDAs are not. A TM accepting any PDA-accepted language is understandable. (Church-Turing thesis)

BTW, I know PDAs accept CFLs, but is that all they accept?


Simple, I don't know if you want the full answer but here is my proof:

We know that "A language is CF iff a PDA recognized it", and you know that this proof has two directions, I won't prove it here either. We can answer your question if we proof: "Any PDA has an equivalent TM".


Let state a TM M and a PDA P.

We know that any operation in P has the following format: a, b -> c, where a is the item you have at the input, b is at the top of the stack and c the symbol I want to put at the top of the stack. We can simulate all the possible operations of P on M and the stack on the tape.

How? P will be simulated on two tapes: one for reading the input and the other for simulating the stack ( we still can simulate on a single-tape TM, since any k-tape TM can be turned on a single one tape TM.) by adding elements to the tape and erasing them as we need. The blank symbol will now be allowed as part of the input symbols $\Sigma$ (so that we can "use" the pop instruction of a PDA).

(I won't go through this but if you want me to, I can rewrite it later).


We know by definition that P has the formal description:

"P is a 6-tuple(Q, $\Sigma ,\Gamma,\delta, qo, F$) where:

Q is a set of states,

$\Sigma$ is a finite set called the input set,

$\Gamma$ is a finite set called the stack set,

$\delta$ is a finite subset of $Q \times (\Sigma \cup\{\varepsilon\}) \times \Gamma \times Q \times \Gamma^* $, the transition relation.

q0 E Q is the start state,

F $\subseteq$ Q is the set of accepting states.


Great, now we'll make a transition algorithm that any TM can be turned into an AP, simply put:

Given an TM M, we'll create the formal transition to make an equivalent PDA:

1st step: We add the state "idle" on M, which is simply move to the left, do nothing, move to the right, do something.

2nd step: For every transition of P (a, b -> c), we'll create an equivalent in M $\delta$.

3rd step: The accept state will only happen if we erase the initial symbol of $\Sigma$ and the reject state if the input ends.

I think you'll get the idea, sorry for my english mistakes, if you want to make improvements, you are free to do so.


Explain simply that you can simulate a push-down automaton using a TM. Thus, you have to "implement" a stack, which should not be that hard. State of the PDA can be stored in the internal state of the TM.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.