Two-cellar machine

The term two-cellar machine (TPDA - Two-stack Push Down Automaton ) stands for a special machine model in theoretical computer science . In particular, it has acquired a special meaning for a uniform representation of automaton characterizations of the language classes of the Chomsky hierarchy and other classes.

The classic terms Turing machine , linearly restricted automaton , push-down automaton and finite automaton can be represented uniformly with special restrictions.

In addition, it allows the characterization of the class of increasingly context-sensitive languages introduced by Elias Dahlhaus and Manfred Warmuth .

Two different models are considered in the literature:

1. The two- cellar machine reads from an extra input belt and can use two cellars for storing and reading. 2-PDA is usually used here as an abbreviation.
2. The two-cellar machine receives its input directly in the cellar: The first character is at the top. This model is the younger model. TPDA (Two PushDown Automaton) is usually used here as an abbreviation.

In both cases it results that the two-cellar machine is already Turing-capable without further restrictions. In the first case, the machine with real-time input was examined in particular. This entry corresponds to the normal push-down automaton that only uses one basement. In the second case, various restrictions were defined with which different language classes can be uniformly characterized.

So limited and shrinking two-cellar machines are considered here. Furthermore, writing in the input basement is forbidden, which leads to the normal basement machine. The prohibition of writing in both basements ultimately leads to the finite automaton.

definition

A two-cell machine is a nondeterministic machine that can access two cellars while it is working and receives its input in one of the two cellars. Such an automaton is mathematically described by a seven-tuple . In detail designated thereby ${\displaystyle M}$ ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},\bot ,F,\delta )}$

• ${\displaystyle Q}$ a finite set: the state set
• ${\displaystyle \Sigma }$ a (finite) alphabet, the input alphabet
• ${\displaystyle \Gamma }$another finite alphabet, the working alphabet: and ${\displaystyle \Sigma \subset \Gamma }$ ${\displaystyle \Gamma \cap Q=\emptyset }$
• ${\displaystyle q_{0}}$ the start state with ${\displaystyle q_{0}\in Q}$
• ${\displaystyle F}$ the final states with ${\displaystyle F\subseteq Q}$
• ${\displaystyle \delta }$the total mapping of into the finite subsets of . If the set is always at most one element, the TPDA is called deterministic ; the abbreviation DTPDA has become established here. ${\displaystyle Q\times \Gamma \times \Gamma }$ ${\displaystyle Q\times \Gamma ^{*}\times \Gamma ^{*}}$ ${\displaystyle \delta (q,A,B)}$

Every situation of computing a TPDA is fully described by its configuration: A configuration can be described as a word above the alphabet ; in this case it is common to describe the configurations with the following regular expression: ${\displaystyle Q\cup \Gamma }$

• ${\displaystyle \Gamma ^{*}Q\Gamma ^{*}}$

The first part of the word is in front of the status symbol for the left cellar and the second for the right cellar. The machine reads from right to left in the left basement and from left to right in the right basement. (The status symbol between the two basement contents can be interpreted intuitively as a read / write head.) Therefore, the entry is noted backwards in the start configuration in the left basement:

• ${\displaystyle \bot w_{n}\dotso w_{1}q\bot }$is thus the start configuration .

The transfer function is now applied in the following way:

• If the current configuration of TPDA and true, then provides for each configuration a possible successor configuration of represents. ${\displaystyle \gamma _{0}AqB\gamma _{1}}$ ${\displaystyle \delta (q,A,B)=\{(q_{1},\alpha _{1},\beta _{1}),(q_{2},\alpha _{2},\beta _{2}),\dotsc ,(q_{m},\alpha _{m},\beta _{m})\}}$ ${\displaystyle i\in \{1,2,\dotsc ,m\}}$ ${\displaystyle \gamma _{0}\alpha _{i}q_{i}\beta _{i}\gamma _{1}}$ ${\displaystyle \gamma _{0}AqB\gamma _{1}}$

An input word is from a TPDA accepted if there is a sequence of configurations that is formed by repeatedly applying the transfer function with the property: the last configuration consists of only one character, this character is a final state of . ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle F}$

Occasionally it is also permitted that the cellars need not be empty. The TPDA model is sufficiently robust here.

For the restrictions that are usually considered, the concept of the evaluation function is required: A evaluation function is a monoid homomorphism from the free monoid over into the natural numbers (with 0): ${\displaystyle \Gamma \cup Q}$

${\displaystyle h\colon ((\Gamma \cup Q)^{*},\circ )\rightarrow (\mathbb {N} ,+)}$,

${\displaystyle h(\varepsilon )=0}$

for all the words apply: . ${\displaystyle v,w\in (\Gamma \cup Q)^{*}}$ ${\displaystyle h(v)+h(w)=h(v\circ w)}$

Here denotes the empty word and the concatenation . ${\displaystyle \varepsilon }$ ${\displaystyle \circ }$

• A TPDA is called shrinking if there is an evaluation so that the following applies to the transfer function : If then is . ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},\bot ,F,\delta )}$ ${\displaystyle h}$ ${\displaystyle \delta }$ ${\displaystyle (q',\alpha ,\beta )\in \delta (q,A,B)}$ ${\displaystyle h(q'\circ \alpha \circ \beta )<h(q\circ A\circ B)}$
• A TPDA is called restricted if there is an evaluation so that the following applies to the transfer function : if then is . ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},\bot ,F,\delta )}$ ${\displaystyle h}$ ${\displaystyle \delta }$ ${\displaystyle (q',\alpha ,\beta )\in \delta (q,A,B)}$ ${\displaystyle h(q'\circ \alpha \circ \beta )\leq h(q\circ A\circ B)}$

Characterizations

1. The recursively enumerable languages are characterized by the TPDA model.
2. The recursively enumerable languages ​​are characterized by the DTPDA model.
3. The context-sensitive languages are characterized by restricted TPDA.
4. The deterministic context-sensitive languages are characterized by restricted DTPDA.
5. The increasingly context-sensitive languages are characterized by shrinking TPDA.
6. The Church-Rosser languages are characterized by shrinking DTPDA.
7. The context-free languages are characterized by TPDA, which are only allowed to write in the right cellar.
8. The deterministic context-free languages are characterized by DTPDA, which are only allowed to write in the right cellar.
9. The regular languages are characterized by TPDA, which are not allowed to write in their basements.
10. The regular languages ​​are characterized by DTPDA, which are not allowed to write in their basements.

Views

If we add more basements to the model, the result for the shrinking case is that it accepts the nondeterministic quasi-real-time languages ( ). ${\displaystyle \mathbf {Q} }$

literature

• Gerhard Buntrock, Friedrich Otto: Growing context-sensitive languages ​​and Church-Rosser languages . In Information and Computation , Volume 141, Issue 1, (February 1998), Pages: 1-36
• Gundula Niemann, Friedrich Otto: The Church-Rosser languages ​​are the deterministic variants of the growing context-sensitive languages . In Information and Computation , Volume 197, Issue 1/2 (February 25, 2005 / March 15, 2005), Pages: 1-21
• Elias Dahlhaus, Manfred K Warmuth: Membership for growing context-sensitive grammars is polynomial . In Journal of Computer and System Sciences , Volume 33, Issue 3 (December 1986), Pages: 456-472