Die Automatentheorie ist ein Teilgebiet der Theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen Automaten lösbaren Problemen beschäftigt. Sie ist ein wichtiges Werkzeug der Berechenbarkeitstheorie und Komplexitätstheorie. Praktische Anwendung findet sie beim Entwurf von lexikalischen Scannern und Parsern im Compilerbau, sowie für den Entwurf von Programmiersprachen. Die Automatentheorie befasst sich mit formalen Sprachen und formalen Grammatiken, die u.a. durch die Chomsky-Hierarchie typisiert werden, und mit Modellen für Automaten, die solche Sprachen verarbeiten können, insbesondere endliche Automaten, Kellerautomaten, Zellularautomaten und Turingmaschinen.
Sprache des Automaten
Gelangt der Automat in den Akzeptierzustand, so wird die dazu notwendige Eingabefolge als ein Wort des Automaten bezeichnet. Die Menge aller akzeptierten Eingabefolgen, die man Wörter nennt, bezeichnet man als Sprache des Automaten L(A).
Die Sprache eines Automaten L(A) ist die Menge aller von ihm akzeptierten Wörter über dem Eingabealphabet X.
L(A) = {w | w ? X* und d*(w, z0) ? ZE}, wobei gilt:
w ist ein Eingabewort über dem Alphabet X,
d* ist eine Folge von Überführungsfunktionen, die beginnend im Startzustand z0 mit dem Eingabewort w den Automaten in einen Endzustand überführen.
Quelle: http://tinohempel.de/info/info/ti/akzeptor.htm