Theorie: FSA
Finite State Automaton

Reguläre Sprachen lassen sich durch FSA (endliche Automaten) beschreiben. Beim FSA handelt es sich um ein sehr einfaches Modell für informationsverarbeitende Maschinen ohne Speicher. Man kann sich dabei ein FSA als eine Maschine mit folgenden Komponenten vorstellen:

Ein Eingabeband, das in einzelne Felder unterteilt ist. Jedes dieser Felder kann mit einem Eingabezeichen (input alphabet) beschriftet sein, oder es kann leer sein.
Eine Kontrolleinheit, die unterschiedliche interne Zustände annehmen kann und die mit einem Lesekopf jeweils den Inhalt eines einzelnen Feldes des Eingabebandes lesen kann.

Graphisch sieht ein FSA somit folgendermassen aus (nach [Stu95], S.50) :


Formal wird ein FSA als Quintupel (S,I,S0,F,T) definiert , wobei

 S = endliche Menge von Zuständen (States)
 I = Eingabealphabet (input alphabet)
 S0= Startzustand (Initial state)
 F = Endzustand (final state), wobei F Teil der Menge S ist
 T = Zustandsübergangsfunktion (transition function): Zustand x Eingabe U {e} -> (neuer) Zustand  (U = vereinigt; {e} = Leerheitssymbol, Epsilon)

Im JFLAP werden die Zustände mit q0, ......qn bezeichnet.

Der FSA lässt sich mit Transitionsgraphen (transition graphs) und Zuständen graphisch als Zustandsdiagramm (transition graphs) darstellen. Beispiel:

Die Zustandsübergangsfunktion T lautet für diesen Automaten:
(q0, a) -> q1
(q1, b) -> q2
(q2, c) -> q3

Dieser FSA entspricht folgender regulären Grammatik:
A -> a B
B -> b C
C -> c

Die Nichterminale bilden dabei die Zustände q<n>, die Terminalsymbole entsprechen den Übergangsfunktionen. Der Startzustand wird mit q0 bezeichnet.

Man unterscheidet zwischen deterministischem und nicht-deterministischem FSA (DFA, bzw. NFA genannt). Diese Unterscheidung ist auch als endlicher, bzw. nicht-endlicher FSA bekannt.