Endliche Automaten werden durch Zustandsübergangsdiagramme dargestellt. Diese bestehen aus Knoten (Zuständen) und gerichteten Kanten (Übergängen), die mit Zeichen beschriftet sind. Sie haben immer genau einen Startzustand, können aber mehrere Endzustände haben.
Zur Abarbeitung einer Eingabekette wird ein Zeichen nach dem anderen eingelesen. Wenn das letzte Zeichen konsumiert wurde und sich der Automat in einem Endzustand befindet, so hat er die Eingabe akzeptiert.
In Prolog wird ein solcher Automat mittels start/1-, final/1- und delta/3-Fakten programmiert. Die Abarbeitung der Eingabeketten erfolgt über ein rekursives Listenprädikat.
Die Sprache, die von Endlichen Automaten akzeptiert wird, kann durch Reguläre Ausdrücke dargestellt werden.