Basement machine

A pushdown automaton ( KA , also PDA for English p USH d own a utomaton ; and stack machine ) is a machine in accordance with the theoretical computer science to certain properties of a construct that is used problems and algorithms to analyze and to prove .

The basement machine is a finite machine that has been expanded to include a storage system (ag stack). A cellar machine with two cellar stores is equal to the Turing machine .

functionality

Basement machine

A push-down machine is used to clarify whether an input (i.e. a word of zero, one or more characters) belongs to a certain formal language (i.e. a set of words). To do this, the machine processes the input word step by step from left to right and can assume a number of states. At the beginning it is in the so-called start state. Typically, a character is read from the input in each processing step. In addition, the top character is read from the cellar in each processing step , i.e. H. away. Depending on the current status, the input character just read and the cellar character that has just been read, the machine changes to a new state and stores a new word in the cellar instead of the cellar character that was removed. If the entire input has been read and the basement is empty, the input belongs to the language recognized by the machine.

In general, however, several deviations from the above explanation are possible:

The recognized language can also be defined as the set of words, the processing of which the basement machine reaches a so-called final state - regardless of whether the basement is emptied.

A character does not have to be read from the input in every processing step. If none was read, the word read is said to be (the empty word ). ${\ displaystyle \ varepsilon}$

For some combinations of status, input characters (or ) and push-down characters, the push-down machine can have the choice between several transitions (i.e. combinations of subsequent status and push-down word). In this case, the entry is considered recognized when the basement can be emptied or a final state can be reached . ${\ displaystyle \ varepsilon}$

example

In order to clarify the principle of a push-button automaton, the syntactic examination of bracketed expressions is often used. For example, in an expression of a certain language, there must also be a closing bracket for each opening bracket:

Example: {… {…}…}

The machine begins in a starting state z0 ; in the basement there is a character that marks the end ( # ). When processing the printout, the reading head moves on character by character. If he comes across an opening bracket, it is written in the cellar. If a closing bracket appears in the further processing, the uppermost bracket-open sign in the basement is deleted again. The printout is then successfully processed when the read head has reached the end of the input tape and only the # character is in the cellar . On the other hand, if there were still open brackets in the basement after the expression has been processed, this would mean that a closing bracket is missing and there is a syntactic error. An error has also occurred if the end of the basement is reached before the entry has been completely processed. In this case there are too many closing brackets in the input.

Formal definition

A nondeterministic pushdown automaton (NKA) is defined as a 7- tuple , where ${\ displaystyle M = (Z, \ Sigma, \ Gamma, \ delta, z_ {0}, \ #, F)}$

{\ displaystyle Z \,}

a finite set of states,

{\ displaystyle \ Sigma \,}

an input alphabet ,

{\ displaystyle \ Gamma \,}

the basement alphabet,

${\ displaystyle \ delta \,}$ the state transition function, which only maps to finite subsets of , ${\ displaystyle \ delta \ colon Z \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma \ rightarrow {\ mathcal {P}} (Z \ times \ Gamma ^ {*})}$ ${\ displaystyle Z \ times \ Gamma ^ {*}}$

{\ displaystyle z_ {0} \ in Z}

the start state,

{\ displaystyle \ # \ in \ Gamma}

the start symbol in the basement and

{\ displaystyle F \ subseteq Z}

a lot of end states

is.

It denotes the empty word and the set of words in the alphabet . ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ Gamma ^ {*}}$ ${\ displaystyle \ Gamma}$

Sometimes you also find push-down automata as 6- tuples , in this case there are no final states and the push-down automaton accepts a word if the cellar is empty after processing the word. ${\ displaystyle M = (Z, \ Sigma, \ Gamma, \ delta, z_ {0}, \ #)}$

If the transition function fulfills the property , one speaks of a deterministic push-down automaton. There is then at most one state transition sequence for a fixed input, so ambiguities cannot arise. ${\ displaystyle \ forall z \ in Z, \ forall a \ in \ Sigma, \ forall g \ in \ Gamma, \ left | \ delta (z, a, g) \ right | + \ left | \ delta (z, \ varepsilon, g) \ right | \ leq 1}$

Remarks

For a nondeterministic push-down automaton, it is possible to omit the set of final states in the definition. Instead, one defines that the nondeterministic push-down automaton accepts its input if there is a computation path in which the push-down contains the empty word after reading the input. The two definitions are equivalent in terms of the languages accepted. For a deterministic push-down automaton, however, this statement is generally incorrect. The deterministic push-down automaton, which accepts via end states, is more powerful.

This means that a deterministic push-down automaton can terminate as soon as a final state has been reached, but does not have to terminate immediately. The cellar does not matter. It accepts a word if it terminates and the input word is empty. If it is not empty and there are no more rules applicable, it has not been accepted.

For such a non-deterministic push-down automaton that accepts when the basement is empty, it is possible to construct an equivalent push-down automaton with a single state by completely simulating the states of the old push-down automaton in the cellar of the new push-down automaton. In the definition of a nondeterministic push-down automaton, in addition to the set of end states, the start state and the set of states can also be dispensed with.

Transitions can be dispensed with in the definition of a nondeterministic push-down automaton . The state transition function is then an element off . With the help of the Greibach normal form one shows that for every nondeterministic push-down automaton there is an equivalent nondeterministic push-down automaton without transitions. ${\ displaystyle \ varepsilon}$ ${\ displaystyle (Z \ times \ Sigma \ times \ Gamma) \ to {\ mathcal {P}} (Z \ times \ Gamma ^ {*})}$ ${\ displaystyle \ varepsilon}$

Accepted language

The set of configurations of a push-down automaton is . One element of this set consists of ${\ displaystyle K = Z \ times \ Sigma ^ {*} \ times \ Gamma ^ {*}}$ ${\ displaystyle (z, \ alpha, \ gamma) \ in K}$

the current state , ${\ displaystyle z}$
the word still to be read as well ${\ displaystyle \ alpha}$
the basement . ${\ displaystyle \ gamma}$

A relation is defined on which then determines which words will be accepted. It is ${\ displaystyle K}$ ${\ displaystyle {\ rightsquigarrow} \ subseteq K \ times K}$

{\ displaystyle {\ begin {aligned} {\ rightsquigarrow}: = & \ \ {((z, a \ alpha, g \ gamma), (z ', \ alpha, \ gamma' \ gamma)) \ mid z \ in Z, a \ in \ Sigma, \ alpha \ in \ Sigma ^ {*}, g \ in \ Gamma, \ gamma, \ gamma '\ in \ Gamma ^ {*}, (z', \ gamma ') \ in \ delta (z, a, g) \} \\\ cup & \ \ {((z, \ alpha, g \ gamma), (z ', \ alpha, \ gamma' \ gamma)) \ mid z \ in Z, \ alpha \ in \ Sigma ^ {*}, g \ in \ Gamma, \ gamma, \ gamma '\ in \ Gamma ^ {*}, (z', \ gamma ') \ in \ delta (z, \ varepsilon, g) \}. \ end {aligned}}}

For machines whose final state sets are to decide on acceptance, it then says:

{\ displaystyle \ alpha \ in \ Sigma ^ {*}}

is accepted by and only if there is and such that .

{\ displaystyle M}

{\ displaystyle f \ in F}

{\ displaystyle \ gamma \ in \ Gamma ^ {*}}

{\ displaystyle (z_ {0}, \ alpha, \ #) \ rightsquigarrow ^ {*} (f, \ varepsilon, \ gamma)}

For machines, on the other hand, where the acceptance depends on whether the basement is empty, the formulation is:

{\ displaystyle \ alpha \ in \ Sigma ^ {*}}

is accepted by and only if there is such a or .

{\ displaystyle M}

{\ displaystyle z \ in Z}

{\ displaystyle (z_ {0}, \ alpha, \ #) \ rightsquigarrow ^ {*} (z, \ varepsilon, \ varepsilon)}

{\ displaystyle (z_ {0}, \ alpha, \ #) \ rightsquigarrow ^ {*} (z, \ varepsilon, \ #)}

It is the reflexive and transitive shell of . ${\ displaystyle \ rightsquigarrow ^ {*}}$ ${\ displaystyle \ rightsquigarrow}$

example

The following push-down automaton M is deterministic and recognizes the context-free language : ${\ displaystyle L = \ {a ^ {n} \, b ^ {n} \, | \, n> 0 \}}$

${\ displaystyle M = (Z, \ Sigma, \ Gamma, \ delta, z_ {0}, \ #, F)}$

${\ displaystyle Z = \ left \ {{z_ {0}}, {z_ {1}}, {z_ {2}} \ right \}}$
${\ displaystyle \ Sigma = \ left \ {a, b \ right \}}$
${\ displaystyle \ Gamma = \ left \ {\ #, a \ right \}}$
${\ displaystyle F = \ left \ {{z_ {2}} \ right \}}$

Definition of δ
parameter			Function value
Status	input	basement, cellar	Status	basement, cellar
z ₀	a	#	z ₀	a #	(1)
z ₀	a	a	z ₀	aa	(2)
z ₀	b	a	z ₁	ε	(3)
z ₁	b	a	z ₁	ε	(4)
z ₁	ε	#	z ₂	ε	(5)

Example push-down machine

(1), (2) In the state z ₀ , the leading a characters of the input are read and stored in the cellar.

(3) If you enter b and an a as the top cellar element, the state changes from z ₀ to z ₁ . Adjustment takes place in the basement. (Adjustment means "deleting" the top stack element or stack "pop")

(4) All other b characters are read, provided there are still enough a characters stored in the basement. The basement is leveled.

(5) If only the start symbol is in the basement and no entry is made, the basement automaton changes to the final state z ₂ and thus accepts the entry. ${\ displaystyle \ # \,}$

For example, if the push-button machine receives the input aabb , it runs through the following configurations:

(the superscript number on the arrow indicates the state transition function used)

(z ₀ , aabb, #) ⇝ ⁽¹⁾ (z ₀ , abb, a #) ⇝ ⁽²⁾ (z ₀ , bb, aa #) ⇝ ⁽³⁾ (z ₁ , b, a #) ⇝ ⁽⁴⁾ ( z ₁ , ε, #) ⇝ ⁽⁵⁾ (z ₂ , ε, ε)

Basically, this basement machine M cannot write again once it has started to read the basement. Therefore, the recognized language is in particular a linear language .

Push-down automata and formal languages

A (basement) machine reads an input consisting of individual characters and accepts (or recognizes) it - or not. The set of accepted inputs forms the language defined by the machine .

The nondeterministic pushdown automaton recognizes the context-free languages exactly (type 2, cf. Chomsky hierarchy ). It is therefore more powerful than finite automata , which precisely recognize the regular languages (type 3), but less powerful than Turing machines , which precisely recognize the recursively enumerable languages (type 0). A deterministic push-down machine (DPDA) recognizes the deterministic context-free languages , i.e. only a real subset of the context-free languages.

The importance of the push-down automaton arises from the fact that knowledge about it (e.g. equivalence with other automatons) can be transferred to context-free languages (and vice versa).

Practical implementation of a push-button machine

The following parser (implemented in C ) is given as a practical application example of a push-down automaton , which parses a language consisting of pairs of brackets and checks it for correctness. The term () ((() () )) would be accepted, for example, wrong, however, would be (() ())) , since a closing parenthesis is given too much.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define POP -1
#define ACCEPT -2
#define ERROR -3

#define ALPHABET 3 /* Größe des Eingabealphabets */

#define MAX_LEN 80
/*
 Ein einfacher Kellerautomat ("pushdown automaton")

 Symbol   | (       | )      | \0
 ---------+---------+--------+-----------
 State 0  | PUSH 1  | ERROR  | ACCEPT
 State 1  | PUSH 1  | POP    | ERROR
*/

int states[2][ALPHABET*2] =
{
   {
      '(', 1 /* PUSH 1 */,
      ')', ERROR,
      '\0', ACCEPT
   },
   {
      '(', 1 /* PUSH 1 */,
      ')', POP,
      '\0', ERROR
   }
};


int main( int argc, char** argv )
{
   int stack[100] = { 0 };
   int i  = 0;
   int action  = 0;
   int* tos  = stack;
   char s  [MAX_LEN+1];
   char* p  = s;

   /* Eingabe-Zeichenkette */
   printf("Bitte Ausdruck eingeben: ");
   fgets(s, sizeof(s), stdin);
   s[strlen(s)-1]='\0'; /* Zeilenvorschub (NL) von fgets() durch binäre Null ersetzen */


   /* Startzustand auf Stack ("push") */
   *(tos++) = 0;

   /* Ausführungsschleife */
   do
   {
      /* Aktion auf Basis des Eingabesymbols ermitteln */
      action = ERROR;
      for( i = 0; i < ALPHABET; ++i )
      {
         if( states[*(tos-1)][i*2] == *p )
         {
            action = states[*(tos-1)][i*2+1];
            break;
         }
      }

      /* Ausführen der Aktionen */
      if( action == ERROR )
      {
         printf("Unerwartetes Zeichen an Position %d\n", p-s);
         break;
      }
      else if( action == ACCEPT )
         printf("Ausdruck akzeptiert!\n");
      else if( action == POP )
         --tos;
      else
         *(tos++) = action;

      /* Eingabe erweitern... */
      ++p;
   }
   while( action != ACCEPT );

   return 0;
}

Applications in technology and science

The floating point unit (Engl. Floating Point Unit , FPU) of the Intel 32-bit x86 architecture originally as a pushdown automaton (Engl. Stack Machine ) realized. Your stack has a depth of 8 memory locations (each for an 80-bit floating point value). In view of the restrictions imposed by the basement model, however, there is a tendency to discern that in the future, as is common in other computer architectures, processing units with directly addressable registers will also be used in the PC ( SIMD extension).

Compilers or interpreters of programming languages can be developed with the help of push-down automata. The push-down machine is used for the syntax analysis, i.e. it checks the syntactic correctness of a token sequence .

Web links

Wiktionary: push-button machine - explanations of meanings, word origins, synonyms, translations

Basement machine

contents

functionality

example

Formal definition

Remarks

Accepted language

example

Push-down automata and formal languages

Practical implementation of a push-button machine

Applications in technology and science

See also

Web links