Sprach-Operationen

Aus Sprachen L₁, L₂ konstruiere:

• Mengenoperationen
  • Vereinigung L₁∪L₂,
  • Durchschnitt L₁∩L₂, Differenz L₁ $\setminus$ L₂;
• Verkettung L₁⋅L₂  = {w₁⋅w₂ | w₁∈L₁, w₂∈L₂}
• Stern (iterierte Verkettung) L₁^*  = $\bigcup_{{k\ge 0}}^{}$L₁^k

Def: Sprache regulär : $\iff$ kann durch diese Operationen aus endlichen Sprachen konstruiert werden.

Satz: Durchschnitt und Differenz braucht man dabei nicht.