World Library  
Flag as Inappropriate
Email this Article

Embedded pushdown automaton

Article Id: WHEBN0014345961
Reproduction Date:

Title: Embedded pushdown automaton  
Author: World Heritage Encyclopedia
Language: English
Subject: Automata theory, Combinatory categorial grammar, Models of computation, Range concatenation grammars, Thread automaton
Collection: Automata Theory, Models of Computation
Publisher: World Heritage Encyclopedia

Embedded pushdown automaton

An embedded pushdown automaton or EPDA is a computational model for parsing languages generated by tree-adjoining grammars (TAGs). It is similar to the context-free grammar-parsing pushdown automaton, except that instead of using a plain stack to store symbols, it has a stack of iterated stacks that store symbols, giving TAGs a generative capacity between context-free grammars and context-sensitive grammars, or a subset of the mildly context-sensitive grammars. Embedded pushdown automata should not be confused with nested stack automata which have more computational power.


  • History and applications 1
  • Theory 2
  • k-order EPDA and the Weir hierarchy 3
  • See also 4
  • References 5
  • Further reading 6

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 classes of mildly context-sensitive grammars and have had important roles in refining the Chomsky hierarchy. Various subgrammars, such as the linear indexed grammar, can thus be defined.[2] EPDAs 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 Joshi, Schabes (1997).[3]


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 = \ddagger\sigma_j = \{\sigma_{j,k}, \sigma_{j,k-1}, \ldots, \sigma_{j,1} \}, where \,\sigma_{j, 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 \,\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\} \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.

An informal description of EPDA can also be found in Joshi, Schabes (1997),[3] Sect.7, p.23-25.

k-order EPDA and the Weir hierarchy

A more precisely defined hierarchy of languages that correspond to the mildly context-sensitive class was defined by David J. Weir.[4] Based on the work of Nabil A. Khabbaz,[5][6] Weir's Control Language Hierarchy is a containment hierarchy of countable set of language classes where the Level-1 is defined as context-free, and Level-2 is the class of tree-adjoining and the other three grammars.

Following are some of the properties of Level-k languages in the hierarchy:

  • Level-k languages are properly contained in the Level-(k + 1) language class
  • Level-k languages can be parsed in O(n^{3\cdot2^{k-1}}) time
  • Level-k contains the language \{a_1^n \dotso a_{2^k}^n|n\geq0\}, but not \{a_1^n \dotso a_{2^{k+1}}^n|n\geq0\}
  • Level-k contains the language \{w^{2^{k-1}}|w\in\{a,b\}^*\}, but not \{w^{2^{k-1}+1}|w\in\{a,b\}^*\}

Those properties correspond well (at least for small k > 1) to the conditions of mildly context-sensitive languages imposed by Joshi, and as k gets bigger, the language class becomes, in a sense, less mildly context-sensitive.

See also


  1. ^ Vijay-Shanker, K. (January 1988). "A Study of Tree-Adjoining Grammars". Ph.D. Thesis ( 
  2. ^ Weir, David J. (1994). "Linear Iterated Pushdowns". Computational Intelligence 10 (4): 431–439.  
  3. ^ a b Joshi, Aravind K.; Yves Schabes (1997). "Tree-Adjoining Grammars". Handbook of Formal Languages (Springer) 3: 69–124. Retrieved 2014-02-07. 
  4. ^ Weir, D. J. (1992), "A geometric hierarchy beyond context-free languages", Theoretical computer science 104 (2): 235–261,  
  5. ^ Nabil Anton Khabbaz (1972). Generalized context-free languages (Ph.D.). University of Iowa. 
  6. ^ Nabil Anton Khabbaz (1974). "A geometric hierarchy of languages". J. Comput. System Sci. 8: 142–157.  

Further reading

  • Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.