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)
LA(p, q, r) =
mathend000# alle Pfade von p
mathend000# nach
r
mathend000# über Zustände ≤q
mathend000#.
Johannes Waldmann
2014-03-31