Endlicher Automat

Ein fröhlicher endlicher Automat, der den regulären Ausdruck L(OL)+ erkennt.

Ein endlicher Automat ist ein theoretisches Rechnermodell, mit dem überprüft werden kann, ob ein Wort zu einer formalen Sprache gehört. Hierbei gilt: Alles, was durch einen regulären Ausdruck ausgedrückt werden kann, kann durch einen endlichen Automaten überprüft werden.

Grundsätzlich besteht ein Automat aus Zuständen und Übergängen, die in Form eines gerichteten Graphen notiert werden. Die Zustände sind dabei die Knoten des Graphen und werden als beschriftete Kreise notiert. Üblicherweise werden die Zustände mit dem Buchstaben $q$ bezeichnet und fortlaufend nummeriert: $q_{0},q_{1},q_{2}\dots$. Die Übergänge sind die Kanten des Graphen und werden als Pfeile eingezeichnet, wobei jeder Übergang mit einem Buchstaben aus dem Alphabet der Sprache beschriftet ist.

Einer der Zustände ist der Startzustand und wird mit einer entsprechenden Beschriftung markiert. Üblicherweise nennt man diesen Zustand $q_{0}$. Beliebig viele Zustände dürfen Endzustände sein und werden mit einer doppelten Umrandung gekennzeichnet.

Akzeptieren eines Wortes

In einen solchen Automaten kann man nun ein Wort hineinfüttern und prüfen, ob dieses Wort zu der Sprache gehört, die der Automat beschreibt. Dabei beginnt man am Startzustand, schaut sich das Wort Buchstabe für Buchstabe an und folgt jeweils dem Übergang, der mit diesem Buchstaben beschriftet ist. Wenn man am Ende des Wortes in einem Endzustand gelandet ist, akzeptiert der Automat das Wort. Dieses Wort gehört somit zu der Sprache, die der Automat beschreibt. Man sagt acuh: Der Automat erkennt diese Sprache.

💬

Beispiel

Betrachten wir den Automaten vom Anfang der Seite und prüfen die Wörter LO und LOL.

Überprüfung des Wortes LO

	LO Von Nach L $q_{0}$ $q_{1}$	Schritt 1: Wir lesen den Buchstaben L und gehen von $q_{0}$ nach $q_{1}$.
	LO Von Nach L $q_{0}$ $q_{1}$ O $q_{1}$ $q_{2}$	Schritt 2: Wir lesen den Buchstaben O und gehen von $q_{1}$ nach $q_{2}$.

Damit haben wir das Wort vollständig abgearbeitet. Unser Weg durch den Automaten endet im Zustand $q_{2}$, der kein Endzustand ist. Das Wort LO wird also nicht vom Automaten akzeptiert.

Überprüfung des Wortes LOL

	LOL Von Nach L $q_{0}$ $q_{1}$	Schritt 1: Wir lesen den Buchstaben L und gehen von $q_{0}$ nach $q_{1}$.
	LOL Von Nach L $q_{0}$ $q_{1}$ O $q_{1}$ $q_{2}$	Schritt 2: Wir lesen den Buchstaben O und gehen von $q_{1}$ nach $q_{2}$.
	LOL Von Nach L $q_{0}$ $q_{1}$ O $q_{1}$ $q_{2}$ L $q_{2}$ $q_{3}$	Schritt 3: Wir lesen den Buchstaben L und gehen von $q_{2}$ nach $q_{3}$.

Damit haben wir das Wort vollständig abgearbeitet. Unser Weg durch den Automaten endet im Zustand $q_{3}$, der ein Endzustand ist. Das Wort LOL wird also vom Automaten akzeptiert.

Der Automat erkennt die Sprache, die alle Wörter enthält, die mit LOL beginnen und danach beliebig viele (oder auch gar kein) OL enthalten.

Zum Weiterlesen

• "Sprachen und Automaten" auf inf-schule.de 🇩🇪