Sätze über reguläre Sprachen

Für jede Sprache L sind die folgenden Aussagen äquivalent:

• es gibt einen regulären Ausdruck X mit L = L(X) ,
• es gibt eine Typ-3-Grammatik G mit L = L(G) ,
• es gibt einen endlichen Automaten A mit L = L(A) .

Beweispläne:

• Grammatik ↔ Automat (Variable = Zustand)
• Ausdruck → Automat (Teilbaum = Zustand)
• Automat → Ausdruck (dynamische Programmierung)

  L_A(p, q, r) = alle Pfade von p nach r über Zustände ≤q .