Der Satz von Kleene

Definition

Für eine Sprache $L\in {\Sigma }^{\ast }$ sind äquivalent:

1. Es gibt einen regulären Ausdruck $r$ mit $L=L(r)$.
2. $L$ ist regulär

Beweis

X Ist eine Teilmege aller Zustände. $L_{pq}^X$ ist die Menge aller Wörter die man bekommt, wenn man von $p$ nach $q$ geht und über alle Zustände X geht.

Beispiel