Nächste Seite:
Über dieses Dokument ...
Aufwärts:
Ergänzungen, Zusammenfassung
Vorherige Seite:
Autotool-Highscore-Auswertung
Ausblick: Erweiterte Sternhöhe
ein
erweiterter regulärer Ausdruck
besteht aus:
,
, Buchstabe
Summe (Vereinigung), Produkt (Verkettung), Stern
(das ist die Erweiterung): Komplement bzgl
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
ist 0, denn
ist Komplement von
, also wird kein Stern benutzt.
Beispiel:
(
ab
)
*
=
a
b
(
aa
+
bb
)
, also ESH 0.
seit vielen Jahren ungeklärt:
gibt es eine reguläre Sprache mit erweiterter Sternhöhe
> 1
?
Johannes Waldmann 2006-02-02