World's most popular travel blog for travel bloggers.

[Answers] Proof for TM accepting any PDA-language

, , No Comments
Problem Detail: 

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?

Asked By : matttm

Answered By : Felipe Bormann

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback