Page or3 zo 1. A2-PDA is a push-down automaton with two stacks instead of one. P
ID: 3717666 • Letter: P
Question
Page or3 zo 1. A2-PDA is a push-down automaton with two stacks instead of one. Prove that a 2-PDA is equivalent to a Turing Machine. Note that you will need to prove both of the following: A2-PDA can simulate a Turing Machine. (HINT: To get started, call the stacks the left stack and the right stack. To set up the simulation, begin by pushing"" onto the left and right stacks. Then, push every character in the input string onto the left stack. Then, pop every character from the left stack and a. push it onto the right stack. Below is partial transition diagram showing this set-up, where the input alphabet ? : 10,1] and ? " (0,1,..} where"-"is the blank character and qTM-start ls the start state for the Turing Machine simulation. You do not need to sketch a diagram for the simulation. lust describe the action of the 2-PDA based on the Turing Machine's transition function ?:0 x r-, Q ? ? x {IN). Note that all of the transtions in the simulation will be s-transitions, since the input was completely processed by the setup.) 0 Qlett setup QTM-startExplanation / Answer
PDA-Push Down Automata
push down automata is type of automaton which employs a stack which
stores the strings in it and do the computational calculations by using
the push and pop operations.
It is a tuple of six elements in it....
where
Q is the finite set of states.
Sigma is the finite set of the input symbols which is called as input alphabet
Tow is the finite set of elements of the stack which is called as stack alphabet
q0 is the initial state
delta is the transition from one state to the another state , which is called as
trasition function.
F is the final state.
PDA=FINITE AUTOMATA + MEMORY(STACK)
The two main important conditions to be checked before the string acceptance by the PDA ARE:-
*)Check the space in the stack inorder to push the strings into it
*)Before poping check whether the stack is empty or not because if
the stack is empty one can't perform the pop operation.
*)TWO STACK PDA:-
PDA which has the same computational power as the Turing Machine and
which contains the two stacks inorder to perform the push and pop
operations with the strings
The strength of tghe pda is increased by the increase in the no. of stacks in it.
Turing machine is the powerful computing machhine wghich performs any computional programs
and hellps them to simulate any computer program
Here it is brached into deterministic and non deterministic pda
Where Non-deterministic Two-Stack PDA is equivalent to a deterministic Two-Stack PDA.
The basic general move of the Two-Stack PDA is based on
*)The state of the finite control.
*)The input symbol read.
*)The top stack symbol on each of its stacks
The general differences between the Turing machine and the Two stack pda was
turing machine:-
Change in state
move the head left or right
two stack pda:-
change in state
Replace the symbol of each stack with the string of 0n or the more stack symbol
Two-Stack PDA simulate the TM tape :-
The baisc general idea is that the first stack can hold what is to the left
of the head, while the second stack holds what is to the right of the head.
When we want to get a symbol which is in the first stack , we will pop all the content in the first stack
above that symbol and push these content in the second stack which is the similar procedure like in turing machine .
In this way we can access any symbol stored in the stack without losing any content.
This allows to simulate the tape of Turing machine , where the Turing machine head is corresponding to the heads
of the two stacks of the Two-Stack PDA .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.