Two-Stack Push Down Automaton

The term two- pushdown automaton ( TPDA -. Engl two- stack pushdown automaton ) is in theoretical computer science for a particular machine model. He has especially gained a special significance for a uniform representation of automata characterizations of language classes of the Chomsky hierarchy and other classes.

Thus, the classical concepts Turing machine, linear bounded automaton, pushdown automaton and finite state machine can be represented uniformly with special restrictions.

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

In the literature, two different models are considered:

In both cases it follows that the two- pushdown automaton without further restriction is already Turing powerful. In the first case, above all, the machine has been studied using real -time input. This input corresponds to the normal pushdown automata, which uses only a cellar. In the second case, various constraints have been defined, which can be characterized consistently different language classes.

So here was limited and shrinking two- pushdown automata are considered. Furthermore, it prohibits the letter in the input basement that leads to the normal pushdown automata. The prohibition of writing in two basements eventually leads to finite automata.

Definition

A two- pushdown automaton is a nondeterministic machine that can access while working on two basement storage and receives its input in one of the two stack. Is described mathematically by a Siebentupel such a machine. Specifically designates

  • A finite set: the set of states
  • A ( finite ) alphabet, the input alphabet
  • Another finite alphabet, the working alphabet: and
  • The initial state with
  • The final states with
  • The total mapping of the finite subsets of. If the amount is always at most a singleton, ie, the TPDA deterministic; here the abbreviation DTPDA has naturalized.

Each situation a calculation of a TPDA is completely described by its configuration: A configuration can be described as a word over the alphabet; in this case it is customary to describe the configurations of the following regular expression:

Here is the first part of the word before the state symbol for the left basement and the second for the right cellar. Reads the machine basement in the left from the right to the left and the right from the left to the right. ( The Zustandssysmbol between the two basement contents may be intuitively interpreted as a read-write head here.) Therefore, the input is in the startup configuration in the left basement backwards noted:

  • Is thus the startup configuration.

The transfer function is now applied in the following manner:

  • If the current configuration of the TPDA is and is, then provides for each configuration a possible successor configuration of dar.

An input word is accepted by a TPDA if there is a sequence of configurations formed by repeatedly applying the transition function, with the property: the last configuration consists of only one character, the character is a final state of.

It is sometimes also allows the basement does not have to be empty. The TPDA model is sufficiently robust here.

For the restrictions that are usually considered, the concept of the evaluation function is needed: An evaluation function is a monoid homomorphism from the free monoid over the natural numbers ( with 0):

Here, the empty word and the concatenation.

  • A TPDA ie declining if there is a vote so that the transfer function is: if then.
  • A TPDA is called bounded if there is a vote so that the transfer function is: if then.

Characterizations

Views

If we add more storage in the model, the result for the shrinking case he accepts the non-deterministic quasi- real-time languages ​​().

Finite-state machine Empty string
838133
de