%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\newcommand{\SH}{\operatorname{SH}}
\newcommand{\ESH}{\operatorname{ESH}}

\begin{slide}{Sternhöhe}

\kopf{$ $Id: star.tex,v 1.1 2011-10-16 14:06:17 waldmann Exp $ $}


Def: die Sternhöhe $\SH(X)$ eines regulären Ausdrucks $X$
ist die maximale Schachteltiefe der Sterne.

Bsp: $\SH((a^*b)^*) = 2$.

Def: die Sternhöhe $\SH(L)$ einer regulären Sprache $L$
ist $\min \{\SH(X) \mid L(X) = L \}$.

Bsp: $\SH((a^*b)^*) = 1$, denn $(a^*b)^* = \epsilon \cup \Sigma^*b$

\end{slide}

\begin{slide}{Erweiterte Sternhöhe}

Def: in \emph{erweiterten} regulären Ausdrücken
ist als zusätzlicher Operator \emph{Komplement} bzgl. $\Sigma^*$
und \emph{Mengendifferenz} gestattet.

Def: erweiterte Sternhöhe $\ESH(X)$ eines Ausdrucks
wie oben als maximale Schachteltiefe,
erweiterte Sternhöhe $\ESH(L)$ einer Sprache
wie oben als kleinste $\ESH(X)$ mit $L(X)=L$.

Bsp: $\ESH((ab)^*) = 0$, denn $(ab)^* = \epsilon \cup a\Sigma^*b
\setminus \Sigma^*(aa \cup bb) \Sigma^*$

beachte: $\ESH(\Sigma^*) = 0$ wegen $\Sigma^* =$ Komplement von $\emptyset$.

Vermutung: für jede reguläre Sprache $L$ gilt $\ESH(L)\le 1$. 



\end{slide}
