Embedded pushdown automaton

EPDAs were first described by K. Vijay-Shanker in his 1988 doctoral thesis.{{cite journal |last=Vijay-Shanker |first=K. |date=January 1988 |title= A Study of Tree-Adjoining Grammars |journal=Ph.D. Thesis |publisher= University of Pennsylvania |url= http://repository.upenn.edu/dissertations/AAI8804974 }} 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.{{cite journal |last=Weir |first=David J. |year=1994 |title=Linear Iterated Pushdowns|journal=Computational Intelligence|volume=10 |issue= 4|pages=431–439 |url=http://www.sussex.ac.uk/Users/davidw/resources/papers/ci94.pdf|access-date=2012-10-20|doi=10.1111/j.1467-8640.1994.tb00007.x|s2cid=205570628 }}

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).{{cite book |last=Joshi |first=Aravind K. |author2=Yves Schabes |chapter=Tree-Adjoining Grammars |year=1997 |title= Handbook of Formal Languages |publisher=Springer |volume=3 |pages=69–124 |chapter-url= http://www.seas.upenn.edu/~joshi/joshi-schabes-tag-97.pdf |access-date= 2014-02-07 |doi=10.1007/978-3-642-59126-6_2 |isbn=978-3-642-63859-6 }}

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 $\backslash ,\backslash Gamma$, and so we define an element of a stack by $\backslash ,\backslash sigma\_i\; \backslash in\; \backslash 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 $\backslash ,j$th stack in the automaton using a double-dagger symbol: $\backslash ,\backslash Upsilon\_j\; =\; \backslash ddagger\backslash sigma\_j\; =\; \backslash \{\backslash sigma\_\{j,k\},\; \backslash sigma\_\{j,k-1\},\; \backslash ldots,\; \backslash sigma\_\{j,1\}\; \backslash \}$,{{clarify|reason=Usually, curly braces build a set (where element ordering and repetition is ignored, e.g. {a,c,a,b} denotes the same set as {a,b,c}), while in a stack, ordering and repetition does matter. Probably, the notation used here is wrong, or at least misleading.|date=February 2014}} where $\backslash ,\backslash sigma\_\{j,\; k\}$ would be the next accessible symbol in the stack. The embedded stack of $\backslash ,m$ stacks can thus be denoted by $\backslash ,\backslash \{\backslash Upsilon\_j\; \backslash \}\; =\; \backslash \{\backslash ddagger\backslash sigma\_m,\backslash ddagger\backslash sigma\_\{m-1\},\; \backslash ldots,\; \backslash ddagger\backslash sigma\_1\; \backslash \}\; \backslash in\; (\backslash ddagger\backslash Gamma^+)^*$.{{clarify|reason=In the sentence before, (upsilon sub j) was explained to equal (ddagger (sigma sub j)), hence {upsilon sub j} would equal {ddagger (sigma sub j)}; however, now it is claimed to equal {ddagger (sigma sub m),...,ddagger (sigma sub 1)} instead. Moreover, in the rightmost term, it should be explained whether (((ddagger Gamma) sup +) sup *) or ((ddagger (Gamma sup +)) sup *) is meant, and what ddagger applied to the stack alphabet Gamma,or to (Gamma sup +), is supposed to mean. Finally, is should be explicitly mentioned that +, as I guessed, denotes the Kleene plus.|date=February 2014}}

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

:$\backslash ,M\; =\; (Q,\; \backslash Sigma,\; \backslash Gamma,\; \backslash delta,\; q\_0,\; Q\_\backslash textrm\{F\},\; \backslash sigma\_0)$ where

• $\backslash ,Q$ is a finite set of states;
• $\backslash ,\backslash Sigma$ is the finite set of the input alphabet;
• $\backslash ,\backslash Gamma$ is the finite stack alphabet;
• $\backslash ,q\_0\; \backslash in\; Q$ is the start state;
• $\backslash ,Q\_\backslash textrm\{F\}\; \backslash subseteq\; Q$ is the set of final states;
• $\backslash ,\backslash sigma\_0\; \backslash in\; \backslash Gamma$ is the initial stack symbol
• $\backslash ,\backslash delta\; :\; Q\; \backslash times\; \backslash Sigma\; \backslash times\; \backslash Gamma\; \backslash rightarrow\; S$ is the transition function, where $\backslash ,S$ are finite subsets of $\backslash ,Q\backslash times\; (\backslash ddagger\backslash Gamma^+)^*\; \backslash times\; \backslash Gamma^*\; \backslash times\; (\backslash ddagger\backslash 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

:$\backslash ,C(M)\; =\; \backslash \{q,\backslash Upsilon\_m\; \backslash ldots\; \backslash Upsilon\_1,\; x\_1,\; x\_2\backslash \}\; \backslash in\; Q\backslash times\; (\backslash ddagger\backslash Gamma^+)^*\; \backslash times\; \backslash Sigma^*\; \backslash times\; \backslash Sigma^*$

where $\backslash ,q$ is the current state, the $\backslash ,\backslash Upsilon$s are the stacks in the embedded stack, with $\backslash ,\backslash Upsilon\_m$ the current stack, and for an input string $\backslash ,x=x\_1\; x\_2\; \backslash in\; \backslash Sigma^*$, $\backslash ,x\_1$ is the portion of the string already processed by the machine and $\backslash ,x\_2$ is the portion to be processed, with its head being the current symbol read. Note that the empty string $\backslash ,\backslash epsilon\; \backslash in\; \backslash 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

:$\backslash ,L(M)\; =\; \backslash left\backslash \{\; x\; |\; \backslash \{q\_0,\backslash Upsilon\_0,\backslash epsilon,x\backslash \}\; \backslash rightarrow\_M^*\; \backslash \{q\_\backslash textrm\{F\},\backslash Upsilon\_m\; \backslash ldots\; \backslash Upsilon\_1,\; x,\; \backslash epsilon\backslash \}\; \backslash right\backslash \}$

where $\backslash ,q\_\backslash textrm\{F\}\; \backslash in\; Q\_\backslash textrm\{F\}$ and $\backslash ,\backslash 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), Sect.7, p. 23-25.

{{cleanup|section|reason=needs rewrite based on Kallmeyer p. 199|date=August 2014}}

A more precisely defined hierarchy of languages that correspond to the mildly context-sensitive class was defined by David J. Weir.{{Citation

| last=Weir

| first=D. J.

| year=1992

| title =A geometric hierarchy beyond context-free languages

| journal = Theoretical Computer Science

| volume = 104

| issue = 2

| pages = 235–261

| doi=10.1016/0304-3975(92)90124-X

| postscript=.

| doi-access=

}}

Based on the work of Nabil A. Khabbaz,{{cite thesis| type=Ph.D.| author=Nabil Anton Khabbaz| title=Generalized context-free languages| year=1972| publisher=University of Iowa}}{{cite journal| author=Nabil Anton Khabbaz| title=A geometric hierarchy of languages| journal=J. Comput. Syst. Sci.| year=1974| volume=8| issue=2| pages=142–157| doi=10.1016/s0022-0000(74)80052-8| doi-access=}}

Weir's Control Language Hierarchy is a containment {{clarify span|hierarchy of countable set of language classes|date=August 2014}} 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\backslash cdot2^\{k-1\}\})$ time
• Level-k contains the language $\backslash \{a\_1^n\; \backslash dotso\; a\_\{2^k\}^n|n\backslash geq0\backslash \}$, but not $\backslash \{a\_1^n\; \backslash dotso\; a\_\{2^\{k+1\}\}^n|n\backslash geq0\backslash \}$
• Level-k contains the language $\backslash \{w^\{2^\{k-1\}\}|w\backslash in\backslash \{a,b\backslash \}^*\backslash \}$, but not $\backslash \{w^\{2^\{k-1\}+1\}|w\backslash in\backslash \{a,b\backslash \}^*\backslash \}$

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.

• combinatory categorial grammar

{{reflist}}

• {{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0}}

{{Formal languages and grammars}}

Category:Models of computation

Category:Automata (computation)