Pushdown automaton

In computer science, in particular automata theory, pushdown automata (PDA) are abstract devices that recognize context-free languages. Informally, a pushdown automaton is a finite automaton outfitted with access to a potentially unlimited amount of memory in the form of a single stack. The finite automaton in question is usually a Nondeterministic finite state machine (resulting in a nondeterministic pushdown automaton or NPDA) since deterministic pushdown automata cannot recognize all context-free languages. 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 machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine. A NPDA W can be defined as a 7-tuple: $W=(Q,\backslash \backslash Sigma,\backslash \backslash Phi,\backslash \backslash sigma,s,\backslash \backslash Omega,F)$ where

• Q is a finite set of states
• Σ is a finite set of the input alphabet
• Φ is a finite set of the stack alphabet
• σ is a finite transition relation (Q × ( Σ & {ε}) × Φ) × ( Q × Φ^* )
• s is an element of Q; the start state
• Ω is the inital stack symbol
• F is subset of Q, consisting of the final states.

There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are easily shown to be equivalent: a final state can perform a pop loop to get to an empty stack, and a machine can detect an empty stack and enter a final state by detecting a unique symbol pushed by the initial state.

See also

• Stack machine

Category:Computational models cs:Zásobníkový automat de:Kellerautomat fi:Pinoautomaatti zh:%E4%B8%8B%E6%8E%A8%E8%87%AA%E5%8A%A8%E6%9C%BA

View Live Article.
This article is from Wikipedia. All text is available under GNU FDL