AUTOMATENTHEORIE  

Teoría de los autómatas

(Recop.) Justo Fernández López

 

Vgl.:

Rekursivität / Algorithmus / Turing Maschine / Formale Sprachen / Finite State Grammar / Informationstheorie / Linguistische Datenverarbeitung

 

Automat [griech. autómatos ‘sich von selbst bewegen’].

Im weiteren Sinn: jede konkrete Maschine, die so konstruiert ist, dass sie bestimmte Funktionen selbständig auszuführen vermag, z. B. Fernsprech-, Zigarettenautomaten oder automatische Uhren.

Im engeren Sinn der Informatik: Mathematisches Modell von konkreten Automaten als informationsverarbeitende Systeme, die Informationen aufnehmen (Input), speichern bzw. verarbeiten und abgeben (Output). In der neueren Sprachwissenschaft spielen A. als analoge Modelle formaler Sprachbeschreibung eine wichtige Rolle. So entsprechen Finite State Grammars „endlichen“ A., kontextfreie Sprachen den sogen. „Kellerautomaten“, während Turing Maschinen die schwache Generative Kapazität von Sprachbeschreibungen zu simulieren vermögen.“ [Bußmann, S. 117]

Automat [automaton / automate]

Automaten sind algorithmische Mechanismen (siehe Algorithmus). Im folgenden seien nur drei Typen von Automaten herausgegriffen. (Bezüglich technischer Details und präziser mathematischer Darstellungen muss auf die bibliographischen Angaben verwiesen werden.)

(a)  Turing-Maschine / Turing machine / machine de Turing:

Nach dem Mathematiker und Logiker Turing benannter infiniter (d. h. mit einem potentiell unendlich großen Gedächtnis ausgezeichneter), für die Explizierung des mathematischen Begriffs der Berechenbarkeit verwendeter Automat, dem Systeme von Ersatzregeln der Form X ® Y entsprechen. Die folgende schematisierte Darstellung kann nur einen ersten Eindruck vom Aufbau und von der Funktionsweise von Turing-Maschinen vermitteln.

 

 

(A):     in Felder mit je einem einzigen Symbol eingeteiltes (Rechen-)Band

(B):     Schaltwerk, das endlich viele innere Zustände (q1, q2, q3, ..., qn) annehmen kann (d.h. Phasen zu einem bestimmten Zeitpunkt)

(C):     Lese- und Schreibkopf zur ‘Kommunikation’ zwischen Schaltwerk (B) und Band (A)

So, S1, S2, ..., Sk: Symbole, die die Maschine liest und schreibt (‘Alphabet’)

So:  Leerzeichen (‘blank’)

Mögliche Operationen des Lese- und Schreibkopfes (C) sind:

1.    Substitution des gelesenen Zeichens durch ein anderes Zeichen:

       (a)            Umschreibung Si > Sj (‘Ersetze Si durch Sj’)

       (b)           Löschung Si >  So (‘Ersetze Si durch das Leerzeichen So’)

2.    Verschiebung des Bandes (um ein Feld) nach links

3.    Verschiebung des Bandes (um ein Feld) nach rechts

4.    Anhalten der Maschine

Nach Gross/Lentin (1971, p. 49) ist eine Turing-Maschine „... eine endliche Menge von Quadrupeln, in der es keine zwei Quadrupel gibt, bei denen die ersten zwei Zeichen gleich sind“.

Die Quadrupel (d.h. geordnete Folgen von je 4 Elementen) stellen die explizit formulierten (und das Abbildungen interpretierbaren) Regeln (Instruktionen) dar, die die Maschine (die ja nicht wie ein Mensch von sich aus entscheidungsfähig ist) mechanisch ausführt. Die jeweilige ‘Reaktion’ der Maschine (d.h. welche der vier oben genannten Operationen sie durchführt) hängt davon ab, welches Symbol Sk sie auf dem Band (A) ‘liest’ und in welchem inneren Zustand q1 sie sich dabei befindet, weil diese Kombination darüber entscheidet, welche Instruktion die Maschine befolgt.

Angenommen, eine Turingmaschine T sei definiert für das Alphabet A = {So, S1. S2} (So sei wieder das Leerzeichen). Die möglichen inneren Zustände von T seien q1, q2, q3, q4, wobei q1 den Anfangszustand markiere. Quadrupel wie

 

(Q1)

qi

Sk

S1

qj

(Q2)

qi

Sk

R

qj

(Q3)

qi

Sk

L

qj

 

besagen folgendes: Die ‘Ausgangsbasis’ ist in den drei Quadrupeltypen dieselbe, nämlich: Die Maschine, die sich im inneren Zustand qi befindet, liest Sk.

Nun gilt

für (Q1):    Sie ersetzt Sk durch S1 und nimmt dann den inneren Zustand qj ein;

für (Q2):   Sie verschiebt das Band (A) mit Sk um ein Feld nach rechts (R) und  nimmt den Zustand qj an.

für (Q3):   Sie verschiebt das Band (A) um ein Feld nach links (L) und geht dabei von qi in den Zustand qj über.

Unter der Annahme, die für unsere (fiktive) Maschine T geltenden ‘Quadrupel-Regeln’ seien:

 

(1)

qi

S1

So

q1

(2)

qi

So

L

q2

(3)

q2

S2

L

q3

(4)

q3

So

L

q4

(5)

q4

S1

So

q4

 

können wir die Sukzession der Arbeitstakte von T folgendermaßen darstellen, wenn auf dem Band etwa die Zeichenkette S1S2SoS1  stehe:

 

q1S1S2SoS1

d.h. T beginnt mit dem Anfangszustand q1 und liest das erste Zeichen der Kette.

Nun muss T den Befehl (1) befolgen und es ergibt sich:

q1SoS2SoS1

Das Verfahren wird nun analog fortgesetzt; die jeweils befolgten Anweisungen sind in Klammern angegeben.

Soq2S2SoS1

(2)

SoS2q3SoS1

(3)

SoS2Soq4S1

(4)

SoS2Soq4So

(5)

 

Da für den Fall, dass die Maschine sich in q4 befindet und So liest, keine Regel (in Form eines Quadrupel) vorgesehen ist, bleibt sie nun stehen. (Cf. H. J. Heringer, Formale Logik und Grammatik, (Tübingen, 1972), pp. 39-41).

b)   Kellerautomat / pushdown storage automaton / automate à pile de mémoire:

       Automat, der – wie Chomsky nachgewiesen hat – in seiner generativen Kapazität einem System kontextfreier Phrasenstrukturregeln äquivalent ist.

c)    Automat (Grammatik) mit endlich vielen Zuständen / finite state automaton (grammar) /

       automate (grammaire) à états finis.“

        [Welte, Werner: Moderne Linguistik. Terminologie / Bibliographie. München: Hueber, 1974, Bd. 1, S. 78-80]

Siehe auch unter: Finite State Grammar / Gramática de estados finitos

Autómata:

(1)  Máquina que imita la figura y los movimientos humanos.

(2)  En informática, dispositivo que procesa una información de entrada para producir otra de salida.

(3)  fam Persona que actúa maquinalmente o dirigida por otra.

Sinónimo: Robot.

Familia de palabras: Automación, automático.“

[Diccionario esencial Santillana de la lengua española. Madrid: Santillana, 1971, p. 109]