Embedded pushdown automaton

Embedded pushdown automaton

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.

History and applications

EPDAs were first described by K. Vijay-Shanker in his 1988 doctoral thesis [cite journal |last=Vijay-Shanker |first=K. |authorlink= |coauthors= |year=1988 |month=January |title=A Study of Tree-Adjoining Grammars |journal=Ph.D. Thesis |publisher=University of Pennsylvania |volume= |issue= |pages= |id= |url= |accessdate= |quote= ] . 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 [cite journal |last=Weir |first=David J. |authorlink= |coauthors= |year=1994 |month= |title=Linear Iterated Pushdowns |journal=Computational Intelligence |volume=10 |issue= |pages=431--439 |id= |url=http://www.informatics.sussex.ac.uk/users/davidw/papers/ci94.ps |accessdate= 2007-11-21 |quote=|doi=10.1111/j.1467-8640.1994.tb00007.x ] . 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 [cite journal |last=Joshi |first=Aravind K. |authorlink= |coauthors=Yves Schabes |year=1997 |month= |title=Tree-Adjoining Grammars |journal=Handbook of Formal Languages |publisher=Springer |volume=3 |issue= |pages=69--124 |id= |url=http://www.cis.upenn.edu/~cse477/ltag-paper.pdf |accessdate= 2007-11-21 |quote= ] .

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 ,jth stack in the automaton using a double-dagger symbol: ,Upsilon_j = ddaggersigma_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 } = {ddaggersigma_m,ddaggersigma_{m-1}, ldots, ddaggersigma_1 } in (ddaggerGamma^+)^*.

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

:,M = (Q, Sigma, Gamma, delta, q_0, Q_ extrm{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_ extrm{F} subseteq Q is the set of "final states";
* ,sigma_0 in Gamma is the "initial stack symbol"
* ,delta : Q imes Sigma imes Gamma ightarrow S is the "transition function", where ,S are finite subsets of ,Q imes (ddaggerGamma^+)^* imes Gamma^* imes (ddaggerGamma^+)^*.

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 imes (ddaggerGamma^+)^* imes Sigma^* imes Sigma^*

where ,q is the current state, the ,Upsilons 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} ightarrow_M^* {q_ extrm{F},Upsilon_m ldots Upsilon_1, x, epsilon} ight}

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

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Deterministic pushdown automaton — In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack. A deterministic… …   Wikipedia

  • Nested stack automaton — In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack… …   Wikipedia

  • Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… …   Wikipedia

  • Mildly context-sensitive language — In formal grammar theory, mildly context sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced …   Wikipedia

  • Tree-adjoining grammar — (TAG) is a grammar formalism defined by Aravind Joshi. Tree adjoining grammars are somewhat similar to context free grammars, but the elementary unit of rewriting is the tree rather than the symbol. Whereas context free grammars have rules for… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Nested word — In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of… …   Wikipedia

  • Chomsky hierarchy — Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of… …   Wikipedia

  • Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”