Id: synth.tex,v 1.3 2005/10/19 22:19:55 waldmann Exp
Satz: Zu jedem regulären Ausdruck X
gibt es einen -Automaten A,
so daß
L(X) = L(A).
Beweis (Automaten-Synthese)
Wir konstruieren zu jedem X ein A mit:
-
| S(A)| = | F(A)| = 1
- keine Pfeile führen nach S(A)
- von S(A) führen genau ein Buchstaben- oder
zwei -Pfeile weg
- keine Pfeile führen von F(A) weg
Wir bezeichnen solche A mit
sf.
Johannes Waldmann
2006-02-02