Sprachen und Sprach-Operationen

Sprache = Menge von Wörtern, Wort = Folge von Zeichen

Bsp: L = {ε, ab, baaaaa}

Operationen:

• Mengeoperationen: L₁∪L₂, ...
• Verkettung L₁⋅L₂ = {w₁⋅w₂ | w₁∈L₁∧w₂∈L₂}
• Potenz (iterierte Verkettung)

  L^k = L⋅…⋅L (mit k Faktoren)

  L^* = L⁰∪L¹∪L²∪… (unendliche viele Summanden)

Satz: für alle Sprachen L:
(L entsteht durch ∪,⋅,^* aus endlichen Sprachen)
$\iff$ (L ist Sprache eines endlichen Automaten)