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₁∪L₂, L₁∩L₂, L₁ $\setminus$ L₂
• Verkettung L₁⋅L₂  = {w₁⋅w₂ | w₁∈L₁, w₂∈L₂}
• Stern L₁^*  = $\bigcup_{{k\ge 0}}^{}$L₁^k