Informatik
Informatik

==== Automatentheorie und Formale Sprachen ====
Automaten sind in der Informatik „gedachte Maschinen“, die sich nach bestimmten Regeln verhalten. Ein endlicher Automat hat eine endliche Menge von inneren Zuständen. Er liest ein „Eingabewort“ zeichenweise ein und führt bei jedem Zeichen einen Zustandsübergang durch. Zusätzlich kann er bei jedem Zustandsübergang ein „Ausgabesymbol“ ausgeben. Nach Ende der Eingabe kann der Automat das Eingabewort akzeptieren oder ablehnen.
Der Ansatz der formalen Sprachen hat seinen Ursprung in der Linguistik und eignet sich daher gut zur Beschreibung von Programmiersprachen. Formale Sprachen lassen sich aber auch durch Automatenmodelle beschreiben, da die Menge aller von einem Automaten akzeptierten Wörter als formale Sprache betrachtet werden kann.
Kompliziertere Modelle verfügen über einen Speicher, zum Beispiel Kellerautomaten oder die Turingmaschine, welche gemäß der Church-Turing-These alle durch Menschen berechenbaren Funktionen nachbilden kann.