Embedded pushdown automaton
An embedded pushdown automaton or EPDA is a computational model for parsing languages generated by treeadjoining grammars (TAGs). It is similar to the contextfree grammarparsing 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 contextfree grammars and contextsensitive grammars, or a subset of the mildly contextsensitive grammars. Embedded pushdown automata should not be confused with nested stack automata which have more computational power.^{[citation needed]}
Contents
History and applications
EPDAs were first described by K. VijayShanker in his 1988 doctoral thesis.^{[1]} They have since been applied to more complete descriptions of classes of mildly contextsensitive 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 contextfree grammars (see transformationalgenerative 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]}
Theory
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 , and so we define an element of a stack by , 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 th stack in the automaton using a doubledagger symbol: ,^{[clarification needed]} where would be the next accessible symbol in the stack. The embedded stack of stacks can thus be denoted by .^{[clarification needed]}
We define an EPDA by the septuple (7tuple)
 where
 is a finite set of states;
 is the finite set of the input alphabet;
 is the finite stack alphabet;
 is the start state;
 is the set of final states;
 is the initial stack symbol
 is the transition function, where are finite subsets of .
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
where is the current state, the s are the stacks in the embedded stack, with the current stack, and for an input string , is the portion of the string already processed by the machine and is the portion to be processed, with its head being the current symbol read. Note that the empty string 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
where and 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.2325.
korder EPDA and the Weir hierarchy
This article is in need of a cleanup. You can help out Infogalactic by reorganizing parts of the article, checking grammar and spelling, and doing other helpful things to correct the article.

A more precisely defined hierarchy of languages that correspond to the mildly contextsensitive 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^{[clarify]} where the Level1 is defined as contextfree, and Level2 is the class of treeadjoining and the other three grammars.
Following are some of the properties of Levelk languages in the hierarchy:
 Levelk languages are properly contained in the Level(k + 1) language class
 Levelk languages can be parsed in time
 Levelk contains the language , but not
 Levelk contains the language , but not
Those properties correspond well (at least for small k > 1) to the conditions of mildly contextsensitive languages imposed by Joshi, and as k gets bigger, the language class becomes, in a sense, less mildly contextsensitive.
See also
References
 ↑ VijayShanker, K. (January 1988). "A Study of TreeAdjoining Grammars". Ph.D. Thesis. University of Pennsylvania.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Weir, David J. (1994). "Linear Iterated Pushdowns" (PDF). Computational Intelligence. 10 (4): 431–439. doi:10.1111/j.14678640.1994.tb00007.x. Retrieved 20121020.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ ^{3.0} ^{3.1} Joshi, Aravind K.; Yves Schabes (1997). "TreeAdjoining Grammars" (PDF). Handbook of Formal Languages. Springer. 3: 69–124. Retrieved 20140207.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Weir, D. J. (1992), "A geometric hierarchy beyond contextfree languages" (PDF), Theoretical computer science, 104 (2): 235–261, doi:10.1016/03043975(92)90124X.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Nabil Anton Khabbaz (1972). Generalized contextfree languages (Ph.D.). University of Iowa.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Nabil Anton Khabbaz (1974). "A geometric hierarchy of languages" (PDF). J. Comput. System Sci. 8: 142–157. doi:10.1016/s00220000(74)800528.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
Further reading
 Laura Kallmeyer (2010). Parsing Beyond ContextFree Grammars. Springer Science & Business Media. ISBN 9783642148460.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>