Automaten-Synthese

Id: synth.tex,v 1.2 2004/12/14 12:36:40 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.