Embedded pushdown automaton

From Wikipedia, the free encyclopedia

An embedded pushdown automaton or EPDA is a computational model that parse languages in the tree-adjoining grammar (TAG). It is similar to the context-free grammar-parsing pushdown automaton, except that instead of using a stack (data structure) to store symbols, it has a stack of iterated stacks that store symbols, giving TAGs a complexity between context-free grammars and context-sensitive grammars, or a subset of the mildly context-sensitive grammars.

[edit] History and applications

EPDAs were first described by K. Vijay-Shanker in his 1988 doctoral thesis^[1]. They have since been applied to more complete descriptions of the class of mildly context-sensitive grammars and have had important roles in extending and refining the Chomsky hierarchy to this class. Various subgrammars, such as the linear indexed grammar, can thus be defined^[2]. They are also beginning to play an important role in natural language processing.

While natural languages have traditionally been analyzed using context-free grammars (see transformational-generative grammar and computational linguistics), this model does not work well for languages with crossed dependencies, such as Dutch, situations for which an EPDA is well suited. A detailed linguistic analysis is available in ^[3].

[edit] Theory

To begin, we reiterate the an EPDA is a finite state machine with a set of stacks that can be themselves accessed through the embedded stack. Each stack contains elements of the stack alphabet $\,\Gamma$ , and so we define an element of a stack by $\,\sigma_i \in \Gamma^*$ , where the star is the Kleene closure of the alphabet.

Each stack can then be defined in terms of its elements, so we denote the $\,j$ th stack in the automaton using a double-dagger symbol: $\,\Upsilon_j = \ddagger\sigma_j = \{\sigma_{j,k}, \sigma_{j,k-1}, \ldots, \sigma_{j,1} \}$ , where $\,\sigma_k$ would be the next accessible symbol in the stack. The embedded stack of $\,m$ stacks can thus be denoted by $\,\{\Upsilon_j \} = \{\ddagger\sigma_m,\ddagger\sigma_{m-1}, \ldots, \ddagger\sigma_1 \} \in (\ddagger\Gamma^+)^*$ .

We define an EPDA by the septuple (7-tuple)

$\,M = (Q, \Sigma, \Gamma, \delta, q_0, Q_\textrm{F}, \sigma_0)$ where

$\,Q$ is a finite set of states;
$\,\Sigma$ is the finite set of the input alphabet;
$\,\Gamma$ is the finite stack alphabet;
$\,q_0 \in Q$ is the start state;
$\,Q_\textrm{F} \subseteq Q$ is the set of final states;
$\,\sigma_0 \in \Gamma$ is the initial stack symbol
$\,\delta : Q \times \Sigma \times \Gamma \rightarrow S$ is the transition function, where $\,S$ are finite subsets of $\,Q\times (\ddagger\Gamma^+)^* \times \Gamma^* \times (\ddagger\Gamma^+)^*$ .

Thus the transition function takes a state, the next symbol of the input string, and the top symbol of the current stack and generates the next state, the stacks to be pushed and popped onto the embedded stack, the pushing and popping of the current stack, and the stacks to be considered the current stacks in the next transition. More conceptually, the embedded stack is pushed and popped, the current stack is optionally pushed back onto the embedded stack, and any other stacks one would like are pushed on top of that, with the last stack being the one read from in the next iteration. Therefore, stacks can be pushed both above and below the current stack.

A given configuration is defined by

$\,C(M) = \{q,\Upsilon_m \ldots \Upsilon_1, x_1, x_2\} \in Q\times (\ddagger\Gamma^+)^* \times \Sigma^* \times \Sigma^*$

where $\,q$ is the current state, the $\,\Upsilon$ s are the stacks in the embedded stack, with $\,\Upsilon_m$ the current stack, and for an input string $\,x=x_1 x_2 \in \Sigma^*$ , $\,x_1$ is the portion of the string already processed by the machine and $\,x_2$ is the portion to be processed, with its head being the current symbol read. Note that the empty string $\,\epsilon \in \Sigma$ is implicitly defined as a terminating symbol, where if the machine is at a final state when the empty string is read, the entire input string is accepted, and if not it is rejected. Such accepted strings are elements of the language

$\,L(M) = \left\{ x | \{q_0,\Upsilon_0,\epsilon,x\} \rightarrow_M^* \{q_\textrm{F},\Upsilon_m \ldots \Upsilon_1, x, \epsilon\} \right\}$

where $\,q_\textrm{F} \in Q_\textrm{F}$ and $\,\rightarrow_M^*$ defines the transition function applied over as many times as necessary to parse the string.

[edit] References

^ Vijay-Shanker, K. (January 1988). "A Study of Tree-Adjoining Grammars". Ph.D. Thesis. University of Pennsylvania.
^ Weir, David J. (1994). "Linear Iterated Pushdowns". Computational Intelligence 10: 431--439.
^ Joshi, Aravind K.; Yves Schabes (1997). "Tree-Adjoining Grammars". Handbook of Formal Languages 3: 69--124. Springer.

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining etc.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a		Star-free	Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it.