Bezeichnungen

\(\varSigma\)

Alphabet

\(\varsigma\)

Leeres Wort

\(\varSigma^*\)

Menge der Wörter über \(\varSigma\)

\(\{ a,b \}^* = \{ \varepsilon, a, b, ab, aa, ba, bb, ... \}\)

\[\begin{split}&\mid w \mid = \text{Länge des Wortes } w \in \varSigma^* \text{(Anzahl der Buchstaben)} &\mid w \mid_a = \text{Anzahl der a's in } w \in \varSigma^*\end{split}\]

Verkettung

\(u \cdot v \equiv uv\)

Wortmenge / formale Sprache in \(P(\varSigma^*)\)

L, L’

\[\begin{split}&L \cdot L' = \{ uv \mid u \in L, v \in L' \} \\ &L^o = \{ \varsigma \} \\ &L^{n + 1} = L^n \cdot L \\ &L^1 = L \\ &L^* = \bigcup_{u \in \mathbb{N}} L^n \\\end{split}\]