ω-(reguläre) Sprachen

• Alphabet Σ,
• ω-Wort w∈Σ^ω: Abbildung $\mathbb {N}$→Σ
• ω-Sprache L⊆Σ^ω: Menge von ω-Wörtern

  
  

• ω-reguläres Wort: hat die Form u⋅v^ω mit v≠ε.

  
  Achtung: es gibt kein Produkt von ω-Wörtern,

  also auch keine geschachtelten Omegas.

• ω-reguläre Sprache:

  beschrieben durch ω-regulären Ausdruck:

  P₁⋅K₁^ω∪…∪P_n⋅K_n^ω      mit P_i, K_i regulär und ≠∅, ε $\notin$K_i

  
  Achtung: eine ω-reguläre Sprache (Bsp. (a + b)^ω)

  kann auch nicht-reguläre ω-Wörter enthalten.