Formale Sprachen

$\sum$ Alphabet, nicht leere endliche Menge an Symbolen

$\varepsilon$ Leerwort (Leer-String (""), nicht Leerzeichen("_")oder leere Menge{})

$w$ Wort über $\Sigma$ , endliche Verkettung von Symbolen

Verkettung: $w \cdot w' = ww'$

Wort Mengen

$L \subseteq \Sigma^{*}$- Formale Sprache über$\Sigma^*$

Sprache ist eine Teilmenge aller Wörter des Alphabets potenziert mit Kleene Stern

$2^{\sum^*}$- Menge aller formalen Sprachen

Potenzmenge = Menge die alle möglichen Teilemengen einer Menge enthält

Operationen auf formale Sprachen

$L, L^{\prime} \subseteq \Sigma^{*}$

Vereinigung$L \cup L^{\prime}=\left\{w \mid w \in L \vee w \in L^{\prime}\right\}$

Verkettung$L \cdot L^{\prime}=\left\{w \cdot w^{\prime} \mid w \in L, w^{\prime} \in L^{\prime}\right\}$(nicht kommutativ)

Potenzierung$L^{0}=\{\varepsilon\}$

$L^{n+1}=L \cdot L^{n}$(n≥0)

$L^{+}=\bigcup_{n \geq 1} L^{n}$(Alle Wörter der Länge n für n≥1)

$L^{*}=\bigcup_{n \geq 0} L^{n}=L^{0} \cup L^{+}=\{\varepsilon\} \cup L^{+}$"Kleene Stern"

• Beispiel: Verkettung

  $L_1 = \{a,b\} \qquad L_2 = \{b,c,d\}$

  $L_1 \cdot L_2 = \{a b, a c, a d, b b, b c, b d\}$

  $L_2 \cdot L_1 = \{ba,bb,ca,cb,da,db\}$

• Beispiel: Potenzierung

  $L=\{\mathrm{a}, 42\}$

  $L^{0}=\{\varepsilon\}$

  $\begin{aligned}L^{+} &=\bigcup_{n \geq 1} L^{n}=L^{1} \cup L^{2} \cup L^{3} \cup \cdots \\&=\{a, 42, \text { aa, } a 42,42 a, 4242, \text { aaa, } a a 42, a 42 a, \text { a4242 }, 42 a a, \ldots\}\end{aligned}$

  $\begin{aligned}L^{*} &=\bigcup_{n \geq 0} L^{n}=L^{0} \cup L^{1} \cup L^{2} \cup L^{3} \cup \cdots \\&=\{\varepsilon, a, 42, \text { aa, } a 42,42 \mathrm{a}, 4242, \mathrm{aaa}, \mathrm{aa} 42, \mathrm{a} 42 \mathrm{a}, \mathrm{a} 4242,42 \mathrm{aa}, \ldots\}\end{aligned}$

  ---

  Einselement$\{\epsilon\}$

  $\{\mathrm{a}, \mathrm{b}\} \cdot\{\varepsilon\}=\{\mathrm{a} \cdot \varepsilon, \mathrm{b} \cdot \varepsilon\}=\{\mathrm{a}, \mathrm{b}\}$

  Nullelement$\{\}$

  $\{\mathrm{a}, \mathrm{b}\} \cdot\{\}=\{\}$