path: root/notes/theo2/main.md

---
author: Marvin Borner
date: "`\\today`{=tex}"
lang: de-DE
pandoc-latex-environment:
  bem-box:
  - bem
  bsp-box:
  - bsp
  defi-box:
  - defi
  proof-box:
  - proof
  satz-box:
  - satz
  visu-box:
  - visu
toc-title: Inhalt
---

```{=tex}
\newpage
\renewcommand\O{\mathcal{O}} % IDK WHY
```
# Reguläre Sprachen und endliche Automaten

## Motivation

-   Eingabe
-   Verarbeitung (Berechnungen, Zustände)
-   Ausgabe

## Wörter und Sprachen

::: defi
Ein *Alphabet* $\Sigma$ sei eine nicht-leere, endliche Menge. Ein *Wort*
$w$ ist entsprechend eine Folge von Elementen aus $\Sigma$.
:::

::: bsp
-   $\Sigma=\{a,...,z\}$, $w=\text{luxburg}$, $|w|=7$
:::

::: defi
$\Sigma^n$ ist die Menge aller Wörter der Länge $n$. Die *Kleene'sche
Hülle* ist $\Sigma^*\defeq\bigcup_{n=0}^\infty\Sigma^n$.
$\Sigma^+\defeq\bigcup_{n=1}^\infty\Sigma^n$.

*Sprache $L$ über $\Sigma$* ist eine Teilmenge von $\Sigma^*$.
:::

::: defi
Eine *Konkatenation* ist eine Aneinanderhängung zweier Wörter $u$ und
$w$. Eine Konkatenation zweier *Sprachen* $L_1,L_2$ ist
$L_1\circ L_2\defeq\{uw\mid u\in L_1,\ w\in L_2\}$. Die Kleene'sche
Hülle einer Sprache $L$ ist dann
$L^*\defeq\{\underbrace{x_1...x_k}_{\mathclap{\text{Konkatenation von $k$ Wörtern}}}\mid x_i\in L,\ k\in\N_0\}$.

Eine $k$-fache Aneinanderhängung von Wörtern ist
$w_k=\underbrace{w...w}_\text{$k$-mal}$.
:::

::: bsp
-   $w=010$, $u=001$, $wu=\underbrace{010}_w \underbrace{001}_u$,
    $uwu=\underbrace{001}_u \underbrace{010}_w \underbrace{001}_u$
-   $w^3=010\ 010\ 010$
:::

::: bem
Die Konkatenation auf $\Sigma^*$ hat die Eigenschaften:

-   assoziativ: $a(bc)=(ab)c$
-   nicht kommutativ: $ab\ne ba$
-   neutrales Element $\varepsilon$: $\varepsilon a=a\varepsilon=a$
-   ein inverses Element
:::

::: defi
Ein Wort $x$ heißt *Teilwort* eines Wortes $y$, falls es Wörter $u$ und
$v$ gibt, sodass $y=uxv$.

-   Falls $u=\varepsilon$, $x$ *Präfix* von $y$
-   Falls $v=\varepsilon$, $x$ *Suffix* von $y$
:::

::: bsp
-   $01$ ist Teilwort von $0\textbf{01}11$
-   $10$ ist Präfix von $\textbf{10}10011$
-   $011$ ist Suffix von $10101110\textbf{011}$
:::

## Endlicher, deterministischer Automat

::: defi
Für einen *endlichen, deterministischen Automat*
$(Q,\Sigma,\delta,q_0,F)$ ist

-   $Q$ eine endliche Menge der *Zustände*
-   $\Sigma$ das *Alphabet*
-   $\delta: Q\times\Sigma\to Q$ die Übergangsfunktion
-   $q_0\in Q$ der *Startzustand*
-   $F\subset Q$ die Menge der *akzeptierenden Zustände*
:::

::: bsp
```{=tex}
\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
    \node[state]           (q_3)  [right of=q_2]    {$q_3$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_3)
          edge [loop above] node {1}    (   )
    (q_3) edge [bend left]  node {0,1}  (q_2);
\end{tikzpicture}\end{center}
```
$Q=\{q_1,q_2,q_3\}$, $\Sigma=\{0,1\}$, $q_1$ Startzustand, $F=\{q_2\}$.

$\delta$ kann dargestellt werden durch

  /       0       1
  ------- ------- -------
  $q_1$   $q_1$   $q_2$
  $q_2$   $q_3$   $q_2$
  $q_3$   $q_2$   $q_2$

Die Zustandsfolge ist mit $w=001$
$$q_1\xrightarrow{0}q_1\xrightarrow{0}q_1\xrightarrow{1}q_2.$$
:::

::: defi
-   partielle Übergangsfunktion: nicht alle Übergänge sind definiert
-   totale Übergangsfunktion: alle Übergänge sind definiert
:::

::: defi
Eine Folge $s_0,...,s_n\in Q$ von Zuständen heißt *Berechnung* des
Automaten $M=(Q,\Sigma,\delta,q_0,F)$ auf dem Wort $w=w_1...w_n$, falls

-   $s_0=q_0$,q
-   $\forall i=0,...,n-1: s_{i+1}=\delta(s_i,w_{i+1})$

Es ist also eine "gültige" Folge von Zuständen, die man durch Abarbeiten
von $w$ erreicht.
:::

::: bsp
```{=tex}
\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
    \node[state]           (q_3)  [right of=q_2]    {$q_3$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_3)
          edge [loop above] node {1}    (   )
    (q_3) edge [bend left]  node {0,1}  (q_2);
\end{tikzpicture}\end{center}
```
-   $w=001$ ergibt die Zustandsfolge $q_1q_1q_1q_2$
:::

::: defi
Eine Berechnung *akzeptiert* das Wort $w$, falls die Berechnung in einem
akzeptierten Zustand endet.

Die von einem endlichen Automaten $M$ *akzeptierte* (erkannte) Sprache
$L(M)$ ist die Menge der Wörter, die von $M$ akzeptiert werden:
$$L(M)\defeq\{w\in\Sigma^*\mid M\text{ akzeptiert } w\}$$
:::

::: bem
Eine Berechnung kann mehrmals in akzeptierenden Zuständen
eintreten/austreten. Wichtig ist der Endzustand, nachdem der letzte
Buchstabe des Eingabewortes verarbeitet wurde.
:::

::: bsp
```{=tex}
\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_1)
          edge [loop above] node {1}    (   );
\end{tikzpicture}\end{center}
```
-   $w=1101\rightarrow q_1q_2q_2q_1q_2\rightarrow w$ wird akzeptiert
-   $w=010\rightarrow q_1q_1q_2q_1\rightarrow w$ wird **nicht**
    akzeptiert

Es folgt:
$$L(M)=\{w\in\Sigma^*\mid w=\varepsilon\text{ oder }w\text{ endet mit }0\}$$
:::

::: defi
Sei $\delta:Q\times\Sigma\to Q$ eine Übergangsfunktion. Die *erweiterte
Übergangsfunktion* $\delta^*$: $Q\times\Sigma^*\to Q$ sei induktiv
definiert:

-   $\delta^*(q,\varepsilon)=q$ für alle $q\in Q$
-   Für $w\in\Sigma^*$, $a\in\Sigma$ ist:
    $$\delta^*(q,wa)=\delta(\underbrace{\delta^*(q,w)}_{\mathclap{\text{Zustand nach Lesen von $w$}}}, \overbrace{a}^{\mathclap{\text{Lesen von Buchstabe $a$}}}).$$
:::

## Reguläre Sprachen und Abschlusseigenschaften

::: defi
Eine Sprache $L\subset\Sigma^*$ heißt *reguläre Sprache*, wenn es einen
endlichen Automaten $M$ gibt, der diese Sprache akzeptiert.

Die Menge aller regulären Sprachen ist *REG*.
:::

::: satz
Sei $L$ eine reguläre Sprache über $\Sigma$. Dann ist auch
$\bar{L}\defeq\Sigma^*\setminus L$ eine reguläre Sprache.

::: proof
-   $L$ regulär $\implies$ es gibt Automaten
    $M=(Q,\Sigma,\delta,q_0,F)$, der $L$ akzeptiert
-   Definiere "Komplementautomat"
    $\bar{M}=(Q,\Sigma,\delta,q_0,\bar{F})$ mit
    $\bar{F}\defeq Q\setminus F$.
-   Dann gilt:
    `\begin{align*} w\in\bar{L}&\iff M\text{ akzeptiert }w\text{ nicht}\\ &\iff \bar{M}\text{ akzeptiert }w. \end{align*}\qed`{=tex}
:::
:::

::: satz
Die Menge der regulären Sprachen ist abgeschlossen bezüglich der
Vereinigung: $$L_1,L_2\in\text{REG}\implies L_1\cup L_2\in\text{REG}.$$

::: proof
Sei $M_1=(Q_1,\Sigma_1,\delta_1,s_1,F_1)$ ein Automat, der L_1 erkennt,
$M_2=(Q_2,\Sigma_2,\delta_2,s_2,F_2)$ ein Automat, der L_2 erkennt.

Wir definieren den Produktautomaten $M\defeq M_1\times M_2$:
$M=(Q,\Sigma,\Delta,s,F)$ mit

-   $Q=Q_1\times Q_2$
-   $\Sigma=\Sigma_1\cup\Sigma_2$,
-   $\underbrace{s}_{\mathclap{\text{neuer Startzustand}}}=(s_1,s_2)$,
    $F=\{(f_1,f_2)\mid f_1\in F_1\text{ oder } f_2\in F_2\}$,
-   $\underbrace{\Delta}_{\mathclap{\text{neue Übergangsfunktion}}}: Q\times\Sigma\to Q$,
    $$\Delta((\underbrace{r_1}_{\in Q_1},\underbrace{r_2}_{\in Q_2}),\underbrace{a}_{\in\Sigma})=(\delta_1(r_1,a),\delta(r_2,a)).$$

Übertragung der Definition auf erweiterte Übergangsfunktionen: Beweis
durch Induktion (ausgelassen).

Nach Definition von $F$ akzeptiert $M$ ein Wort $w$, wenn $M_1$ oder
$M_2$ das entsprechende Wort akzeptieren. Der Satz folgt. `\qed`{=tex}
:::
:::

::: bsp
```{=tex}
$M_1$: \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_1)
          edge [loop above] node {1}    (   );
\end{tikzpicture}\end{center}
$M_2$: TODO \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state]           (q_2)  [right of=q_1]    {$q_2$};
    \node[state,accepting] (q_2)  [right of=q_2]    {$q_2$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_1)
          edge [loop above] node {1}    (   )
    (q_3) edge [bend left]  node {0}    (q_1)
          edge [loop above] node {1}    (   );
\end{tikzpicture}\end{center}
$M_1\times M_2$: TODO \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_1)
          edge [loop above] node {1}    (   );
\end{tikzpicture}\end{center}
```
:::

::: satz
Seien $L_1,L_2$ zwei reguläre Sprachen. Dann sind auch $L_1\cap L_2$ und
$L_1\setminus L_2$ reguläre Sprachen.

::: proof
-   $L_1\cap L_2$: Beweis funktioniert analog wie für $L_1\cup L_2$, nur
    mit
    $$F\defeq\{(q_1,q_2)\mid q_1\in F_1\text{\textbf{ und }}q_2\in F_2\}.$$
-   $L_1\setminus L_2=L_q\cap\bar{L_2}$

`\qed`{=tex}
:::
:::

## Nicht-deterministische Automaten

::: bsp
TODO (ggf. auch Sipser).

```{=tex}
\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
  \tikzstyle{every state}=[]

    \node[state,initial]   (q_1)                    {$q_1$};
    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
    \node[state]           (q_3)  [right of=q_2]    {$q_3$};

    \path[->]
    (q_1) edge [loop above] node {0}    (   )
          edge [bend left]  node {1}    (q_2)
    (q_2) edge [bend left]  node {0}    (q_1)
          edge [loop above] node {1}    (   );
\end{tikzpicture}\end{center}
```
:::

::: defi
Ein *nicht-deterministischer Automat* besteht aus einem $5$-Tupel
$(Q,\Sigma,\delta,q_0,F)$.

-   $Q$, $\Sigma$, $q_0$, $F$ wie beim deterministischen Automat,
-   $\delta: Q\times\Sigma\cup\{\varepsilon\}\to\overbrace{\pot(Q)}^{(*)}$
    Übergangsfunktion

$(*)$: Die Funktion definiert die **Menge** der möglichen Zustände, in
die man von einem Zustand durch Lesen eines Buchstabens gelangen kann.
:::

::: defi
Sei $M=(Q,\Sigma,\delta,q_0,F)$ ein nicht-deterministischer endlicher
Automat, $w=w_1...w_n\in\Sigma^*$. Eine Folge von Zuständen
$s_0,s_1,...,s_m\in Q$ heißt *Berechnng von $M$ auf $w$*, falls man $w$
schreiben kann als $w=u_1u_2...u_m$ mit
$u_i\in\Sigma\cup\{\underbrace{\varepsilon}_{\mathclap{\text{Übergänge $\varepsilon$, hier $u_i=\varepsilon$}}}\}$,
sodass

-   $s_0=q_0$,
-   für alle $0\le i\le m-1:s_{i+1}\in\delta(s_1,u_{i+1}).$

Die Berechnung heißt *akzeptierend*, falls $s_m\in F$.

Der nicht-deterministische Automat $M$ *akzeptiert Wort $w$*, falls es
eine akzeptierende Berechnung von $M$ auf $w$ gibt.
:::

::: bem
$\varepsilon$-Transitionen: TODO.
:::

::: bsp
Betrachte die regulären Sprachen

-   $A\defeq\{x\in\{0,1\}^*\mid\text{Anzahl }0\text{ gerade}\}$
-   $B\defeq\{x\in\{0,1\}^*\mid\text{Anzahl }0\text{ ungerade}\}$

Zugehörige Automaten: TODO

Nun betrachte *Konkatenation $AB$*. Um die Sprache zu erkennen, müsste
der Automat bei einer Eingabe zunächst einen ersten Teil $A$ des Wortes
betrachten und schauen, ob die Anzahl der $0$ gerade ist. **Irgendwann**
müsste er beschließen, dass nun der zweite Teil $B$ des Wortes anfängt
und er müsste schauen, ob dort die Anzahl der $0$ ungerade ist.

$$\text{"Irgendwann"}\implies\text{nicht-deterministisch.}$$

TODO: Graph.
:::

## Mächtigkeit

::: bem
Die Mächtigkeit eines Automaten wird hierbei beschrieben durch die
Anzahl an Sprachen, die dieser erkennen kann.
:::

::: defi
Zwei Automaten $M_1$, $M_2$ heißen *äquivalent*, wenn sie die gleiche
Sprache erkennen: $$L(M_1)=L(M_2)$$
:::

::: satz
Zu jedem nicht-deterministischen endlichen Automaten gibt es einen
äquivalenten deterministischen endlichen Automaten.

::: proof
Lang aber trivial. Basically konstruiert man einfach eine
deterministische Übergangsfunktion auf den nicht-deterministischen
Verzweigungen.
:::
:::

::: satz
Es folgt:

Eine Sprache $L$ ist regulär $\iff$ es gibt einen
nicht-deterministischen Automaten, der $L$ akzeptiert.
:::

::: satz
Die Klasse der regulären Sprachen ist abgeschlossen unter Konkatenation:
$$L_1,L_2\in\mathrm{REG}\implies L_1L_2\in\mathrm{REG}$$
:::

::: satz
Die Klasse REG ist abgeschlossen unter Bildung der Kleene'schen Hülle,
d.h.: $$L\in\mathrm{REG}\implies L^*\in\mathrm{REG}$$
:::

## Reguläre Ausdrücke

::: defi
Sei $\Sigma$ ein Alphabet. Dann:

-   $\underbrace{\emptyset}_{\mathclap{\text{leere Sprache}}}$ und
    $\overbrace{\varepsilon}^{\mathclap{\text{leeres Wort}}}$ sind
    reguläre Ausdrücke.
-   Alle Buchstaben aus $\Sigma$ sind reguläre Ausdrücke.
-   Falls $R_1$, $R_2$ reguläre Ausdrücke sind, dann sind auch die
    folgenden Ausdrücke regulär:
    -   $R_1\cup R_2$,
    -   $R_1\circ R_2$,
    -   $R_1^*$.
:::

::: defi
Sei $R$ ein regulärer Ausdruck. Dann ist die *von $R$ induzierte Sprache
$L(R)$* wie folgt definiert:

-   $R=\emptyset\implies L(R)=\emptyset$
-   $R=\epsilon\implies L(R)=\{\varepsilon\}$
-   $R=\sigma\text{ für ein }\sigma\in\Sigma\implies L(R)=\{\sigma\}$
-   $R=R_1\cup R_2\implies L(R)=L(R_1)\cup L(R_2)$
-   $R=R_1\circ R_2\implies L(R)=L(R_1)\circ L(R_2)$
-   $R=R_1^*\implies L(R)=(L(R_1))^*$
:::

::: satz
Eine Sprache ist genau dann regulär, wenn sie durch einen regulären
Ausdruck beschrieben wird.

::: proof
Strukturelle Induktion. Tja.
:::
:::