Jede durch einen endlichen Automaten erkennbare Sprache ist regulär
Zu jedem endlichen Automaten kann man eine Grammatik finden, aber man findet nicht immer einen endlichen Automaten zu einer Grammatik. Probleme treten meistens dann auf, wenn man eine Grammatik hat, die beliebig lange Wörter erzeugt, bei denen der Automat sich die Häufigkeit einzelner Elemente merken müsste. (z.B S  a S b | ab) Er bräuchte dafür beliebig viele Zustände und wäre nicht mehr endlichDef. Endlicher Aut. Zustandsmenge Z = {zi; z2; … zn } also gäbe es einen Widerspruch.

Sofern man eine reguläre Grammatik vorliegen hat, kann man immer einen Automaten nach einem Schema finden. Dieses Schema liefert nicht zwangsläufig den schnellsten Automaten