Sätze über Reguläre Sprachen

Für jede Sprache L sind die folgenden Aussagen äquivalent:

• es gibt einen regulären Ausdruck X mit L = L(X),
• es gibt eine Typ-3-Grammatik G mit L = L(G),
• es gibt einen endlichen Automaten A mit L = L(A).

Wenn L₁, L₂ reguläre Sprachen sind, dann sind die folgenden Sprachen auch regulär:

• Mengenoperationen L₁ $\cup$ L₂, L₁ $\cap$ L₂, L₁ $\setminus$ L₂
• Verkettung L₁ ^. L₂  = {w₁ ^. w₂ | w₁ $\in$ L₁, w₂ $\in$ L₂}
• Stern L₁^*  = $\bigcup_{{k\ge 0}}^{}$L₁^k