Sprach-Operationen

Aus Sprachen L₁, L₂ mathend000# konstruiere:

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

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

Satz: Durchschnitt und Differenz braucht man dabei nicht.