Einführung in die Theoretische Informatik und in die Mathematische Logik - Benutzerbeiträge [de]

Orakel

2018-08-29T15:37:26Z

Jana: /* Turing-Reduzierbarkeit */

Man ist im Allgemeinen nicht nur daran interessiert, ob und wie gut ein Problem berechenbar ist, sondern auch daran, wie sich Probleme relativ zueinander verhalten. Hierzu führt man '''Orakel''' ein. Ein Orakel ist eine zusätzliche Anweisung einer Maschine, die ein konkretes Problem lösen kann, ohne dafür Zeit zu brauchen.

In Registermaschinen kann man zum Beispiel einen Befehl <code>oracle R[i] R[j] ...</code> einführen. Bei Turingmaschinen würde man ein zusätzliches Band einführen, auf das man dann das Orakel anwenden kann. Wichtig ist jedenfalls, besonders später in der Komplexitätstheorie, dass dieses Orakel keine Zeit braucht.

== Turing-Reduzierbarkeit ==

Von '''Turing-Reduzierbarkeit''' zwischen zwei Problemen $A$ und $B$, geschrieben $A \le_T B$, redet man, wenn es eine Orakel-Turingmaschine $M$ gibt, mit einem Orakel für $B$, die damit das Problem $A$ lösen kann.

Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $H \le_T PCP$. Allgemein sind die meisten Unentscheidbarkeitsbeweise Turing-Reduktionen auf das Halteproblem und verwandte Probleme.

== Jenseits von Unentscheidbarkeit ==

Die Betrachtung von Maschinen mit Halteproblem-Orakel macht nicht nur Sinn, um andere Probleme mit dem Halteproblem zu vergleichen. Man kann dieses Maschinenmodell auch einfach so betrachten. Turingmaschinen mit Halteproblem-Orakel haben insbesondere wieder ein eigenes, neues, schwereres Halteproblem. In diesem Halteproblem kann man wiederum eine neue Orakelturingmaschine definieren, und wenn man dies fortsetzt, erhält man eine Hierarchie von immer komplizierteren Halteproblemen. Wir werden '''TODO''' später sehen, dass man diese Orakelturingmaschinen verwenden kann, um die Schwierigkeit bestimmter arithmetischer Formeln zu klassifizieren.

== Der Satz von Friedberg und Muchnik ==

Eine weitere Frage, die man sich stellen kann, ist, ob es auch unentscheidbare Probleme gibt, die nicht Turingreduzierbar auf das Halteproblem sind. Das heißt, ein Problem, das "echt leichter" ist als das Halteproblem, aber dennoch "echt schwerer" als alle berechenbaren Probleme.

Der [https://de.wikipedia.org/wiki/Satz_von_Friedberg_und_Muchnik|Satz von Friedberg und Muchnik] beweist, dass es in der Tat solche Probleme gibt.

[[Kategorie:TODO]]

Entscheidbarkeit

2018-08-29T09:33:21Z

Jana: /* Aufzählbare Sprachen */

Wir wollen nun Sprachen klassifizieren. Die Frage, ob ein Wort in einer Sprache vorkommt, nennt sich das '''Entscheidungsproblem''' dieser Sprache. In der Literatur bezeichnet man mit dem Entscheidungsproblem allerdings teilweise auch nur ein ganz spezielles Problem, nämlich das Entscheidungsproblem der Menge der wahren mathematischen Aussagen.

Zu diesem Zweck müssen wir jedenfalls irgendwie vereinbaren, dass die Rechenmaschine uns "Wahr" und "Falsch" zurückliefern kann. Wir können dazu bei Turingmaschinen zusätzliche Spezialzustände einführen, und für Registermaschinen Befehle <code>return true</code> und <code>return false</code>. Wie genau wir es machen ist aber letztendlich egal, die meisten Methoden sind offensichtlich äquivalent.

== Entscheidbare Sprachen ==

Eine Sprache $\frak L$ heißt '''entscheidbar''', wenn es einen Algorithmus gibt, der für alle Wörter terminiert, und genau dann "Wahr" zurückliefert, wenn das übergebene Wort in $\frak L$ liegt. Es sind also die Sprachen, für die es einen effektiven Algorithmus gibt. Beispielsweise ist ${\cal L}^*$ immer entscheidbar, genauso $\emptyset$. Die Menge der geraden Zahlen, genauso wie die Menge der Primzahlen.

Einen effektiven Algorithmus zu haben heißt aber nicht, dass dieser auch effizient sein muss. Die zugehörige Maschine muss ''irgendwann'' terminieren. Wie lange sie ansonsten brauchen darf, ist nicht begrenzt.

'''Lemma:''' Ist $\frak L$ entscheidbar, so ist auch $\overline{\frak L}$ entscheidbar.

'''Beweis:''' Übung.

'''TODO'''

== Aufzählbare Sprachen ==
Wir erweitern Registermaschinen um einen Befehl <code>print R[i]</code>. Die Intuition ist, dass solche Registermaschinen eine Folge von Werten ausgeben, und zwar einen Wert mit jedem <code>print</code>-Befehl.

Eine Sprache $\frak L$ heißt nun '''aufzählbar''', wenn es eine Registermaschine gibt, die jedes Element irgendwann <code>print</code>-ed.

'''Lemma:''' Jede entscheidbare Menge ist aufzählbar.

'''Beweis:''' Sei $\frak L\subseteq\mathbb{N}$ entscheidbar, und werde durch das Programm $E$ entschieden. Dann zählt das folgende Programm die Menge auf:

Start: if E(R[1]) then goto Pr
R[1]++
goto Start

Pr: print R[1]
R[1]++
goto Start

'''Lemma:''' Die Menge der Lösungen eines gegebenen diophantischen Gleichungssystems $D(x_1,\ldots,x_n)=0$ ist aufzählbar.

'''Beweis:''' Die Idee ist, einfach alle $n$-tupel $(x_1,\ldots,x_n)$ durchzuprobieren, und die, für die es passt, auszugeben.

'''Satz:''' Die Menge der terminierenden Turingmaschinen $\frak T$ ist aufzählbar.

'''Beweis:''' Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:

Start: if T[R[0],R[1]] == ‾|‾ then print R[0]
R[0]++
if R[0] > R[1] then goto Rst
goto Start

Rst: R[0] := 0
R[1]++
goto Start

Der Algorithmus probiert alle $T_i^k$ durch, in der Reihenfolge $T_0^0, T_0^1, T_1^1, \ldots$.

== Semi-Entscheidbare Sprachen ==
Eine Sprache $\frak L$ heißt Semi-Entscheidbar, wenn es einen Algorithmus $M(n)$ gibt, der als Eingabe eine natürliche Zahl $n$ erhält, und ein Wort oder $\bot$ ausgibt, sodass es genau für die Wörter in $\frak L$ eine Eingabe $n$ gibt. Formaler ist also $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$ surjektiv.

'''Lemma:''' Semi-Entscheidbare Sprachen sind Aufzählbar

'''Beweis:''' Sei ${\frak L}\subseteq\mathbb{N}$ semi-entscheidbar mit zugehörigem $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$. Dann wird $\frak L$ von folgendem Programm aufgezählt:

Start: if M(R[0]) == _|_ then goto Cont
print M(R[0])
Cont: R[0]++
goto Start

'''Lemma:''' Aufzählbare Sprachen sind Semi-Entscheidbar

'''Beweis:''' Sei ${\frak L}\subseteq\mathbb{N}$ aufzählbar und werde von $M$ aufgezählt. Sei $M_i = \bot$, falls $M$ nach $i$ Schritten eine andere Anweisung als <code>print</code> ausführt, ansonsten, falls die Anweisung nach $i$ Schritten <code>print R[j]</code> ist, $M_i=R_j$. Offenbar ist $M_i$ für jedes $i$ berechenbar, denn man muss ja nur die Registermaschine $M$ für $i$ schritte simulieren. Die zurückgelieferte Funktion $i\mapsto M_i$ ist offenbar von der Form, dass sie $\frak L$ semi-entscheidet.

Damit sind Semi-Entscheidbarkeit und Aufzählbarkeit also äquivalent, und damit zwei Arten, über die selbe Sache nachzudenken.

'''Lemma:''' Eine Sprache $\frak L$ ist genau dann entscheidbar, wenn sowohl $\frak L$ als auch $\overline{\frak L}$ semi-entscheidbar sind.

'''Beweis:''' "$\Rightarrow$" ist trivial. "$\Leftarrow$": Seien $M : \mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ und $\overline{M}:\mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ entsprechend gegeben. Dann entscheidet folgendes Programm $\frak L$:

Start: if M(R[1]) == R[0] then goto Tr
if ‾M(R[1]) == R[0] then goto Fa
R[1]++
goto Start

Tr: return True
Fa: return False

Dieser Algorithmus terminiert garantiert.

'''Korollar:''' Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.

== Beispiel: Das Post'sche Korrespondenzproblem ==

Gegeben eine Menge an Dominosteinen bei denen jeweils oben und unten eine Zeichenkette steht, gibt es eine Folge an Dominos, so dass die Konkatenation der Ketten oben und unten gleich sind? (Dabei dürfen Steine mehrmals verwendet werden.)

Beispiel:

(1) (2) (3)
[ 1 ] [10] [011]
----- ---- -----
[101] [00] [ 11]

Überlegung:
Damit die ersten beiden Zeichen des konkatenierten Strings gleich sein können, muss der erste Stein (1) sein.
Dann muss das erste Zeichen des oberen Strings eine 0 sein, also ist der nächste Stein (3). Als nächstes könnte man sowohl (1) oder (2) nehmen, damit der untere String im Vergleich zum oberen aber nicht immer länger nimmt nehmen wir (2). Als nächsten Stein müssen wir wieder (3) nehmen und damit haben wir auch eine Lösung gefunden.

Lösung:(1)(3)(2)(3)

Offensichtlich können wir Lösungen miteinander konkatenieren um neue (beliebig lange) Lösungen zu erhalten. Wenn kein Teil einer Lösung für sich stehend eine Lösung ist nennen wir sie primitiv.

Keine Lösung gibt es zB für:
[11] [01]
---- ----
[ 1] [ 0]
(Der obere String ist immer länger als der untere)

Eine Formalisierung dieses Problems ist folgendermaßen:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_1,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_(i_1),...,x_(i_n) = y_(i_1),...,y_(i_n)$.

Wir wollen zeigen, dass dieses Problem nicht entscheidbar ist.

Dazu werden wir zeigen, dass sich das Halteproblem auf eine modifizierte Version des PKPs reduzieren lässt, die sich wiederum auf das PKP reduzieren lässt. Wenn es also einen allgemeinen Algorithmus zur Entscheidung des PKPs gäbe, müsste es auch einen allgemeinen Algorithmus für das Halteproblem geben.

mPKP:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_2,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_1,...,x_(i_n) = y_1,...,y_(i_n)$.

Wir zeigen die Äquivalenz der beiden Probleme in dem wir eine Funktion $f$ basteln die ein Set $K$ von Dominos in ein neues Set $f(K)$ überführt, so dass eine Lösung für mPKP über K auch eine Lösung für PKP ist und umgekehrt.

Sei $K = \{[\frac{x_1}{y_1}],...,[\frac{x_1}{x_k}]\}$,
dann sei $f(K) = \{[\frac{x'_0}{y'_0}],[\frac{x'_1}{y'_1}],...,[\frac{x'_k}{y'_k}],[\frac{x'_{k+1}}{y'_{k+1}}]\}$ mit

<ul>
<li> $x'_i$ aus $x_i$ entsteht, indem wir hinter jedes Zeichen ein # einfügen</li>
<li> $y'_i$ aus $y_i$ entsteht, indem wir vor jedes Zeichen ein # einfügen</li>
</ul>

Außerdem gelte $x'_0 = \# x'_1$, $ x'_{k+1} = \$ $, $y'_0 = y'_1$ und $y'_{k+1} = \#\$ $

Beispiel:
$ K= \{ [\frac{ab}{a}],[\frac{c}{abc}],[\frac{c}{abc}]\}$
wird zu
$ f(K) = \{[\frac{\#a\#b\#}{\#a}],[\frac{a\#b\#}{\#a}],[\frac{c\#}{\#a\#b\#c}],[\frac{a\#}{\#b}],[\frac{\$}{\#\$}]\}$

mPKP -> PKP

Sei $(1,i_2,...i_n)$ eine Lösung für $K$, d.h. $x_1 x_{i_2} x_{i_n} = y_1 y_{i_2}... y_{i_n} = a_1 a_2 ... a_1$ so dass $a_1...a_s$ Symbole aus $\Sigma$.

Dann ist $(0, i_2,....,in,k+1)$ eine Lösung für $f(K)$, denn $$x'_0x'_{i_2}...x'_{i_n}\$ = \#a_1\#a_2...\#a_s\#\$ = y'_0y'_{i_2}...y'_{i_n}\#\$ $$

Wenn es also eine Lösung für $K$ bzgl. mPKP, so gibt es auch eine Lösung für $f)K=$ bgzl. PKP.

PKP -> mPKP

Sei nun(i_1,i_2,...,i_n) eine primitve Lösung für $f(K)$:

<ul>
<li>Es gilt $i_1=0$ und $i_n = k+1$, weil nur $x'_0$ und $y'_0$ mit demselben Zeichen beginnen und nur $x'_{k+1}$ und $y'_{k+1} mit demselben Zeichen enden.</li>
<li>Es gilt $i_j$ \neq 0$ für $2\leq j \leq n$, weil sonst zwei # oben aufeinanderfolgen, was unten nicht sein kann.</li>
<li>Es gilt $i_j \neq k+1$ für $1\leq j < n$, weil sonst die Folge bis $i_j$ auch eine Lösung wäre (Widerspruch zur geforderten Primitivität der Lösung)</li>
</ul>

Also sieht unsere Lösung für PKP folgendermaßen aus: $$x'_0x'_{i_2}...x'_{i_n} = \#a_1\#a_2...\#a_s\#\$ = y'_0y'_{i_2}...y'_{i_n} $$ woraus wir die mPKP Lösung $$x_1 x_{i_2} x_{i_n} = y_1 y_{i_2}... y_{i_n} = a_1 a_2 ... a_1$$

Wenn man mPKP lösen kann, kann man also auch PKP lösen.

(Fortsetzung: [https://algo.rwth-aachen.de/Lehre/WS0910/VBuK/Folien/berechenbarkeit6.pdf]

[[Kategorie:TODO]]

Entscheidbarkeit

2018-08-27T14:21:23Z

Jana: /* Beispiel: Das Post'sche Korrespondenzproblem */

Wir wollen nun Sprachen klassifizieren. Die Frage, ob ein Wort in einer Sprache vorkommt, nennt sich das '''Entscheidungsproblem''' dieser Sprache. In der Literatur bezeichnet man mit dem Entscheidungsproblem allerdings teilweise auch nur ein ganz spezielles Problem, nämlich das Entscheidungsproblem der Menge der wahren mathematischen Aussagen.

Zu diesem Zweck müssen wir jedenfalls irgendwie vereinbaren, dass die Rechenmaschine uns "Wahr" und "Falsch" zurückliefern kann. Wir können dazu bei Turingmaschinen zusätzliche Spezialzustände einführen, und für Registermaschinen Befehle <code>return true</code> und <code>return false</code>. Wie genau wir es machen ist aber letztendlich egal, die meisten Methoden sind offensichtlich äquivalent.

== Entscheidbare Sprachen ==

Eine Sprache $\frak L$ heißt '''entscheidbar''', wenn es einen Algorithmus gibt, der für alle Wörter terminiert, und genau dann "Wahr" zurückliefert, wenn das übergebene Wort in $\frak L$ liegt. Es sind also die Sprachen, für die es einen effektiven Algorithmus gibt. Beispielsweise ist ${\cal L}^*$ immer entscheidbar, genauso $\emptyset$. Die Menge der geraden Zahlen, genauso wie die Menge der Primzahlen.

Einen effektiven Algorithmus zu haben heißt aber nicht, dass dieser auch effizient sein muss. Die zugehörige Maschine muss ''irgendwann'' terminieren. Wie lange sie ansonsten brauchen darf, ist nicht begrenzt.

'''Lemma:''' Ist $\frak L$ entscheidbar, so ist auch $\overline{\frak L}$ entscheidbar.

'''Beweis:''' Übung.

'''TODO'''

== Aufzählbare Sprachen ==
Wir erweitern Registermaschinen um einen Befehl <code>print R[i]</code>. Die Intuition ist, dass solche Registermaschinen eine Folge von Werten ausgeben, und zwar einen Wert mit jedem <code>print</code>-Befehl.

Eine Sprache $\frak L$ heißt nun '''aufzählbar''', wenn es eine Registermaschine gibt, die jedes Element irgendwann <code>print</code>-ed.

'''Lemma:''' Jede entscheidbare Menge ist aufzählbar.

'''Beweis:''' Sei $\frak L\subseteq\mathbb{N}$ entscheidbar, und werde durch das Programm $E$ entschieden. Dann zählt das folgende Programm die Menge auf:

Start: if E(R[1]) then goto Pr
R[1]++
goto Start

Pr: print R[1]
R[1]++
goto Start

'''Lemma:''' Die Menge der Lösungen eines gegebenen diophantischen Gleichungssystems $D(x_1,\ldots,x_n)=0$ ist aufzählbar.

'''Beweis:''' Die Idee ist, einfach alle $n$-tupel $(x_1,\ldots,x_n)$ durchzuprobieren, und die, für die es passt, auszugeben.

'''Satz:''' Die Menge der terminierenden Turingmaschinen $\frak T$ ist aufzählbar.

'''Beweis:''' Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:

Start: if T[R[0],R[1]] == ‾|‾ then print R[0]
R[0]++
if R[0] > R[1] then goto Rst
goto Start

Rst: R[0] := 0
R[1]++

Der Algorithmus probiert alle $T_i^k$ durch, in der Reihenfolge $T_0^0, T_0^1, T_1^1, \ldots$.

== Semi-Entscheidbare Sprachen ==
Eine Sprache $\frak L$ heißt Semi-Entscheidbar, wenn es einen Algorithmus $M(n)$ gibt, der als Eingabe eine natürliche Zahl $n$ erhält, und ein Wort oder $\bot$ ausgibt, sodass es genau für die Wörter in $\frak L$ eine Eingabe $n$ gibt. Formaler ist also $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$ surjektiv.

'''Lemma:''' Semi-Entscheidbare Sprachen sind Aufzählbar

'''Beweis:''' Sei ${\frak L}\subseteq\mathbb{N}$ semi-entscheidbar mit zugehörigem $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$. Dann wird $\frak L$ von folgendem Programm aufgezählt:

Start: if M(R[0]) == _|_ then goto Cont
print M(R[0])
Cont: R[0]++
goto Start

'''Lemma:''' Aufzählbare Sprachen sind Semi-Entscheidbar

'''Beweis:''' Sei ${\frak L}\subseteq\mathbb{N}$ aufzählbar und werde von $M$ aufgezählt. Sei $M_i = \bot$, falls $M$ nach $i$ Schritten eine andere Anweisung als <code>print</code> ausführt, ansonsten, falls die Anweisung nach $i$ Schritten <code>print R[j]</code> ist, $M_i=R_j$. Offenbar ist $M_i$ für jedes $i$ berechenbar, denn man muss ja nur die Registermaschine $M$ für $i$ schritte simulieren. Die zurückgelieferte Funktion $i\mapsto M_i$ ist offenbar von der Form, dass sie $\frak L$ semi-entscheidet.

Damit sind Semi-Entscheidbarkeit und Aufzählbarkeit also äquivalent, und damit zwei Arten, über die selbe Sache nachzudenken.

'''Lemma:''' Eine Sprache $\frak L$ ist genau dann entscheidbar, wenn sowohl $\frak L$ als auch $\overline{\frak L}$ semi-entscheidbar sind.

'''Beweis:''' "$\Rightarrow$" ist trivial. "$\Leftarrow$": Seien $M : \mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ und $\overline{M}:\mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ entsprechend gegeben. Dann entscheidet folgendes Programm $\frak L$:

Start: if M(R[1]) == R[0] then goto Tr
if ‾M(R[1]) == R[0] then goto Fa
R[1]++
goto Start

Tr: return True
Fa: return False

Dieser Algorithmus terminiert garantiert.

'''Korollar:''' Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.

== Beispiel: Das Post'sche Korrespondenzproblem ==

Gegeben eine Menge an Dominosteinen bei denen jeweils oben und unten eine Zeichenkette steht, gibt es eine Folge an Dominos, so dass die Konkatenation der Ketten oben und unten gleich sind? (Dabei dürfen Steine mehrmals verwendet werden.)

Beispiel:

(1) (2) (3)
[ 1 ] [10] [011]
----- ---- -----
[101] [00] [ 11]

Überlegung:
Damit die ersten beiden Zeichen des konkatenierten Strings gleich sein können, muss der erste Stein (1) sein.
Dann muss das erste Zeichen des oberen Strings eine 0 sein, also ist der nächste Stein (3). Als nächstes könnte man sowohl (1) oder (2) nehmen, damit der untere String im Vergleich zum oberen aber nicht immer länger nimmt nehmen wir (2). Als nächsten Stein müssen wir wieder (3) nehmen und damit haben wir auch eine Lösung gefunden.

Lösung:(1)(3)(2)(3)

Offensichtlich können wir Lösungen miteinander konkatenieren um neue (beliebig lange) Lösungen zu erhalten. Wenn kein Teil einer Lösung für sich stehend eine Lösung ist nennen wir sie primitiv.

Keine Lösung gibt es zB für:
[11] [01]
---- ----
[ 1] [ 0]
(Der obere String ist immer länger als der untere)

Eine Formalisierung dieses Problems ist folgendermaßen:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_1,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_(i_1),...,x_(i_n) = y_(i_1),...,y_(i_n)$.

Wir wollen zeigen, dass dieses Problem nicht entscheidbar ist.

Dazu werden wir zeigen, dass sich das Halteproblem auf eine modifizierte Version des PKPs reduzieren lässt, die sich wiederum auf das PKP reduzieren lässt. Wenn es also einen allgemeinen Algorithmus zur Entscheidung des PKPs gäbe, müsste es auch einen allgemeinen Algorithmus für das Halteproblem geben.

mPKP:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_2,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_1,...,x_(i_n) = y_1,...,y_(i_n)$.

Wir zeigen die Äquivalenz der beiden Probleme in dem wir eine Funktion $f$ basteln die ein Set $K$ von Dominos in ein neues Set $f(K)$ überführt, so dass eine Lösung für mPKP über K auch eine Lösung für PKP ist und umgekehrt.

Sei $K = \{[\frac{x_1}{y_1}],...,[\frac{x_1}{x_k}]\}$,
dann sei $f(K) = \{[\frac{x'_0}{y'_0}],[\frac{x'_1}{y'_1}],...,[\frac{x'_k}{y'_k}],[\frac{x'_{k+1}}{y'_{k+1}}]\}$ mit

<ul>
<li> $x'_i$ aus $x_i$ entsteht, indem wir hinter jedes Zeichen ein # einfügen</li>
<li> $y'_i$ aus $y_i$ entsteht, indem wir vor jedes Zeichen ein # einfügen</li>
</ul>

Außerdem gelte $x'_0 = \# x'_1$, $ x'_{k+1} = \$ $, $y'_0 = y'_1$ und $y'_{k+1} = \#\$ $

Beispiel:
$ K= \{ [\frac{ab}{a}],[\frac{c}{abc}],[\frac{c}{abc}]\}$
wird zu
$ f(K) = \{[\frac{\#a\#b\#}{\#a}],[\frac{a\#b\#}{\#a}],[\frac{c\#}{\#a\#b\#c}],[\frac{a\#}{\#b}],[\frac{\$}{\#\$}]\}$

mPKP -> PKP

Sei $(1,i_2,...i_n)$ eine Lösung für $K$, d.h. $x_1 x_{i_2} x_{i_n} = y_1 y_{i_2}... y_{i_n} = a_1 a_2 ... a_1$ so dass $a_1...a_s$ Symbole aus $\Sigma$.

Dann ist $(0, i_2,....,in,k+1)$ eine Lösung für $f(K)$, denn $$x'_0x'_{i_2}...x'_{i_n}\$ = \#a_1\#a_2...\#a_s\#\$ = y'_0y'_{i_2}...y'_{i_n}\#\$ $$

Wenn es also eine Lösung für $K$ bzgl. mPKP, so gibt es auch eine Lösung für $f)K=$ bgzl. PKP.

PKP -> mPKP

Sei nun(i_1,i_2,...,i_n) eine primitve Lösung für $f(K)$:

<ul>
<li>Es gilt $i_1=0$ und $i_n = k+1$, weil nur $x'_0$ und $y'_0$ mit demselben Zeichen beginnen und nur $x'_{k+1}$ und $y'_{k+1} mit demselben Zeichen enden.</li>
<li>Es gilt $i_j$ \neq 0$ für $2\leq j \leq n$, weil sonst zwei # oben aufeinanderfolgen, was unten nicht sein kann.</li>
<li>Es gilt $i_j \neq k+1$ für $1\leq j < n$, weil sonst die Folge bis $i_j$ auch eine Lösung wäre (Widerspruch zur geforderten Primitivität der Lösung)</li>
</ul>

Also sieht unsere Lösung für PKP folgendermaßen aus: $$x'_0x'_{i_2}...x'_{i_n} = \#a_1\#a_2...\#a_s\#\$ = y'_0y'_{i_2}...y'_{i_n} $$ woraus wir die mPKP Lösung $$x_1 x_{i_2} x_{i_n} = y_1 y_{i_2}... y_{i_n} = a_1 a_2 ... a_1$$

Wenn man mPKP lösen kann, kann man also auch PKP lösen.

(Fortsetzung: [https://algo.rwth-aachen.de/Lehre/WS0910/VBuK/Folien/berechenbarkeit6.pdf]

[[Kategorie:TODO]]

Entscheidbarkeit

2018-08-26T22:49:11Z

Jana: /* Beispiel: Das Post'sche Korrespondenzproblem */

Wir wollen nun Sprachen klassifizieren. Die Frage, ob ein Wort in einer Sprache vorkommt, nennt sich das '''Entscheidungsproblem''' dieser Sprache. In der Literatur bezeichnet man mit dem Entscheidungsproblem allerdings teilweise auch nur ein ganz spezielles Problem, nämlich das Entscheidungsproblem der Menge der wahren mathematischen Aussagen.

Zu diesem Zweck müssen wir jedenfalls irgendwie vereinbaren, dass die Rechenmaschine uns "Wahr" und "Falsch" zurückliefern kann. Wir können dazu bei Turingmaschinen zusätzliche Spezialzustände einführen, und für Registermaschinen Befehle <code>return true</code> und <code>return false</code>. Wie genau wir es machen ist aber letztendlich egal, die meisten Methoden sind offensichtlich äquivalent.

== Entscheidbare Sprachen ==

Eine Sprache $\frak L$ heißt '''entscheidbar''', wenn es einen Algorithmus gibt, der für alle Wörter terminiert, und genau dann "Wahr" zurückliefert, wenn das übergebene Wort in $\frak L$ liegt. Es sind also die Sprachen, für die es einen effektiven Algorithmus gibt. Beispielsweise ist ${\cal L}^*$ immer entscheidbar, genauso $\emptyset$. Die Menge der geraden Zahlen, genauso wie die Menge der Primzahlen.

Einen effektiven Algorithmus zu haben heißt aber nicht, dass dieser auch effizient sein muss. Die zugehörige Maschine muss ''irgendwann'' terminieren. Wie lange sie ansonsten brauchen darf, ist nicht begrenzt.

'''Lemma:''' Ist $\frak L$ entscheidbar, so ist auch $\overline{\frak L}$ entscheidbar.

'''Beweis:''' Übung.

'''TODO'''

== Aufzählbare Sprachen ==
Wir erweitern Registermaschinen um einen Befehl <code>print R[i]</code>. Die Intuition ist, dass solche Registermaschinen eine Folge von Werten ausgeben, und zwar einen Wert mit jedem <code>print</code>-Befehl.

Eine Sprache $\frak L$ heißt nun '''aufzählbar''', wenn es eine Registermaschine gibt, die jedes Element irgendwann <code>print</code>-ed.

'''Lemma:''' Jede entscheidbare Menge ist aufzählbar.

'''Beweis:''' Sei $\frak L\subseteq\mathbb{N}$ entscheidbar, und werde durch das Programm $E$ entschieden. Dann zählt das folgende Programm die Menge auf:

Start: if E(R[1]) then goto Pr
R[1]++
goto Start

Pr: print R[1]
R[1]++
goto Start

'''Lemma:''' Die Menge der Lösungen eines gegebenen diophantischen Gleichungssystems $D(x_1,\ldots,x_n)=0$ ist aufzählbar.

'''Beweis:''' Die Idee ist, einfach alle $n$-tupel $(x_1,\ldots,x_n)$ durchzuprobieren, und die, für die es passt, auszugeben.

'''Satz:''' Die Menge der terminierenden Turingmaschinen $\frak T$ ist aufzählbar.

'''Beweis:''' Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:

Start: if T[R[0],R[1]] == ‾|‾ then print R[0]
R[0]++
if R[0] > R[1] then goto Rst
goto Start

Rst: R[0] := 0
R[1]++

Der Algorithmus probiert alle $T_i^k$ durch, in der Reihenfolge $T_0^0, T_0^1, T_1^1, \ldots$.

== Semi-Entscheidbare Sprachen ==
Eine Sprache $\frak L$ heißt Semi-Entscheidbar, wenn es einen Algorithmus $M(n)$ gibt, der als Eingabe eine natürliche Zahl $n$ erhält, und ein Wort oder $\bot$ ausgibt, sodass es genau für die Wörter in $\frak L$ eine Eingabe $n$ gibt. Formaler ist also $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$ surjektiv.

'''Lemma:''' Semi-Entscheidbare Sprachen sind Aufzählbar

'''Beweis:''' Sei ${\frak L}\subseteq\mathbb{N}$ semi-entscheidbar mit zugehörigem $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$. Dann wird $\frak L$ von folgendem Programm aufgezählt:

Start: if M(R[0]) == _|_ then goto Cont
print M(R[0])
Cont: R[0]++
goto Start

'''Lemma:''' Aufzählbare Sprachen sind Semi-Entscheidbar

'''Beweis:''' Sei ${\frak L}\subseteq\mathbb{N}$ aufzählbar und werde von $M$ aufgezählt. Sei $M_i = \bot$, falls $M$ nach $i$ Schritten eine andere Anweisung als <code>print</code> ausführt, ansonsten, falls die Anweisung nach $i$ Schritten <code>print R[j]</code> ist, $M_i=R_j$. Offenbar ist $M_i$ für jedes $i$ berechenbar, denn man muss ja nur die Registermaschine $M$ für $i$ schritte simulieren. Die zurückgelieferte Funktion $i\mapsto M_i$ ist offenbar von der Form, dass sie $\frak L$ semi-entscheidet.

Damit sind Semi-Entscheidbarkeit und Aufzählbarkeit also äquivalent, und damit zwei Arten, über die selbe Sache nachzudenken.

'''Lemma:''' Eine Sprache $\frak L$ ist genau dann entscheidbar, wenn sowohl $\frak L$ als auch $\overline{\frak L}$ semi-entscheidbar sind.

'''Beweis:''' "$\Rightarrow$" ist trivial. "$\Leftarrow$": Seien $M : \mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ und $\overline{M}:\mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ entsprechend gegeben. Dann entscheidet folgendes Programm $\frak L$:

Start: if M(R[1]) == R[0] then goto Tr
if ‾M(R[1]) == R[0] then goto Fa
R[1]++
goto Start

Tr: return True
Fa: return False

Dieser Algorithmus terminiert garantiert.

'''Korollar:''' Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.

== Beispiel: Das Post'sche Korrespondenzproblem ==

Gegeben eine Menge an Dominosteinen bei denen jeweils oben und unten eine Zeichenkette steht, gibt es eine Folge an Dominos, so dass die Konkatenation der Ketten oben und unten gleich sind? (Dabei dürfen Steine mehrmals verwendet werden.)

Beispiel:

(1) (2) (3)
[ 1 ] [10] [011]
----- ---- -----
[101] [00] [ 11]

Überlegung:
Damit die ersten beiden Zeichen des konkatenierten Strings gleich sein können, muss der erste Stein (1) sein.
Dann muss das erste Zeichen des oberen Strings eine 0 sein, also ist der nächste Stein (3). Als nächstes könnte man sowohl (1) oder (2) nehmen, damit der untere String im Vergleich zum oberen aber nicht immer länger nimmt nehmen wir (2). Als nächsten Stein müssen wir wieder (3) nehmen und damit haben wir auch eine Lösung gefunden.

Lösung:(1)(3)(2)(3)

Keine Lösung gibt es zB für:
[11] [01]
---- ----
[ 1] [ 0]
(Der obere String ist immer länger als der untere)

Eine Formalisierung dieses Problems ist folgendermaßen:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_1,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_(i_1),...,x_(i_n) = y_(i_1),...,y_(i_n)$.

Wir wollen zeigen, dass dieses Problem nicht entscheidbar ist.

Dazu werden wir zeigen, dass sich das Halteproblem auf eine modifizierte Version des PKPs reduzieren lässt, die sich wiederum auf das PKP reduzieren lässt. Wenn es also einen allgemeinen Algorithmus zur Entscheidung des PKPs gäbe, müsste es auch einen allgemeinen Algorithmus für das Halteproblem geben.

mPKP:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_2,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_1,...,x_(i_n) = y_1,...,y_(i_n)$.

[[Kategorie:TODO]]

Nichtdeterministische Endliche Automaten

2018-08-26T16:33:03Z

Jana:

Deterministische endliche Automaten beschreiben ziemlich direkt ein Modell zur Berechnung, zur Entscheidung von Sprachenzugehörigkeit. Andererseits kann man es auch anders herum so betrachten, als würde ein deterministischer endlicher Automat eine Sprache beschreiben. Mit dieser Intuition können wir, auch zur formalen Betrachtung, den Automatenbegriff erweitern.

Anders als bisher dürfen jetzt mehrere Kanten mit der selben Beschriftung von einem Status wegführen. Die Transitionsfunktion $\delta$ hat damit eine andere Signatur, nämlich geht sie nicht in die Menge der Zustände, sondern in deren '''Potenzmenge''': $\delta:Z\times{\cal L}\rightarrow{\frak P}(Z)$.

Solche Automaten heißen Nichtdeterministische endliche Automaten. Ein Wort gilt als akzeptiert, wenn es einen Lauf durch den Automaten gibt, der in einem Endzustand endet. Wo deterministische endliche Automaten sich eignen, um Berechnungen zu beschreiben, eignen sich nichtdeterministische endliche Automaten, um Suchprobleme zu beschreiben.

== Beispiele ==

=== Beispiel 1 ===
Sei ${\cal L}=\{a,b\}$ und der folgende Automat betrachtet:

+---+ |
| | V
a,b (0)--a-->(1)--a,b-->(2)--a,b-->(3)-- ... -->((k))
| A
+---+

Dieser Automat akzeptiert genau die Wörter, sodass das an $k$-letzter Stelle ein $a$ steht. An diesem Beispiel sieht man gut, dass nichtdeterministische endliche Automaten viel kleiner sein können, als äquivalente deterministische endliche Automaten. Man benötigt einen deterministischen endlichen Automaten mit $2^k$ Zuständen, um dasselbe zu erreichen, zum Beispiel für $k=3$:

+b+ +----------------------+
| | | +-a-+ |
V | V V | |
-->(bbb)---a--->(bba)---a---->(baa)---a--->((aaa)) |
A | A | | |
| b | b b |
| | +--------+ | | |
| V | V | |
| (bab)-----+ | ((aab))<-------+ |
| A | | | | | |
| | a b a b | |
| b | | | | | |
| | V V | V | |
| ((aba)) ((abb)) a |
| | A | | |
| a | b | |
| | | | | |
| +-*------*-----*---------------------+
| | | |
+--------------*------+ |
| |
+------------+

=== Beispiel 2 ===
Sei ${\cal L}=\{a\}$. Für eine Primzahl $p$ sei folgendes Gadget betrachtet:

*
|
V
((q[p,0]))--a-->(q[p,1])--a-->((q[p,2]))--a-->...--a-->((q[p,p-1])) =: {p}-*
A |
+----------------------------a--------------------------+

Man betrachte nun folgenden Automaten:

+--------a---->{2}
| +------a---->{3}
| |
(q[0])----a---->{5}
| |
| +------a---->{7}
... ...
|
+--------a---->{p}

Sei $q\le p$ eine Primzahl. Ein Wort, dessen Länge $\equiv -1\mod q$ ist, wird nicht in {q} akzeptiert, aber in irgendeinem anderen Gadget. Das kürzteste Wort, das nicht akzeptiert wird, muss also $\equiv -1\mod q$ sein, für alle Primzahlen $q\le p$. Nach dem chinesischen Restsatz hat das kürzeste nicht akzeptierte Wort damit die Länge $2\cdot 3\cdot \ldots\cdot p-1$.

== Epsilon-Kanten ==

Eine nützliche Erweiterung von nichtdeterministischen endlichen Automaten ist die Einführung sogenannter $\varepsilon$-Kanten. Das sind Kanten, die man passieren kann, ohne ein Zeichen zu konsumieren. Beispielsweise akzeptiert folgender Automat

+----ε-----+
| |
V |
(1)---a--->(2)---b--->((3))

beliebige Wörter ab, aab, aaab, etc. $\varepsilon$-Kanten sind praktisch, um Abschlusseigenschaften von Automaten zu zeigen. Allerdings sind sie eine Erweiterung des Automatenmodells. Es ist allerdings möglich, sie zu '''eliminieren''', das heißt, einen äquivalenten Automaten anzugeben, der keine $\varepsilon$-Kanten mehr enthält.

Zunächst betrachten wir drei Zustände $p,q,r$. Bezeichne $A$ die Menge der Übergänge von $p$ nach $q$, und $B$ die Menge der Übergänge von $q$ nach $r$, wir schreiben $p \stackrel{A}{\rightarrow} q \stackrel{B}{\rightarrow} r$. Ist nun $\varepsilon\in A$, das heißt, eine $\varepsilon$-Kante geht von $p$ nach $q$, so fügen wir für jedes Element von $B$ eine Kante von $p$ nach $r$ hinzu (sofern diese nicht schon existiert), das heißt, $p\stackrel{B}{\rightarrow} r$. Analog für $\varepsilon\in B$ Kanten $p\stackrel{A}{\rightarrow} r$.

Wenn wir dies für jedes Tripel $p,q,r$ tun, und immer wieder wiederholen, wird sich irgendwann nichts mehr ändern: Es kann maximal für jedes Zeichen von allen Zuständen zu allen anderen eine Kante geben, und dies sind nur endlich viele, das ist also eine obere Schranke.

Im entstehenden Automaten gibt es für jeden Lauf, der eine $\varepsilon$-Kante enthält, einen äquivalenten Lauf, der diese nicht enthält. Entsprechend können wir jetzt alle $\varepsilon$-Kanten entfernen, ohne die akzeptierte Sprache zu ändern.

Aus obigem Automaten wird beispielsweise

+----a-----+
| |
V |
(1)---a--->(2)---b--->((3))

== Potenzmengen-Konstruktion ==

Die kanonische Frage die sich nun stellt ist, ob nichtdeterministische endliche Automaten mehr können, als deterministische endliche Automaten. Tatsächlich zeigt sich, dass sie das nicht können: Man kann zu jedem nichtdeterministischen endlichen Automaten einen deterministischen endlichen Automaten konstruieren, der die selbe Sprache akzeptiert. Allerdings kann es sein, wie in obigem Beispiel erwähnt, dass man exponentiell viele Zustände bekommt. Dies ist aber in der Praxis eher selten der Fall.

Zunächst sei ein nichtdeterministischer endlicher Automat über dem Alphabet $\cal L$ gegeben, mit Zustandsmenge $Q$, Startzustand $q_0\in Q$, Endzustände $Z\subseteq Q$ und Transitionsfunktion $\delta:Q\times{\cal L}\rightarrow{\frak P}(Q)$. Wir wollen dazu den passenden deterministischen endlichen Automaten definieren.

Dessen Zustandsmenge wird ${\frak P}(Q)$ selbst. Der Startzustand wird das Singleton $\{q_0\}\in{\frak P}(Q)$. Ein Übergang zu einem Zeichen $a\in{\cal L}$ wird dann zwischen $X,Y\subseteq Q$ eingezeichnet, wenn $Y$ genau die Zustände aus $Q$ enthält, die von Zuständen in $X$ mittels eines $a$-Übergangs erreichbar sind, formal $\delta'(X, a) = \bigcup\limits_{x\in X} \delta(x,a)$. Ein Zustand wird Endzustand, wenn mindestens ein Element Endzustand war.

=== Beispiel ===

Sei der obige Automat für $k=2$ betrachtet, also

+---+ |
| | V
a,b (0)--a-->(1)--a,b-->((2))
| A
+---+

Die Potenzmenge der Zustände ist $\{\emptyset, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\}$, der neue Startzustand ist also $\{0\}$. Neue Endzustände sind $\{2\},\{1,2\},\{0,1,2\}$. Wir erhalten

+---------------a---------------+ +------------------a---------------+
| | | |
| V | V
-->(0) (1) ((2)) (01) ((02)) ((12)) ((012))
| A | A | A
| | | | | |
+b+ +----a,b----+ +-----b----+

oder, wenn wir die nicht erreichbaren Zustände weglassen,

+---------------a---------------+ +------------------a---------------+
| | | |
| V | V
-->(0) (01) ((02)) ((012))
| A | A
| | | |
+b+ +-----b----+

== Abschlusseigenschaften ==

Wir zeigen hier Abschlusseigenschaften für nichtdeterministische endliche Automaten mit $\varepsilon$-Kanten. Analog zu den obigen Algorithmen kann aus den resultierenden Automaten aber jeweils wieder ein deterministischer endlicher Automat hergestellt werden. Entsprechend sind die Abschlusseigenschaften hier auch Abschlusseigenschaften für deterministische endliche Automaten.

=== Singletons ===

Die Sprache, die nur ein einzelnes Wort der Länge 1 enthält, zum Beispiel $\{a\}$, wird akzeptiert von

-->(1)--a-->((2))

=== Negation/Komplement ===

Ist eine Sprache $A$ gegeben, und wird von einem Automaten $M$ akzeptiert, so ist ihre Negation oder ihr '''Komplement''' definiert durch $\overline{A} := {\cal L}^*\backslash A$. Den Automaten $M$ muss man nur dahingehend verändern, dass man die Rolle von Endzustand und Zwischenzustand vertauscht. Dann werden genau die Wörter akzeptiert, die $M$ nicht akzeptiert.

=== Konkatenation ===

Wird eine Sprache $A$ von einem Automaten $M$ mit Endzuständen $q_1,\ldots, q_n$

+------->((q1))
|
--->[M] ...
|
+-------->((qn))

akzeptiert, und eine Sprache $B$ von einem Automaten $N$ mit den Endzuständen $r_1,\ldots, r_k$

+-------->((r1))
|
--->[N] ...
|
+-------->((rk))

so wird die Konkatenation der Sprachen, also die Sprache $AB := \{ab\mid a\in A, b\in B\}$, akzeptiert vom Automaten, bei dem von jedem Endzustand in $M$ eine $\varepsilon$-Kante zum Anfangszustand $N$ gezogen wird, also

+------->(q1)---ε--+ +------>((r1))
| V |
--->[M] ... [N] ...
| A |
+------->(qn)---ε--+ +------>((rk))

=== Vereinigung ===

Wird eine Sprache $A$ vom Automaten $M$ akzeptiert, und eine Sprache $B$ vom Automaten $N$ akzeptiert, so wird $A\cup B$ akzeptiert von

+---ε--->[M]
|
--->(1)
|
+---ε--->[N]

=== Schnitt ===

Es gilt $A\cap B = \overline{\overline{A}\cup\overline{B}}$.

=== Kleene-Hülle ===

Die Kleene-Hülle $A*$ einer Sprache $A$ ist definiert als $\{\varepsilon\}\cup A\cup AA\cup AAA\cup\ldots$, also alle endlichen Wiederholungen von Wörtern aus $A$. Akzeptiert der Automat $M$ mit Anfangszustand $q_0$ und mit Endzuständen $q_1,\ldots,q_n$ die Sprache $A$, so wird $A*$ akzeptiert von

+--ε----------+
| |
| +-->((q1))
V |
---->((q0))-->[M] ...
A |
| +->((qn))
| |
+---ε-------+

Deterministische Endliche Automaten

2018-08-26T15:09:26Z

Jana:

== Einführung ==
Wir wollen uns nun ein einfaches Maschinenmodell ansehen, mit dem man bestimmte Wörter erkennen kann. Das Ganze ist zwar inspiriert von echten Schaltkreisen, und man kann anhand dessen auch theoretisch Maschinen bauen, ist aber ein rein formales Konstrukt.

Zunächst überlegen wir uns, dass eine Maschine ein Wort am sinnvollsten Zeichen für Zeichen einliest und verarbeitet. Wenn ein Zeichen eingelesen ist, muss sich irgendetwas in der Maschine verändern, das heißt, eine Maschine hat irgendeinen '''Zustand'''. Das heißt, das Einlesen eines Zeichens führt eine Maschine von einem Zustand in einen anderen Zustand über.

Gehen wir der Einfachheit halber davon aus, dass eine bestimmte Maschine nur endlich viele Zustände hat, und benennen wir diese Zustände mit Zahlen $1,\ldots,n$. Das Einfachste, was so eine Maschine beim Einlesen eines Zeichens tun kann ist, entscheiden, zu welchem Zustand sie Springen soll. Man kann sich einen so einfachen Zustand also so vorstellen:

+------a1-------->
|
(n)-----a2-------->
| ...
|
+------an-------->

wobei $n$ die Nummer des Zustandes ist, und die $a_i$ die Zeichen des endlichen Alphabets sind. Die Pfeile zeigen dabei jeweils entweder wieder auf Zustände, oder "ins Leere". Eine Maschine, die sich aus mehreren solchen einfachen Zuständen zusammensetzt, nennt man einen (deterministischen endlichen) '''Automaten'''.

Ein sehr einfacher endlicher Automat ist zum Beispiel gegeben durch

A
|
1
|
(1)---0--->(2)---0--->
A |
| |
+----1-----+

Der Einfachheit halber lässt man die Pfeile, die "ins Leere" zeigen, weg:

(1)---0--->(2)
A |
| |
+----1-----+

Einer der Zustände muss derjenige sein, in dem der Automat am Anfang, wenn noch garnichts eingelesen wurde, ist. Es hat sich eingebürgert, einen Pfeil der "aus dem Leeren" kommt, dafür zu benutzen:

---->(1)---0--->(2)
A |
| |
+----1-----+

Nehmen wir nun an, dieser Automat lese das Wort $0101$ ein. Das erste Zeichen ist $0$, und wir sind im Zustand (1). Der Zustand (1) hat einen Pfeil mit der Beschriftung $0$ zu Zustand (2). Das heißt, danach sind wir in Zustand (2).

Das nächste Zeichen ist $1$. Von (2) geht ein Pfeil mit der Beschriftung $1$ zum Zustand (1), das heißt, danach sind wir wieder im Zustand (1).

Das dritte Zeichen ist $0$. Analog zu vorhin gehen wir zu Zustand (2). Das vierte Zeichen ist wieder $1$, und wir gehen wieder zum Zustand (1). Das Wort ist vollständig eingelesen.

Natürlich bringt es uns nicht viel, Wörter nur einlesen zu können. Was wir wollen, ist, dass der Automat eine ''Entscheidung'' trifft: Er kann ein Wort '''akzeptieren''' oder '''ablehnen'''. Fürs Akzeptieren definieren wir '''Endzustände''', und sagen, wenn der Automat nach dem Einlesen des Wortes in einem Endzustand ist, dann gilt das Wort als akzeptiert. Endzustände stellen wir dar mit zwei Kreisen statt einem.

---->(1)---0--->((2))
A |
| |
+----1------+

Das Wort $010$ wird zum Beispiel akzeptiert: Nach dem vollständigen Einlesen sind wir bei Zustand (2), welches ein Endzustand ist.

Wann immer ein Wort nicht akzeptiert wird, gilt es als abgelehnt. Das Wort $0101$ wird zum Beispiel abgelehnt: Am Ende ist man in Zustand (1), welcher kein Endzustand ist. Das Wort $011$ wird ebenfalls abgelehnt: nachdem wir $01$ eingelesen haben, sind wir in Zustand (1), aber der $1$-Pfeil von (1) zeigt ins Leere.

== Beispiele ==

* Der folgende Automat erkennt genau $\varepsilon$:

---->((1))

* Der folgende Automat erkennt beliebig viele Wiederholungen von "abc":

---->((1))---a--->(2)---b--->(3)
A |
| |
+----------c-----------+

* Der folgende Automat erkennt beliebige Folgen von $0$ und $1$ mit gerade vielen $1$-en:

+------------+
| +--------+ |
| | | |
V V | |
---->((1))---0---+ |
| |
1 |
| |
V |
+-(2)----1-----+
| A
0 |
| |
+--+

* Der folgende Automat erkennt, ob die Summe der Zahlen einer Folge von Nullen, Einsen und Zweien durch drei Teilbar ist:

+-+ +-+ +-+
| | | | | |
0 | 0 | 0 |
| V | V | V
---->((1))----1---->(2)------1----->(3)
A A | A | |
| | | | | |
| +-----2----+ +------2------+ |
+--------------1----------------+

== Alternativen ==

=== Abflusszustand ===

Statt Pfeile, die "ins Leere" gehen, wegzulassen, können wir auch festlegen, dass immer alle Pfeile wieder auf einen Zustand zeigen. Um dann Pfeile "ins Leere" zu simulieren, fügen wir einen '''Abflusszustand''' ($\bot$) hinzu. Auf ($\bot$) sollen alle Pfeile die sonst ins Leere gehen würden zeigen, außerdem führen alle Pfeile von ($\bot$) weg wieder zurück zu ($\bot$), und ($\bot$) ist kein Endzustand. Aus obigem Beispiel würde dann

+------------------------+
| | +--0--+
1 V | |
| +-->(_|_)<---+
---->(1)---0--->((2))--0---+ | A
A | | |
| | +-1-+
+----1------+

Der Automat akzeptiert offensichtlich die gleichen Wörter, und hat keine Pfeile mehr, die ins Leere zeigen. Wir werden, je nach Anwendungsfall, auf diese Form von Automaten zurückgreifen, da sie ja äquivalent ist.

== Formale Definition ==

Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen, und einen Startzustand $s\in Z$. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\delta : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Quartupel $(Z, E, s, \delta)$ beschreibt den Automaten damit eindeutig.

Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $s=1$, $\delta(1,0)=1$, $\delta(1,1)=2$, $\delta(2,0)=2$, $\delta(2,1)=1$.

Deterministische Endliche Automaten

2018-08-26T14:57:46Z

Jana: Fehlende-Automatenkante-bei Teilbarkeit-durch-3-Fix

Grundbegriffe

2018-08-26T14:39:09Z

Jana: Zahlendreherfix

== Alphabet ==
Als '''Alphabet''' bezeichnet man eine Menge von Zeichen. Eine Menge als "Alphabet" zu bezeichnen sagt nichts über diese Menge aus, sondern gibt an, was man vorhat mit der Menge zu tun.

Beispiele:

* Das Alphabet für Unalzahlen $\{1\}$
* Das Alphabet der Dualstellen $\{0,1\}$
* Ein Alphabet für einfache mathematische Formeln $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
* '''TODO'''

In den meisten Fällen verwenden wir endliche Alphabete. Es ist aber ohne Weiteres möglich, eine unendliche Menge als Alphabet zu benutzen.

== Wort ==

Als '''Wort''' über einer Sprache $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einer Sprache $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.

Beispiele:

* Die Wörter über $\{1\}$ sind endliche Folgen von Einsen; sie stellen die Unaldarstellungen von $\mathbb{N}$ dar.
* $00101001$, $1$, $000$ sind Wörter über $\{0,1\}$
* $(1+(2\cdot 3))$, aber auch syntaktisch falsche Wörter wie $)($, sind Wörter über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
* Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jeder Sprache. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einer Sprache $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.
* '''TODO'''

Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als '''Verkettung''' oder '''Konkatenation'''. Beispielsweise ist $a\varepsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.

== Sprache ==

Als '''Sprache''' über einem Alphabet $\cal L$ bezeichnet man eine (nicht notwendigerweise endliche) Teilmenge von ${\cal L}^*$.

Beispiele:

* Die leere Sprache $\emptyset$ ist Sprache über jedem Alphabet.
* ${\cal L}^+$ und ${\cal L}^*$ sind Sprachen über dem Alphabet $\cal L$.
* Die Menge der syntaktisch korrekten Formeln über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ist eine Sprache. Sie enthält insbesondere zum Beispiel nicht die Zeichenkette $)($.
* Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.
* '''TODO'''

== Codierung als Zahlen ==

Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[1;n]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [1;n]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen. $\varepsilon$ wird $0$ zugeordnet.

Lemma: Diese Zuordnung ist Bijektiv.
Beweis: Übung.

Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.

Das Wort $)($ bekäme die Zahl $6+ 5 \cdot 16=86$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.

Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.

Datei:Logo.svg.png

2018-07-27T13:33:57Z

Jana: