Pushdown automaton: Facts, Discussion Forum, and Encyclopedia Article

All Topics

Pushdown automaton

	Email		Print
	Bookmark		Link

	Pushdown automaton
	Home Discussion
	Topics Pushdown automaton Topic Home In automata theoryAutomata theory Summary In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve.... , a pushdown automaton (PDA) is a finite automatonFinite state machine A finite state machine or finite automaton is a model of behavior composed of states, transitions and actions.... that can make use of a stackStack (data structure) In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First ... containing data. Operation Pushdown automata differ from normal finite state machines in two ways: They can use the top of the stack to decide which transition to take. They can manipulate the stack as part of performing a transition. Pushdown automata choose a transition by indexing a table by input signal, current state, and the top of the stack. Normal finite state machines just look at the input signal and the current state: they have no stack to work with. Pushdown automata add the stack as a parameter for choice. Given an input signal, current state, and a given symbol at the top of the stack, a transition path is chosen. Pushdown automata can also manipulate the stack, as part of performing a transition. Normal finite state machines choose a new state, the result of following the transition. The manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is. The choice of manipulation (or no manipulation) is determined by the transition table. Put together: Given an input signal, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack. The (underlying) finite automation is specifically a nondeterministic finite state machineNondeterministic finite state machine Summary In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton is a finite... , giving what is technically known as a "nondeterministic pushdown automaton" (NPDA). If a deterministic finite state machineDeterministic finite state machine In the theory of computation, a deterministic finite state machine or deterministic finite automaton is a finite state... is used, then the result is a deterministic pushdown automatonDeterministic pushdown automaton In automata theory, a deterministic pushdown automaton is a deterministic finite automaton with an additional stack of symbo... (DPDA), a strictly weaker device. Nondeterminism means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol. If we allow a finite automaton access to two stacks instead of just one, we obtain a more powerful device, equivalent in power to a Turing machineTuring machine Turing machines are extremely basic symbol-manipulating devices which despite their simplicity can be adapted to simulate ... . A linear bounded automatonLinear bounded automaton A linear bounded automaton is a restricted form of a non-deterministic Turing machine.... is a device which is more powerful than a pushdown automaton but less so than a Turing machine. Pushdown automata are equivalent to context-free grammars: for every context-free grammar, there exists a pushdown automaton such that the language generated by the grammar is identical with the language generated by the automaton, and for every pushdown automaton there exists a context-free grammar such that the language generated by the automaton is identical with the language generated by the grammar. Example The following is the formal description of the PDA which recognizes the language : Q = = = F = (q₁, , ) = (q₂, 0, ) = (q₂, 1, 0) = (q₃, 1, 0) = (q₃, , $) = (q, w, a) = for any other values of state, input and stack symbols. Understanding the computation process The following illustrates how the above PDA computes on different input strings. (a) Input string = 0011 (i) write (q₁, , ) (q₂, $) to represent (q₂, $) (q₁, , ) s₀ = , s₁ = $, t = , a = , b = $ set r₀ = q₂ (ii) (r₀, 0, ) = (q₂, 0, ) (q₂, 0) s₁ = $, a = , t = $, b = 0, s₂ = 0$ set r₁ = q₂ (iii) (r₁, 0, ) = (q₂, 0, ) (q₂, 0) s₂ = 0$, a = , t = 0$, b = 0, s₃ = 00$ set r₂ = q₂ (iv) (r₂, 1, 0) = (q₂, 1, 0) (q₃, ) s₃ = 00$, a = 0, t = 0$, b = , s₄ = 0$ set r₃ = q₃ (v) (r₃, 1, 0) = (q₃, 1, 0) (q₃, ) s₄ = 0$, a = 0, t = $, b = , s₅ = $ (vi) (q₃, , $) (q₄, ) s₅ = $, a = $, t = , b = , s₆ = set r₄ = q₄ Since q₄ is an accept state, 0011 is accepted. In summary, computation path = (q₁, q₂, q₂, q₂, q₃, q₃, q₄) and (r₀, r₁, r₂, r₃, r₄) = (q₂, q₂, q₂, q₃, q₄) (b) Input string = 001 Computation moves (i), (ii), (iii), (iv) would have to be the same as in case (a), otherwise, the PDA would have come to a dead end before reaching (v). (v) (r₃, , a) = (q₃, , a) Since s₄ = 0$, either a = or a = 0 In either case, (q₃, , a) = Therefore, computation comes to an end at r₃ = q₃ which is not an accept state. Therefore, 001 is rejected. (c) Input string = Set r₀ = q₁, r₁ = q₁ (r₀, , ) (q₁, ) Since q₁ is an accept state, is accepted. Generalized Pushdown Automaton (GPDA) A GPDA is a PDA which writes an entire string to the stack or removes an entire string from the stack in one step. A GPDA is formally defined as a 6-tuple where Q, , , q₀ and F are defined the same way as a PDA. is the transition function. Computation rules for a GPDA are the same as a PDA except that the a_i+1's and b_i+1's are now strings intead of symbols. GPDA's and PDA's are equivalent in that if a language is recognized by a PDA, it is also recognized by a GPDA and vice versa. One can formulate an analytic proof for the equivalence of GPDA's and PDA's using the following simulation: Let (q₁, w, x₁x₂...x_m) (q₂, y₁y₂...y_n) be a transition of the GPDA where q₁, q₂ Q, w , x₁x₂...x_m , m0, y₁y₂...y_n , n0. Construct the following transitions for the PDA: (p₁, ) (p₂, ) (p_m, ) (p_m+1, y_n) (p_m+2, y_n-1) (q₂, y₁) See also Stack machineStack machine In computer science, a stack machine is a model of computation in which the computer's memory takes the form of one or more ... context-free grammarContext-free grammar In linguistics and computer science, a context-free grammar is a formal grammar in which every production rule is of the fo... finite automaton External links on Planet Math. , simulator for several types of automata including nondeterministic pushdown automata