Mathematisches Berechnungsmodell, bestehend aus einer endlichen Menge von Zuständen, einem Eingabealphabet, Übergangsrelationen, einem Startzustand und einem oder mehreren akzeptierenden Zuständen; verwendet zur Erkennung regulärer Sprachen. Varianten umfassen deterministische (DFA) und nichtdeterministische endliche Automaten (NFA).

Prinzip

Die Berechnung schreitet voran, indem ein Eingabesymbol gelesen und entsprechend den Übergangsregeln zwischen Zuständen gewechselt wird; Akzeptanz wird dadurch bestimmt, ob nach dem Verbrauch der Eingabe ein akzeptierender Zustand erreicht wurde. Nichtdeterminismus erlaubt mehrere mögliche Übergänge; Determinismus genau einen pro Zustand-Symbol-Paar.

Demonstration

Ein Lexikalischer Analysator, aus regulären Ausdrücken kompiliert, wird als DFA implementiert, der Quelltext von links nach rechts scannt; Zustandsübergänge kodieren reguläre Muster für Schlüsselwörter, Bezeichner und Literale, sodass Tokens in linearer Zeit mit begrenztem Speicher erkannt werden.

Fehlanwendung

Zu versuchen, einen endlichen Automaten zur Analyse verschachtelter oder kontextfreier Strukturen (z. B. beliebig tiefe ausbalancierte Klammern) zu verwenden, die unbegrenzten Speicher (z. B. einen Stack) erfordern; dies führt zu falscher oder unvollständiger Erkennung.

Konsequenz

Effiziente, lineare Erkennung regulärer Muster mit festem, geringem Speicheraufwand; ermöglicht die Kompilierung regulärer Ausdrücke in kompakte Übergangstabellen und bildet die Grundlage vieler Textverarbeitungs- und Hardwaresteuerungsanwendungen.

Umkehrung

Ein Kellerautomat (Pushdown-Automat) oder eine Turingmaschine, die den Zustand um unbegrenzten Speicher (Stack oder Band) erweitern, um kontextfreie oder Turing-vollständige Sprachen zu erkennen, jedoch mit komplexerem Kontroll- und Ressourcenverbrauch.

Abgrenzung

Charakterisiert genau die regulären Sprachen; kann keine nicht-regulären Sprachen erkennen, die unbegrenzten Speicher erfordern. DFA und NFA sind in Ausdrucksstärke äquivalent, unterscheiden sich jedoch in Kürze und Implementierungsabwägungen.

Semantische Spannung

Endlicher Automat versus regulärer Ausdruck: beide definieren dieselbe Sprachklasse, unterscheiden sich jedoch zwischen einer operationalen Zustandsmaschinenansicht und einer deklarativen Musterbeschreibung; das wirkt sich auf Konstruktion und Optimierung aus.

Synthese

Eine endliche Steuerung, die Eingabesymbole durch Zustandsübergänge verarbeitet und so einen kompakten, effizienten Mechanismus zur exakten Erkennung regulärer Sprachen bereitstellt; ihr begrenzter Speicher (endliche Zustände) ist zugleich Einschränkung und Nutzen.