사용자:내용있음/작업장/내리누름 오토마타

 Deterministic pushdown automaton 문서를 참고하십시오.

In automata theory, a pushdown automaton (PDA) is a variation of finite automaton that can make use of a stack containing data.

Operation

a diagram of the pushdown automaton

Pushdown automata differ from finite state machines in two ways:

1. They can use the top of the stack to decide which transition to take.
2. 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 symbol at the top of the stack. This means that those three parameters completely determine the transition path that is chosen. 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.

Pushdown automata can also manipulate the stack, as part of performing a transition. 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.

In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations while others are not. Thus we have a model which is technically known as a "nondeterministic pushdown automaton" (NPDA). Nondeterminism means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol. If in every situation only one transition is available as continuation of the computation, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device.

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.

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, which is easy to prove. The reverse is true, though harder to prove: 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.

Formal Definition

A PDA is formally defined as a 7-tuple:

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$ where

• $\,Q$ is a finite set of states
• $\,\Sigma$ is a finite set which is called the input alphabet
• $\,\Gamma$ is a finite set which is called the stack alphabet
• $\,\delta$ is a finite subset of $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$, the transition relation, where $\Gamma ^{*}$ denote the set of strings over $\Gamma$ and $\varepsilon$ denotes the empty string.
• $\,q_{0}\in \,Q$ is the start state
• $\ Z\in \,\Gamma$ is the initial stack symbol
• $F\subseteq Q$ is the set of accepting states

An element $(p,a,A,q,\alpha )\in \delta$ is a transition of $M$. It has the intended meaning that $M$, in state $p\in Q$, with $a\in \Sigma \cup \{\varepsilon \}$ on the input and with $A\in \Gamma$ as topmost stack symbol, may read $a$, change the state to $q$, pop $A$, replacing it by pushing $\alpha \in \Gamma ^{*}$. The letter $\epsilon$ (epsilon) denotes the empty string and the $(\Sigma \cup \{\varepsilon \})$ component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.

In many texts the transition relation is replaced by an (equivalent) formalization, where

• $\,\delta$ is the transition function, mapping $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma$ into finite subsets of $Q\times \Gamma ^{*}$.

Here $\delta (p,a,A)$ contains all possible actions in state $p$ with $A$ on the stack, while reading $a$ on the input. One writes $(q,\alpha )\in \delta (p,a,A)$ for the function precisely when $(p,a,A,q,\alpha )\in \delta$ for the relation. Note that finite in this definition is essential.

Computations

a step of the pushdown automaton

In order to formalize the semantics of the pushdown automaton a description of the current situation is introduced. Any 3-tuple $(p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}$ is called an instantaneous description (ID) of $M$, which includes the current state, the part of the input tape that has not been read, and the contents of the stack (topmost symbol written first). The transition relation $\delta$ defines the step-relation $\vdash _{M}$ of $M$ on instantaneous descriptions. For instruction $(p,a,A,q,\alpha )\in \delta$ there exists a step $(p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )$, for every $x\in \Sigma ^{*}$ and every $\gamma \in \Gamma ^{*}$.

In general pushdown automata are nondeterministic meaning that in a given instantaneous description $(p,w,\beta )$ there may be several possible steps. Any of these steps can be chosen in a computation. With the above definition in each step always a single symbol (top of the stack) is popped, replacing it with as many symbols as necessary. As a consequence no step is defined when the stack is empty.

Computations of the pushdown automaton are sequences of steps. The computation starts in the initial state $q_{0}$ with the initial stack symbol $Z$ on the stack, and a string $w$ on the input tape, thus with initial description $(q_{0},w,Z)$. There are two modes of accepting. The pushdown automaton either accepts by final state, which means after reading its input the automaton reaches an accepting state (in $F$), or it accepts by empty stack ($\varepsilon$), which means after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory (state), the second the external memory (stack).

Formally one defines

1. $L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ with $f\in F$ and $\gamma \in \Gamma ^{*}\}$ (final state)
2. $N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )$ with $q\in Q\}$ (empty stack)

Here $\vdash _{M}^{*}$ represents the reflexive and transitive closure of the step relation $\vdash _{M}$ meaning any number of consecutive steps (zero, one or more).

For each single pushdown automaton these two languages need to have no relation: they may be equal but usually this is not the case. A specification of the automaton should also include the intended mode of acceptance. Taken over all pushdown automata both acceptance conditions define the same family of languages.

Theorem. For each pushdown automaton $M$ one may construct a pushdown automaton $M'$ such that $L(M)=N(M')$, and vice versa, for each pushdown automaton $M$ one may construct a pushdown automaton $M'$ such that $N(M)=L(M')$

Example

The following is the formal description of the PDA which recognizes the language $\{0^{n}1^{n}\mid n\geq 0\}$ by final state:

PDA for $\{0^{n}1^{n}\mid n\geq 0\}$ (by final state)

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ p,\ Z,\ F)$, where

$Q=\{p,q,r\}$

$\Sigma =\{0,1\}$

$\Gamma =\{A,Z\}$

$q_{0}=p$

$F=\{r\}$

$\delta$ consists of the following six instructions:

$(p,0,Z,p,AZ)$, $(p,0,A,p,AA)$, $(p,\epsilon ,Z,q,Z)$, $(p,\epsilon ,A,q,A)$, $(q,1,A,q,\epsilon )$, and $(q,\epsilon ,Z,r,Z)$.

In words, in state $p$ for each symbol $0$ read, one $A$ is pushed onto the stack. Pushing symbol $A$ on top of another $A$ is formalized as replacing top $A$ by $AA$. In state $q$ for each symbol $1$ read one $A$ is popped. At any moment the automaton may move from state $p$ to state $q$, while it may move from state $q$ to accepting state $r$ only when the stack consists of a single $Z$.

There seems to be no generally used representation for PDA. Here we have depicted the instruction $(p,a,A,q,\alpha )$ by an edge from state $p$ to state $q$ labelled by $a;A/\alpha$ (read $a$; replace $A$ by $\alpha$).

Understanding the computation process

accepting computation for $0011$

The following illustrates how the above PDA computes on different input strings. The subscript $M$ from the step symbol $\vdash$ is here omitted.

(a) Input string = 0011. There are various computations, depending on the moment the move from state $p$ to state $q$ is made. Only one of these is accepting.

(i) $(p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)$. The final state is accepting, but the input is not accepted this way as it has not been read.

(ii) $(p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)$. No further steps possible.

(iii) $(p,0011,Z)\vdash (p,011,AZ)\vdash (p,11,AAZ)\vdash (q,11,AAZ)$ $\vdash (q,1,AZ)\vdash (q,\epsilon ,Z)$ $\vdash (r,\epsilon ,Z)$. Accepting computation: ends in accepting state, while complete input has been read.

(b) Input string = 00111. Again there are various computations. None of these is accepting.

(i) $(p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)$. The final state is accepting, but the input is not accepted this way as it has not been read.

(ii) $(p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)$. No further steps possible.

(iii) $(p,00111,Z)\vdash (p,0111,AZ)\vdash (p,111,AAZ)\vdash (q,111,AAZ)$ $\vdash (q,11,AZ)\vdash (q,1,Z)$ $\vdash (r,1,Z)$. The final state is accepting, but the input is not accepted this way as it has not been (completely) read.

PDA and Context-free Languages

Every context-free grammar can be transformed into an equivalent pushdown automaton. The derivation process of the grammar is simulated in a leftmost way. Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule (expand). Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack (match). In a sense the stack of the PDA contains the unprocessed data of the grammar, corresponding to a pre-order traversal of a derivation tree.

Technically, given a context-free grammar, the PDA is constructed as follows.

1. $(1,\varepsilon ,A,1,\alpha )$ for each rule $A\to \alpha$ (expand)
2. $(1,a,a,1,\varepsilon )$ for each terminal symbol $a$ (match)

As a result we obtain a single state pushdown automaton, the state here is $1$, accepting the context-free language by empty stack. Its initial stack symbol equals the axiom of the context-free grammar.

The converse, finding a grammar for a given PDA, is not that easy. The trick is to code two states of the PDA into the nonterminals of the grammar.

Theorem. For each pushdown automaton $M$ one may construct a context-free grammar $G$ such that $N(M)=L(G)$.

Generalized Pushdown Automaton (GPDA)

A GPDA is a PDA which writes an entire string of some known length to the stack or removes an entire string from the stack in one step.

A GPDA is formally defined as a 6-tuple:

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)$

where Q, $\Sigma \,$, $\Gamma \,$, q₀ and F are defined the same way as a PDA.

$\,\delta$: $Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})$

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 instead 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 $\delta$(q₁, w, x₁x₂...x_m) $\longrightarrow$ (q₂, y₁y₂...y_n) be a transition of the GPDA

where $q_{1},q_{2}\in Q$, $w\in \Sigma _{\epsilon }$, $x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*}$, $m\geq 0$, $y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*}$, $n\geq 0$.

Construct the following transitions for the PDA:

$\delta ^{'}$(q₁, w, x₁) $\longrightarrow$ (p₁, $\epsilon$)

$\delta ^{'}$(p₁, $\epsilon$, x₂) $\longrightarrow$ (p₂, $\epsilon$)

$\vdots$

$\delta ^{'}$(p_m-1, $\epsilon$, x_m) $\longrightarrow$ (p_m, $\epsilon$)

$\delta ^{'}$(p_m, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (p_m+1, y_n)

$\delta ^{'}$(p_m+1, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (p_m+2, y_n-1)

$\vdots$

$\delta ^{'}$(p_m+n-1, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (q₂, y₁)

See also

• Stack machine
• Context-free grammar
• Finite automaton

References

• Michael Sipser (1997). 《Introduction to the Theory of Computation》. PWS Publishing. ISBN 0-534-94728-X.  Section 2.2: Pushdown Automata, pp.101–114.
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111-174.

External links

• non-deterministic pushdown automaton, on Planet Math.
• JFLAP, simulator for several types of automata including nondeterministic pushdown automata

이 문서는 일반 이름공간으로 이동될 경우 다음 분류에 배치될 예정입니다.

분류:

• Automata theory
• Models of computation