Definition:
Ein Endlicher Automat enthält ein Alphabet, eine Menge von Zuständen mit Start- und Endzuständen
sowie eine Überführungsfunktion (deterministisch: DEA, nicht-deterministisch: NEA),
die den Automaten auf Grund eines gelesenen Eingabesymbols in einen neuen Zustand bringt.
Wird ein Endzustand erreicht, so hat der Automat die Eingabe akzeptiert.
Algorithmus:
Für das String Matching wird aus dem Muster ein DEA erzeugt,
der als Eingabe den Text erhält. Sobald er den Text akzeptiert, waren die
letzten Eingabezeichen genau das Muster.
Komplexität:
DEA: 
Bemerkungen:
- Primitive Vergleichswörter als Muster ergeben immer einen DEA.
- Endliche Automaten erkennen natürlich beliebige reguläre Ausdrücke und
sind somit wesentlich mächtiger, jedoch für einfaches String Matching
in Textverarbeitungsprogrammen meist zu aufwendig.
Reguläre Ausdrücke:
- DEA schnell, aber exponentieller Speicheraufwand
- NEA mit Backtracking, aber linearer Speicheraufwand
- Compilerbau: Lazy transition evaluation, minimaler DEA aus Syntaxbaum