Ausblick: Erweiterte Sternhöhe

• ein erweiterter regulärer Ausdruck besteht aus:
  • $\emptyset$, $\epsilon$, Buchstabe
  • Summe (Vereinigung), Produkt (Verkettung), Stern
  • (das ist die Erweiterung): Komplement bzgl $\Sigma^{*}_{}$
• Die ESH (erweiterte Sternhöhe) eines e. r. Ausdrucks X ist die maximale Schachteltiefe der Sterne.
• Die ESH eine Sprache L ist die kleinste ESH eines e. r. Ausdrucks X mit L(X) = L.
• ESH von $\Sigma^{*}_{}$ ist 0, denn $\Sigma^{*}_{}$ ist Komplement von $\emptyset$, also wird kein Stern benutzt.

• Beispiel: (ab)^* = a$\Sigma^{*}_{}$b $\setminus$ $\Sigma^{*}_{}$(aa + bb)$\Sigma^{*}_{}$, also ESH 0.

seit vielen Jahren ungeklärt: gibt es eine reguläre Sprache mit erweiterter Sternhöhe > 1?