Ableitungen (2)

definiere Relation X₁X₂

für Ausdrücke X₁, X₂ und Zeichen a∈Σ

bestimme alle von X durch -Pfade erreichbaren Ausdrücke.

der so definierte Graph ist ein endlicher Automat für Lang(X)

man erhält ein Verfahren zur Automaten-Synthese:

• Eingabe: regulärer Ausdruck X
• Ausgabe: endlicher Automat A mit Lang(A) = Lang(X)

und A ist sogar vollständig und deterministisch.