Endliche Automaten

By | 11. März 2017

Ein endlicher Automat (englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.
Ein Automat heißt endlich, wenn die Menge der Zustände, die er annehmen kann (später S genannt), endlich ist. Ein endlicher Automat ist ein Spezialfall aus der Menge der Automaten.

Ein Zustandsübergang zeigt eine Änderung des Zustandes des EA und wird durch logische Bedingungen beschrieben, die erfüllt sein müssen, um den Übergang zu ermöglichen.

Ein endlicher Automat kann über eine Zustandstabelle beschrieben werden. Wobei die möglichen Eingabe-Werte mit den möglichen Zuständen in Relation gesetzt werden.

Der Vorteil einer Zustandstabelle ist ihre leichte Übertragbarkeit in eine Programmiersprache.

Endliche Automaten entsprechen regulären Sprachen, diese wiederum werden durch reguläre Ausdrücke oder auch reguläre Grammatiken beschrieben.

Formale Sprachen und reguläre Ausdrücke

Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu konkreten Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die mathematische Verwendung.

Eine formale Sprache besteht aus einer bestimmten Menge von Zeichenketten („Worte“ der Sprache), die aus einem Zeichenvorrat („Alphabet“, Grundsymbole) zusammengesetzt werden können.

∑ = { Menge von Symbolen}  ∑* = {Menge aller Möglichen Kombinationen der Symbole}

∑ = {a,b}   ∑* ={a, ab, b, ba}

∑ ={a,b,1}  ∑*={a, b, 1, ab, a1, ba, b1, 1a, 1b, ab1, a1b, ba1, b1a, 1ab, 1ba}

∑= {<,M,L,R,0,1,2,3,4,5,6,7,8,9,>}  ∑*={ … über 500 000 mögliche Worte…}

∑= {+,.,/,0,1,2,3,4,5,6,7,8,9}    ∑*={ … über 500 000 mögliche Worte….}

  • Reguläre Ausdrücke beschreiben eine Familie von formalen Sprachen und gehören damit zur theoretischen Informatik.
  • Diese Sprachen, die regulären Sprachen, befinden sich auf der untersten und somit ausdrucksschwächsten Stufe der Chomsky-Hierarchie (Typ 3).
  • Sie werden erzeugt durch reguläre Grammatiken.
  • Ein regulärer Ausdruck besteht aus den Zeichen des zugrunde liegenden Alphabets in Kombination mit den Metazeichen:
    [ ] ( ) { } | ? + – * ^ $

Eine reguläre Sprache kann man statt durch einen regulären Ausdruck auch durch eine reguläre Grammatik beschreiben.

Das Alphabet sei {a, b}, die Sprache sei durch ab(bb)*a beschrieben.

Die Sprache ist demnach {aba, abbba, abbbbba…}, jedes Wort besteht aus einem a und danach einer ungeraden Zahl an b’s, gefolgt von einem schließenden a.

Beispiel: Telefon Nummern Prüfer

Um die oben beschriebenen Konzepte zu veranschaulichen sollen im folgenden der reguläre Ausdruck für eine Telefon-Nummern Überprüfung entwickelt werden.

Unsere Telefon-Nummer sollen der folgenden Beschreibung entsprechen:

Jede unserer Telefon-Nummern soll mit einer 0 starten, gefolgt von einer beliebigen Ziffer 1..9 dann ein “/” gefolgt von einer beliebigen Ziffer 1..9 der dann beliebig viele Ziffern von 0 …9 folgen dürfen. Der entsprechende reguläre Ausdruck sieht so aus:

0([1-9][0-9]+)\/[1-9][0-9]*

Auf internationale Kennzeichen wie +49 etc. ist hier im Beispiel bewusst verzichtet worden, wäre aber leicht herzustellen:

(\+|0)([1-9][0-9]+)\/[1-9][0-9]*

Ein entsprechenderes Syntax-Diagramm für den ersten regulären Ausdruck sieht so aus:

Aus diesem lässt sich nun leicht ein endlicher Automat ableiten:

Dieser Automat wird nun in eine Zustandstabelle überführt. Wobei man sich eine 2-dimensionale Datenstruktur für die Zustandstabelle vorstellt, in der

  • Zeilen = Eingabe-Möglichkeiten
  • Spalten = Möglichen Zustände

darstellen. Wie diese dann entsprechend der gewünschten Programmiersprache zu implementieren ist, wird nachfolgend am Beispiel von C-Code für den Arduino vorgestellt.

Da dargestellte Programm implementiert den regulären Ausdruck zum überprüfen von Telephonnummern.

Auf Basis der vorgestellten Mechanismen lassen sich natürlich auch wesentlich komplexere Analyse-Aufgaben durchführen, da es die Grundprinzipien der lexikalischen Analyse darstellt.