What is PDA
In computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
The PDA is used in theories about what can be computed by machines. It is more capable than a finite-state machine but less capable than a Turing machine. Because its input can be described with a formal grammar, it can be used in parser design. The deterministic pushdown automaton can handle all deterministic context-free languages while the non-deterministic version can handle all context-free languages.
The term “pushdown” refers to the fact that the stack can be regarded as being “pushed down” like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than deterministic pushdown automata.[citation needed] A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.
READ MORE >>
READ MORE >>
What is 2PDA
Formal Definition of Two-Stack Push Down Automaton
is two-stack pushdown automaton to be a sextuple
M = (K, Σ, Γ, Δ, s, F)
K is a finite set of states,
Σ is an alphabet (the input symbols),
Γ is an alphabet (the stack symbols),
s belongs to K is the initial state,
F is subset of K is the set of final states, and
Δ, the transition relation, is a finite subset of (K x (Σ U {e}) x Γ* x Γ*) x (K x Γ* x Γ*), where the third parameter pops the first stack, the fourth parameter pops the second stack, the fifth parameter pushes a symbol onto the first stack, and the sixth parameter pushes a symbol onto the second stack.
is two-stack pushdown automaton to be a sextuple
M = (K, Σ, Γ, Δ, s, F)
K is a finite set of states,
Σ is an alphabet (the input symbols),
Γ is an alphabet (the stack symbols),
s belongs to K is the initial state,
F is subset of K is the set of final states, and
Δ, the transition relation, is a finite subset of (K x (Σ U {e}) x Γ* x Γ*) x (K x Γ* x Γ*), where the third parameter pops the first stack, the fourth parameter pops the second stack, the fifth parameter pushes a symbol onto the first stack, and the sixth parameter pushes a symbol onto the second stack.
Relation of Two-Stack PDA to Chomsky Hierarchy
In order to discuss where a two-stack PDA falls into the Chomsky Hierarchy, it is important to first explore its relation to a Turing Machine. Every two-stack PDA can be represented by a Turing Machine. To see this divide the Turing Machine’s tape into three areas, the first area corresponds to the input string of the PDA, the second area corresponds to the first stack’s contents, and the third area corresponds to the second stack’s contents.
A push to the first or second stack is accomplished by the Turing Machine instruction that inserts the symbol being pushed to the cell that represents the top of the stack in the appropriate region.
A pop to the first or second stack is accomplished by the Turing Machine instruction that reads the cell corresponding to the top of the stack in the appropriate region and then deletes that symbol, making sure to shift left all the cells that follow it.
A reading of the input string in the two-stack PDA is accomplished by the Turing Machine instruction that reads the symbol at a cell on the Turing Machine’s region of the tape that represents the input string of the PDA and then overwriting it with a ‘b’ (the blank symbol).
Thus using this algorithm, every two-stack PDA can be converted into a Turing Machine. There also exists an algorithm to convert every Turing Machine into a two-stack PDA. The two stacks are used to represent what is before and after the read head on the Turing Machine’s tape. When the Turing Machine’s head moves to the left or right, the two-stack PDA shifts symbols from the first stack to the second stack and vice versa. Thus every Turing Machine can be represented by a two-stack PDA. Since every Turing Machine can be represented by a two-stack PDA and every two-stack PDA can be represented by a Turing Machine, the two are equal.
From the fact that two-stack PDA’s are essentially Turing Machines, it falls into the same place on the Chomsky hierarchy as Turing Machines. That means it can solve all problems that are solvable by a Turing Machine. From the Church-Turing thesis, we know that each Turing Machine is essentially an algorithm. Since every two-stack PDA is essentially a Turing Machine, it must be an algorithm also. Also, we know that a non-deterministic two-stack PDA is no more powerful than a deterministic PDA, because non-deterministic Turing Machines are no more powerful than deterministic Turing Machines. They may be able to calculate something more efficiently, but they are not more powerful.
No comments:
Post a Comment