Sätze über reguläre Sprachen

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

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

Beweispläne:

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

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