eth-summaries/semester3/ti/parts/02_finite-automata/02_proofs-of-nonexistance.tex

\newpage
\subsection{Beweise der Nichtexistenz}
Im Gegensatz zum Beweis, dass eine bestimmte Klasse von Programmen (Algorithmen) ein Problem lösen kann
(was ein einfacher Existenzbeweis ist, bei welchem man eine korrekte Implementation liefern kann),
ist der Beweis, dass diese Klasse von Programmen (Algorithmen) dies nicht tun kann viel schwieriger,
da man (logischerweise) nicht für alle (unendlich vielen) Programme zeigen kann, dass sie das Problem nicht lösen.

In diesem Kurs werden wir aber vorerst nur die Klasse der endlichen Automaten behandlen, welche sehr stark eingeschränkt sind,
was diese Beweise verhältnismässig einfach macht.
Falls also ein EA $A$ für zwei unterschiedliche Wörter $x$ und $y$ im gleichen Zustand endet (also $\hdelta(q_0, x) = \hdelta(q_0, y))$),
so heisst das für uns von jetzt an, dass $A$ nicht zwischen $x$ und $y$ unterscheiden kann:

\begin{lemma}[]{Unterscheidung von Wörtern}
    Sei $A$ ein EA über $\Sigma$ und $x \neq y \in \Sigma^*$ so dass
    \begin{align*}
        (q_0, x) \bigvdash{A}{*} (p, \lambda) \text{ und } (q_0, y) \bigvdash{A}{*} (p, \lambda)
    \end{align*}
    für ein $p \in Q$ (also $\hdelta_A (q_0, x) = \hdelta(q_0, y) = p(x, y \in \class [p])$).
    Dann existiert für jedes $z \in \Sigma^*$ ein $r \in Q$, so dass $xz, yz \in \class[r]$, also gilt insbesondere
    \begin{align*}
        xz \in L(A) \Longleftrightarrow yz \in L(A)
    \end{align*}
\end{lemma}
Das obenstehende Lemma 3.3 ist ein Spezialfall einer Eigenschaft, die für jedes (deterministische) Rechnermodell gilt.
Es besagt eigentlich nichts anderes, als dass wenn das Wort $xz$ akzeptiert wird, so wird auch das Wort $yz$

Mithilfe von Lemma 3.3 kann man für einen grossteil Sprachen deren Nichtregularität beweisen.

\numberingOff
\inlineex Sei $L = \{ 0^n1^n \divides n \in \N \}$.
Intuitiv ist diese Sprache Nichtregulär, da $n$ unendlich gross sein kann, aber ein EA logischerweise endlich ist.
Wir müssen hier nur formal ausdrücken, dass das Zählen benötigt wird, dass $L$ akzeptiert wird:

Dazu benutzen wir einen Widerspruchsbeweis. Sei $A$ ein EA über $\alphabets{bool}$ und $L(A) = L$.
Wir nehmen an, dass $L$ regulär ist und betrachten die Wörter $0^1, 0^2, \ldots, 0^{|Q| + 1}$.
Weil wir $|Q| + 1$ Wörter haben, existiert per Pigeonhole-Principle o.B.d.A $i < j \in \{ 1, 2, \ldots, |Q| + 1 \}$
(die Ungleichheit kann in komplexeren Beweisen sehr nützlich werden, da wir dann besser mit Längen argumentieren können),
so dass $\hdelta_A(q_0, 0^i) = \hdelta_A(q_0, 0^j)$, also gilt nach Lemma $0^i z \in L \Leftrightarrow 0^j z \in L \smallhspace \forall z \in \wordbool$.
Dies gilt jedoch nicht, weil für jedes $z = 1^i$ zwar jedes $0^i 1^i \in L$ gilt, aber $0^i 1^j \notin Lh$

\numberingOn

Um die Nichtregularität konkreter Sprachen zu beweisen, sucht man nach einfach verifizierbaren Eigenschaften,
denn wenn eine Sprache eine dieser Eigenschaften \textit{nicht} erfüllt, so ist sie nicht regulär.

% TODO: For Kolmogorov complexity elaborate some more, i.e. how to do proofs properly / how to derive a word more easily
% -> TA Slides explain that really well

\vspace{0.3cm}
\hrule
\vspace{0.2cm}

\fhlc{Cyan}{Pumping}

Eine weitere Methode zum Beweis von Aussagen $L \notin \mathcal{L}_{\text{EA}}$ nennt sich \bi{Pumping} und basiert auf folgender Idee:\\
Wenn für ein Wort $x$ und einen Zustand $p$ gilt, dass $(p, x) \bigvdash{A}{*} (p, \lambda)$, so gilt auch für alle $i \in \N$, dass $(p, x^i) \bigvdash{A}{*} (p, \lambda)$.
Also kann $A$ nicht zwischen $x$ und $x^i$ unterscheiden, oder in anderen Worten, wie viele $x$ er gelesen hat,
also akzeptiert $A$ entweder alle Wörter der Form $yx^iz$ (für $i \in \N$) oder keines davon

\begin{lemma}[]{Pumping-Lemma für reguläre Sprachen}
    Sei $L$ regulär. Dann existiert eine Konstante $n_0 \in \N$, so dass sich jedes Wort $w \in \word$ mit $|w| \geq n_0$ in $w = yxz$ zerlegen lässt, wobei
    \rmvspace
    \begin{multicols}{2}
        \begin{enumerate}[label=\textit{(\roman*)}]
            \item $|yx| \leq n_0$
            \item $|x| \geq 1$
            \item Für $X = \{ yx^kz \divides k\in \N \}$ \textit{entweder} $X \subseteq L$ oder $X \cap L = \emptyset$ gilt
        \end{enumerate}
    \end{multicols}
\end{lemma}
Bei der Wahl von den Teilen von $w$ sollte man idealerweise einen Teil (der dann $=y$ in $w = yxz$ ist) bereits gross genug zu wählen, so dass (i) zutrifft, was es nachher einfacher macht.

\newpage
\numberingOff
\inlineex Wir verwenden wieder die Sprache $L = \{ 0^n 1^n \divides n \in \N \}$ und wieder einen Widerspruchsbeweis:

Wir nehmen an, dass $L$ regulär ist, also gilt Lemma 3.4 und es existiert eine Konstante $n_0$ so dass $|w| \geq n_0$.
Um zu zeigen, dass eine Sprache nicht regulär ist, reicht es aus, zu zeigen, dass es ein (hinreichend langes) Wort gibt, für das eine der Eigenschaften in Lemma 3.4 nicht zutrifft.

Wir wählen $w = 0^{n_0} 1^{n_0}$, also ist $|w| = 2n_0 \geq n_0$.
Zudem müssen wir eine sinnvolle Zerlegung wählen -- denn eine solche existiert für jedes Wort $w$ mit $|w| \geq n_0$ laut Lemma 3.4 --
wir wählen $yx = 0^{n_0}$, also ist $y = 0^l$ und $x = 0^m$ für irgendwelche $l, m \in \N$, so dass $l + m \leq n_0$.

Nach Lemma 3.4 (ii) ist $m \neq 0$ ($|x| \geq 1$).
Nun, da $w = 0^{n_0} 1^{n_0} \in L$, ist $\{ yx^kz \divides k \in \N \} = \{ 0^{n_0 - m + km} 1^{n_0} \divides k \in \N \} \subseteq L$, was aber ein Widerspruch ist,
da $yx^0z = yz = 0^{n_0 - m} 1^{n_0} \notin L$ ($0^{n_0}1^{n_0}$ ist sogar das einzige Wort aus der Menge, das in $L$ liegt)

\inlineintuition Woher kommt $0^{n_0 - m + km}$?
Das Ganze wird mit Klammern bedeutend offensichtlicher: $0^{(n_0 - m) + (km)}$.
Also ist der Ursprung der Koeffizienten auch klar, und sie kommen von $|y| = n_0 - m$ und $|x^k| = km$.
Die Addition im Exponent kommt dann deshalb zustande, da dies ja nicht ein Exponent ist, sondern die Anzahl der Repetitionen.

\numberingOn


\vspace{0.3cm}
\hrule
\vspace{0.2cm}

\fhlc{Cyan}{Kolmogorov-Komplexität basiert}

\begin{theorem}[]{Kolmogorov-Komplexität regulärer Sprachen}
    Sei $L \subseteq \wordbool$ eine reguläre Sprache. Sei $L_x = \{ y \in \wordbool \divides xy \in L \}$ für jedes $x \in \wordbool$.
    Dann existiert eine Konstante $c$, so dass für alle $x, y \in \wordbool$ gilt, dass
    \rmvspace
    \begin{align*}
        K(y) \leq \ceil{\log_2(n + 1)} + c
    \end{align*}

    \rmvspace
    falls $y$ das $n$-te Wort in der Sprache $L_x$ ist
\end{theorem}

\numberingOff
\inlineex Wir verwenden wieder die Sprache $L = \{ 0^n 1^n \divides n \in \N \}$ und wieder einen Widerspruchsbeweis:

Dazu nehmen wir wieder an, dass $L$ regulär ist. Für jedes $m \in \N$ ist $1^m$ das erste Wort in der Sprache $L_{0^m} = \{ y \divides 0^m y \in L \} = \{ 0^j 1^{m + j} \divides j \in \N \}$.
Die zweite Menge beinhaltet also alle möglichen Wörter $y$, die noch immer in $L$ sind, wenn man sie mit $0^m$ als $0^m 0^j 1^{m + j}$ konkateniert
und ist deshalb eine konkrete Beschreibung von $L_{0^m}$.

Also gibt es laut Satz 3.1 eine Konstante $c$, die unabhängig von $x = 0^m$ und $y = 1^m$ und somit von $m$ ist, so dass $K(1^m) \leq \ceil{\log_2(1 + 1)} + c = 1 + c$
($n = 1$ hier, da $1^m$ das erste Wort in $L_{0^m}$ ist und wir dieses Wort betrachten wollen),
also gilt für eine Konstante $d = 1 + c$, dass $K(1^m) \leq d$.
Dies ist aber unmöglich, da:
\begin{enumerate}[label=(\roman*)]
    \item die Anzahl aller Programme, deren Länge $\leq d$ ist, ist höchstens $2^d$ und entsprechend endlich
    \item die Menge $\{ 1^m \divides m \in \N \}$ unendlich ist
\end{enumerate}

Für komplexere Sprachen ist es oft einfach, $L_x$ so zu wählen, dass $x = a^{\alpha + 1}$ ist, wobei $\alpha$ der Exponent (nach Variabelnwechsel) aus der Sprache ist.
Also beispielsweise für $L = \{ 0^{n^2 \cdot 2n \divides n \in \N }\}$ ist $\alpha = m^2 \cdot 2m$, also ist $x = 0^{m^2 \cdot 2m + 1}$.
$y_1$ (das erste Wort der Sprache $L_x$) ist dann $y_1 = 0^{(m + 1)^2 \cdot 2(m + 1) - m^2 \cdot 2m + 1}$.

Wir können dann mit der Länge des Wortes $|y_1|$ und dem Theorem 3.1 argumentieren, dass wir einen Widerspruch erreichen und so also die Sprache nichtregulär ist.

Dazu sagen wir, dass für jedes $m \in \N$ eine Konstante $c$ existiert, so dass $K(y_1) \leq \ceil{\log_2(1 + 1)} + c = 1 + c$.
Da unser Wort $y_1$ unendlich lang werden kann, gibt es unendlich viele solcher Wörter. 
Dies widerspricht jedoch dem Fakt, dass es nur endlich viele Programme mit Kolmogorov-Komplexität $\leq 1 + c$ gibt.

\numberingOn