AUTOMATENTHEORIE Teoría de los autómatas

AUTOMATENTHEORIE Teoría de los autómatas

(comp.) Justo Fernández López

Diccionario de lingüística español y alemán

www.hispanoteca.eu

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]

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.)

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.

(B): Schaltwerk, das endlich viele innere Zustände (q₁, q₂, q₃, ..., q_n) annehmen kann (d.h. Phasen zu einem bestimmten Zeitpunkt)

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

S_o, S₁, S₂, ..., S_k: Symbole, die die Maschine liest und schreibt (‘Alphabet’)

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 S_k sie auf dem Band (A) ‘liest’ und in welchem inneren Zustand q₁ 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 = {S_o, S₁. S₂} (S_o sei wieder das Leerzeichen). Die möglichen inneren Zustände von T seien q₁, q₂, q₃, q₄, wobei q₁ den Anfangszustand markiere. Quadrupel wie

(Q1)	q_i	S_k	S₁	q_j
(Q2)	q_i	S_k	R	q_j
(Q3)	q_i	S_k	L	q_j

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

für (Q1): Sie ersetzt S_k durch S₁ und nimmt dann den inneren Zustand q_j ein;

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

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

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

(1)	q_i	S₁	S_o	q₁
(2)	q_i	S_o	L	q₂
(3)	q₂	S₂	L	q₃
(4)	q₃	S_o	L	q₄
(5)	q₄	S₁	S_o	q₄

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

q₁S₁S₂S_oS₁	d.h. T beginnt mit dem Anfangszustand q₁ und liest das erste Zeichen der Kette. Nun muss T den Befehl (1) befolgen und es ergibt sich:
q₁S_oS₂S_oS₁	Das Verfahren wird nun analog fortgesetzt; die jeweils befolgten Anweisungen sind in Klammern angegeben.
S_oq₂S₂S_oS₁	(2)
S_oS₂q₃S_oS₁	(3)
S_oS₂S_oq₄S₁	(4)
S_oS₂S_oq₄S_o	(5)

Da für den Fall, dass die Maschine sich in q₄ befindet und S_o 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) /

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

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

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