Automaten-Synthese

Id: synth.tex,v 1.2 2007-11-16 20:01:11 waldmann Exp

Satz: Zu jedem regulären Ausdruck X gibt es einen $\epsilon$-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 $\epsilon$-Pfeile weg
• keine Pfeile führen von F(A) weg

Wir bezeichnen solche A mit s$\;\stackrel{{X}}{{\to}}\;$f.