====== Sprachen ======
"Sprache entscheidbar" = Wortproblem entscheidbar

Äquivalent
  * Wortproblem semi-entscheidbar
  * Sprache semi-entscheidbar
  * Sprache rekursiv aufzählbar
  * Sprache ist Typ 0
  * Es existiert TM für Sprache
  * $\chi_A$ ist Turing-berechenbar
  * Sprache ist Definitionsbereich einer berechenbaren Funktion
  * Sprache ist Wertebereich einer berechenbaren Funktion

{{:users:skruppy:ext:uni:4:fsk:languages.png|}}
===== (formale) Sprache =====
//Menge// von //Wörtern// die als //korrekt// erachtet werden

$L \subseteq \Sigma$

==== Typ ===
//Sprache// ist vom Typ $x$, wenn //Grammatik// vom Typ $x$ existiet.

Vom Typ einer //Grammatik// kann nicht auf Typ der //Sprache// geschlossen werden.


==== Chomsky ====
"0 hat nix Vorgeschrieben"

^     ^^  Typ 0  ^  Typ 1  ^    Typ 2  ^^  Typ 3  ^
^ ::: ^^ :::     ^ :::     ^  ND  ^  D  ^ :::     ^
^                                         Name ||  Alle Grammatiken  |  Kontext//sensitiv//  |  Kontext//frei//  ||  Regulär  |
^           Bedingung \\ $w_1 \rightarrow w_2$ ||  -  |  $|w_1| \le |w_2|$  |  $|w_1| \le |w_2|$ \\ $w_1$ Exakt eine Variable  ||  $|w_1| \le |w_2|$ \\ $w_1$ Exakt eine Variable \\ $V \rightarrow t$ oder $V \rightarrow tV$  |
^                             Produktionsgröße ||   kann schwanken    |          monoton Steigend              ||||
^                     Probleme ^          Wort~ |  semi-entscheidbar  |  entscheidbar \\ O($2^n$) NP-hart  |  entscheidbar \\ O(n³)  |  entscheidbar \\ O(n)  |  entscheidbar \\ O(n)  |
^                          ::: ^     Leerheits~ |             nicht entscheidbar                          ||                                entscheidbar                             |||
^                          ::: ^  Endlichkeits~ |                    nicht entscheidbar                   ||                                entscheidbar                             |||
^                          ::: ^    Äquivalenz~ |                    nicht entscheidbar                                            |||      entscheidbar      |  entscheidbar \\ NP-hart  |
^                          ::: ^       Schnitt~ |                                         nicht entscheidbar                                           ||||         entscheidbar       |
^  Abschluss- \\ Eigenschaften ^    Vereinigung |   Ja   |   Ja   |   Ja   |  Nein  |   Ja   |
^                          ::: ^        Schnitt |   Ja   |   Ja   |  Nein  |  Nein  |   Ja   |
^                          ::: ^     Kompliment |  Nein  |   Ja   |  Nein  |   Ja   |   Ja   |
^                          ::: ^        Produkt |   Ja   |   Ja   |   Ja   |  Nein  |   Ja   |
^                          ::: ^          Stern |   Ja   |   Ja   |   Ja   |  Nein  |   Ja   |
^                                   Syntaxbaum ||        -       ||       Ja       ||  Ja \\ (String nach links/rechts)  |
^                               (Extended) BNF ||        -       ||       Ja               |||
==== Typ 3 ====
DFA <=> NFA <=> Typ(L) =3

**Satz von Kleene** Die Menge der durch //reguläre Ausdrücke// beschreibbaren Sprachen //ist genau// die Menge der //regulären Sprachen//.

  * Hat kein gedächtniss
  * Kann minimal gemacht werden
  * Kann eindeutig gemacht werden (Minimal)

=== Grammatik -> DFA ===
  - Grammatik -> NFA
  - NFA -> DFA

=== Grammatik -> NFA ===
== Gegeben ==
$G = (V, \Sigma, P, S)$
== Ergebniss ==
$M = (V \cup \{X\}, \Sigma, \delta, \{S\}, E)$

mit

\[
E = \begin{cases}
\{S, X\} & \text{ wenn } S \rightarrow \epsilon \in P \\
\{X\} & \text{ sonst }
\end{cases}
\]

mit

^  Grammatik \\ Regel  ^  NFA Produktions- \\ Regel  ^
| A -> aB | $\delta(A, a) = B$ |
| A -> a | $\delta(A, a) = X$ |

=== NFA -> DFA ===
$M' = (Z', \Sigma, \delta', z_0, E')$
mit
  * $Z' = \mathcal P(Z)$
  * $z_0' = "S"$ z.B. "{$S_1, S_2, S_3$}"
  * $E'$ alle $Z'$ die //mindestens einen// der alten Endzustände enthalten.

Danach: Aufräumen (alle nicht erreichbaren knoten löschen)

=== Pumping Leamma ===
== Schlüsse ==
Typ 3 Sprachen $\subset$ Pumping Lemma $\subset$ Sprachen

"Mehr Sprachen erfüllen das Pumping Leamma als in T3 sind."

  * $L     \in T3 \Rightarrow L \in PL$
  * $L \not\in T3 \Rightarrow L \in PL \vee L \not\in PL$
  * $L     \in PL \Rightarrow L \in T3 \vee L \not\in T3$
  * $L \not\in PL \Rightarrow L \in T3$

== Bedingungen ==
Für alle Wörter $x = uvw$, die mindestens $n$ lang sind muss gelten:
| $|v| \ge 1$ | u**v**w muss existieren |
| $|uv| \le n$ | **uv**w mindestens n lang |
| $uv^iw \in L \forall i \ge 0$ | u**v**w pumpbar |

== Beweisidee ==
Mit $x = uvw$ beliebig, aber von $n$ abhängig, einen Widerspruch in den Regeln herbeiführen.

=== Minimalautomat ===
{{:users:skruppy:ext:uni:4:foo.png?150|}}

Achte auf den Versatz von Zeilen und Spalten!

^  Unmarkierte \\ Zustände  ^  $\sigma_1$  ^  $\sigma_2$  ^  ...  ^  Ergebniss  ^
|  {0,1}  | $\{\delta(0, \sigma_1), \delta(1, \sigma_1)\} \times$ | $\{\delta(0, \sigma_2), \delta(1, \sigma_2)\} \checkmark$ | | Markieren |
|  **{0,2}**  | $\{\delta(0, \sigma_1), \delta(2, \sigma_1)\} \times$ | $\{\delta(0, \sigma_2), \delta(2, \sigma_2)\} \times$ | | Zusamenfassen |
|  {0,3}  | $\{\delta(0, \sigma_1), \delta(3, \sigma_1)\} \checkmark$ |  -  | | Markieren |
|  {1,2}  | $\{\delta(1, \sigma_1), \delta(2, \sigma_1)\} \checkmark$ |  -  | | Markieren |
|  **{1,3}**  | $\{\delta(1, \sigma_1), \delta(3, \sigma_1)\} \times$ | $\{\delta(1, \sigma_2), \delta(3, \sigma_2)\} \times$ | | Zusamenfassen |
|  {2,3}  | $\{\delta(2, \sigma_1), \delta(3, \sigma_1)\} \checkmark$ |  -  | | Markieren |

  - Alle Paare parkieren wo ein $\in E$ das andere nicht (XOR).
  - Loop über Tabelle
    * Wenn Ergebnis markiert, markiere auch diese
  - Unmarkierte zusamenfassen


==== Typ 2 ====
  * Typ(L) <=> nichtdeterministischer Kellerautomat
  * deterministisch kontextfreie Sprache <=> deterministischer Kellerautomat
  * deterministisch kontextfreie Sprachen $\subset$ kontextfreie Sprachen
=== Chomsky Normalform (CNF) ===
Nur
  * A -> a
  * A -> CD

=> Ableitungsbaum = Binärbaum

  - $\epsilon$-Produktionen entfernen.
  - ''A -> a'' für jede Konstante einfüren
  - ''U -> Xyz'' => ''U -> XYZ'' \\ Konstanten durch Variablen in allen alten Regeln ersetzen
  - ''U -> XYZ'' => ''U -> XV'' & ''V -> YZ'' \\ Aufsplitten wenn rechte Seite länger als 2
  - ''X -> Y'' & ''Y -> X'' => Überall ''X'' und ''Y'' druch ''Z'' ersetzen \\ Zyklen entfernen
  - Ketten entfernen (von hinten)

=== Greibach Normalform (GNF) ===
Nur
  * $A \rightarrow aB_1B_2B_3 \dots B_k$ (Mindestens 2 ''B'')

=== Pumping Leamma ===
== Bedingungen ==
Für alle Wörter $x = uvwxy$, die mindestens $n$ lang sind muss gelten:
| $|vx| \ge 1$ | u**v**w**x**y eins von beiden muss existieren |
| $|vwx| \le n$ | u**vwx**y mindestens n lang |
| $uv^iwx^iy \in L \forall i \ge 0$ | u**v**w**x**y pumpbar |

== Beweisidee ==
Mit $x = uvwxy$ beliebig, aber von $n$ abhängig, einen Widerspruch in den Regeln herbeiführen.

=== Grammatik -> Kellerautomat ===
$G = (V, \Sigma, \delta, S)$ => $M = (\{z\}, \Sigma, V \cup \Sigma, \delta, z, S)$
  - Nur ein Zustand ''z''
  - Startvariable ''S'' der //Grammatik// wird zu unterstem Kellerelement (entspricht #)
  - Für jede Produktion ''A -> Xyz'' ergänze Produktion $(z, \epsilon, A) \rightarrow (u, Xyz)$ \\ (Mache Variablenableitungen (Auflösungen) im Keller)
  - Für jedes $a \in \Sigma$ ergänze Produktion $(z, a, a) \rightarrow (z, \epsilon)$ \\ (Wenn Keller und Wort übereinstimmen, lösche sie)

=== CYK-Algorithmus ===
CNF Normalform

{{:users:skruppy:ext:uni:4:fsk:cyk.jpg|}}
==== Typ 1 ====
Typ(L) = 1 <=> Nicht deterministische, linear beschränkte TM

Wort ist akzeptiert wenn TM
  * //hält//
  * in //Endzustand//
  * (Band ist egal)


=== Church-Turing-These ===
Alles was man "intuitiv" berechnen kann, kann man auch mit einer Turingmaschine berechnen.

=== Kuroda Normalform ===
Nur
  * A -> a
  * A -> CD
  * A -> C **(neu)**
  * AB -> CD **(neu)**

=> Ableitungsbaum = Binärbaum

  - $\epsilon$-Produktionen entfernen.
  - ''A -> a'' für jede Konstante einfüren
  - ''U -> Xyz'' => ''U -> XYZ'' \\ Konstanten durch Variablen in allen alten Regeln ersetzen
  - $A_1A_2A_3 \rightarrow B_1B_2B_3B_4B_5$ \\ $\Rightarrow$ \\ $A_1A_2 \rightarrow B_1X_1$ \\ $X_1A_3 \rightarrow B_2X_2$ \\ $X_2 \rightarrow B_3X_3$ \\ $X_3 \rightarrow B_4B_5$  \\ Aufsplitten wenn rechte Seite länger als 2 **(neu)**
  - ''U -> XYZ'' => ''U -> XV'' & ''V -> YZ'' \\ Aufsplitten wenn rechte Seite länger als 2
  - ''X -> Y'' & ''Y -> X'' => Überall ''X'' und ''Y'' druch ''Z'' ersetzen \\ Zyklen entfernen
  - Ketten entfernen (von hinten)

==== Typ ====
Typ(L) = 0 <=> (Nicht) deterministische TM

Wort ist akzeptiert wenn TM
  * //hält//
  * in //Endzustand//
  * (Band ist egal)
===== Probleme =====
==== Wortproblem (Sprache) ====
== Gefragt ==
"Ist Wort in Sprache?"

== Beweis ==
Typ 2: CYK

==== Leerheitsproblem (Sprache) ====
== Gefragt ==
"Gibt es akkzeptierte Wörter?"

== Beweis ==
Kein Pfad von Start zu Ende.


==== Endlichkeitsproblem (Sprache) ====
== Gefragt ==
"Gibt es nur endlich viele Wörter?"

== Beweis ==
Zyklus


==== Schnittproblem (Sprache) ====
== Gefragt ==
"Haben zwei Sprachen die selben Wörter?"

== Beweis ==
  - $L = L_1 \cap L_2$
  - Leerheitsproblem von $L$


==== Äquivalenzproblem (Sprache) ====
== Gefragt ==
"Sind zwei Sprachen gleich?"

== Beweis ==
Typ 3: Isomorphie von Minimalautomaten


==== (Allgemeines) Halteproblem ====
== Gegeben ==
  * TM (codiert)
  * Eingabe

== Gefragt ==
"Hält das Programm?"

== Entscheidbarkeit ==
nicht entscheidbar & semi-entscheidbar


==== Spezielles Halteproblem ====
== Gegeben ==
  * TM (codiert)

== Gefragt ==
"Hält das Programm auf sich selbst angewendet?"

== Entscheidbarkeit ==
nicht entscheidbar & semi-entscheidbar


==== Leerband TM ====
== Gegeben ==
  * TM (codiert)

== Gefragt ==
"Hält das Programm auf leerem Band?"

== Entscheidbarkeit ==
nicht entscheidbar & semi-entscheidbar


==== Satz von Rice ====
== Gegeben ==
  * Sei $R = \{g \mid g \text{Truing berechenbar}\}$ \\ Unendliche und konstante Menge an Funktionen
  * Sei $S \subset R$ mit $\emptyset \neq S \neq R$ \\ Gewünschtest funktionales Verhalten einer TM verhalten

== Gefragt ==
"Berechnet die TM $M_w$ mindestens eine Funktion aus ''S''?"

== Entscheidbarkeit ==
nicht entscheidbar (semi-entscheidbar?)


==== Postsche Korrespondenzproblem (PCP) ====
== Gegeben ==
  * Endliche Folge von ''n'' Tupeln (Dominosteinen) $(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)$ mit $x_i, y_i \in \Sigma^+$ (Ohne 𝞮)

== Gefragt ==
"Gibt es eine Folge $i_1, i_2, \dots i_n$ so dass $x_{i_1} x_{i_2} \dots x_{i_n} = y_{i_1} y_{i_2} \dots y_{i_n}$ (obere Zeile = untere Zeile)?"

== Entscheidbarkeit ==
nicht entscheidbar und semi-entscheidbar


==== Erfüllbarkeitsproblem der Aussagenlogik (SAT) ====
== Gegeben ==
  * Endliche Folge von ''n'' Tupeln (Dominosteinen) $(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)$ mit $x_i, y_i \in \Sigma^+$ (Ohne 𝞮)

== Gefragt ==
"Gibt es eine Belegung, so das ''F'' erfüllbar ist?"

== Härte ==
SAT ∈ NP


===== Abschlusseigenschaften =====
Wenn $L_1$ und $L_2$ von Typ $n$. Ist dann auch $L_1 \text{op} L_2$ vom Typ $n$.

==== Vereinigung ====
$L_1 \cup L_2$

Typ 3: ''L|K''

==== Schnitt ====
$L_1 \cap L_2 = C(C(L_1) \cup C(L_2))$

Typ 3: ''L|K''

==== Komplement ====
$C(L) = \Sigma^* \setminus L$

Vertausche Endzustände mit nicht Endzuständen.

==== Produkt ====
Konkatenation

Typ 3: ''LK''

==== Stern ====
Wiederholung

Typ 3: ''L*''
===== Notationen =====
==== Grammatik ====
  * Regelsystem
  * Ausgehend von //Startsymbol//
  * Ableiten/komplexer werden $u \Rightarrow_G v$

$G = (V, \Sigma, P, S)$

^ FZ ^ Art ^ Heist ^ Besteht aus ^
| $V$ | Menge | | Variablen/nicht-Terminalsymbolen |
| $\Sigma$ | Menge | Alphabet/Signatur | Konstanten / Terminalsymbolen |
| $P$ | Menge | | Produktionsregeln |
| $S$ | Element | Startsymbol ||
| $\epsilon$ | Element | leere Sequenz ||

$S \in \Sigma$

  * Relation \\ $u \Rightarrow_G v$
  * Reflexiv-transitive Relation \\ $S \Rightarrow_G^* w$

$L(G) = L$

  * Es ist nicht vorgeschrieben, das von links ersetzt wird.
  * Sind mehrere Ableitungen möglich => Nicht deterministisch
==== Mathematische Notation ====
//Ist direkt menge und damit Sprache.//

$L = \{a^nb^n | n > 0\}$

==== ??? ====
//???//
| $ab$    | Konkatination |
| $\{a,b\}$ | Auswahl |
| $a^n$   | $n$ Mal |
| $a^*$   | $0-\infty$ Mal |
| $a^+$   | $1-\infty$ Mal |
| $a?$    | $0-1$ Mal |
| $\epsilon$    | Leeres Wort |

==== (Extended) Backus-Naur-Form ====
Nur Typ 2 und 3
| ''%%a|b%%'' | Auswahl |
| ''[a]'' | $0-1$ Mal |
| ''{a}'' | $0-\infty$ Mal |

==== Regulärer Ausdruck ====
Nur Typ 3

| $\emptyset$ | Leere Sprache (Menge) |
| $\epsilon$ | Leeres Wort (Element) |
| $a \in \Sigma$ | Konstante |
| $ab$ | Konkatination |
| $(a|b)$ | Auswahl |
| $(a)^*$ | $0-\infty$ Mal |
===== Entscheidungsverfahren =====
==== Parser ====
%%=%% Programm
==== Automaten ====
Nicht deterministisch => Backtracking

^  Typ  ^  Äquivalent  ^
|   3   |   Ja   |
|   2   |  Nein  |
|   1   |   ?    |
|   0   |   Ja   |

=== DFA ===
  * **DFA** \\ Deterministic Finite Automaton
  * **DEA** \\ Deterministischer Endlicher Automat

$M = (Z, \Sigma, \delta, z_0,E)$

^ FZ ^ Art ^ Heist ^ Besteht aus ^ Bedingung ^
| $Z$ | Menge | | Zuständen | $z_0 \in Z$ |
| $\Sigma$ | Menge | //Eingabe//alphabet | Konstanten / Terminalsymbolen | |
| $z_0$ | //Element// | Startzustand  || $z_0 \in Z$ |
| $E$ | Menge | | Endzustände | $E \subseteq Z$ |
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Sigma \rightarrow Z$ || total (überall Def.) |

== Konfiguration ==
Tupel $(z_i, v)$
  * $z_i$ \\ Zustand
  * $v$ \\ Restwort

$(z_0, \text{foo}) \rightarrow (z_1, \text{oo}) \rightarrow (z_2, \text{o}) \rightarrow (z_2, \epsilon)$

=== NFA ===
  * **NFA** \\ Nondeterministic Finite Automaton
  * **NEA** \\ Nichtdeterministischer Endlicher Automat

$M = (Z, \Sigma, \delta, S,E)$

^ FZ ^ Art ^ Heist ^ Besteht aus ^ Bedingung ^
| $Z$ | Menge | | Zuständen | $z_0 \in Z$ |
| $\Sigma$ | Menge | //Eingabe//alphabet | Konstanten / Terminalsymbolen | |
| $S$ | //Menge// | | Startzustände  | $S \subseteq Z$ |
| $E$ | Menge | | Endzustände | $E \subseteq Z$ |
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Sigma \rightarrow \mathcal P(Z)$ || total (überall Def.) |

== Konfiguration ==
Tupel (z, v)
  * z:  Zustand
  * v: Restwort

$(z_0, \text{foo}) \rightarrow (z_1, \text{oo}) \rightarrow (z_2, \text{o}) \rightarrow (z_2, \epsilon)$

=== Kellerautomat ===
  * Kellerautomat
  * Push-Down Automaton (PDA)

$\epsilon$-Übergang => Nichtdeterministisch (es gibt aber auch weitere Fälle)

$M = (Z, \Sigma, \Gamma, \delta, z_0, \#)$

^ FZ ^ Art ^ Heist ^ Besteht aus ^ Bedingung ^
| $Z$ | Menge | | Zuständen | $z_0 \in Z$ |
| $\Sigma$ | Menge | //Eingabe//alphabet | Konstanten / Terminalsymbolen | |
| $\Gamma$ | Menge | //Keller//alphabet | | $\# \in \Gamma$ \\ Es kann $\Gamma \ne \Sigma$ gelten |
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Sigma \rightarrow \mathcal P(Z)$ || total (überall Def.) |
| $z_0$ | Element | Startzustand  || $z_0 \in Z$ |
| # | Element | Unterstes Kellerelement || $\# \in \Gamma$ |

(Keine Endzustände)

== Start ==
Keller //leer// oder //#//.

== Ende ==
Akzeptiert
  * Restwort leer
  * Keller leer

Nicht Akzeptiert
  * sonst

== Übergang ==
$(z, \sigma, S_1) \rightarrow (z', S_1'S_2'...)$

| $(z, \sigma, S_1) \rightarrow (z', )$ | POP() |
| $(z, \sigma, S_1) \rightarrow (z', S_nS_1)$ | PUSH($S_n$) |
| $(z, \textbf{$\epsilon$}, S_1) \rightarrow (z', S_1'S_2'...)$ | Restwort bleibt unverändert |
| $(z, \sigma, \textbf{$\epsilon$}) \rightarrow (z')$ | Restwort und Keller bleiben unverändert |

Vereinfacht
  * $\sigma, S_1: \text{POP}()$
  * $\sigma: \text{PUSH}(S_\text{neu})$ (Achtung: Top of Stack egal)

== Konfiguration ==
Tupel (z, v, K)
  * z: Zustand
  * v: Restwort
  * K: Kellerinhalt $(S_1, S_2, ...)$

$(z_0, \text{foo}, (\#)) \rightarrow (z_1, \text{oo}, (x\#)) \rightarrow (z_2, \text{o}, (\#)) \rightarrow (z_2, \epsilon, ())$

  * $S_1$ = neustes Stackelement

=== Turingmaschiene ===
Deterministische TM <=> Nichtdeterministische TM

$M = (Z, \Sigma, \Gamma, \delta, z_0, \square, E)$

^ FZ ^ Art ^ Heist ^ Besteht aus ^ Bedingung ^
| $Z$ | Menge | | Zuständen | $z_0 \in Z$ \\ $E \subseteq Z$ |
| $\Sigma$ | Menge | //Eingabe//alphabet | Konstanten / Terminalsymbolen | $\Sigma \subset \Gamma$ |
| $\Gamma$ | Menge | //Arbeits//alphabet | | $\square \in \Gamma$ \\ $\Sigma \subset \Gamma$ |
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Gamma \rightarrow Z \times \Gamma \times \{\text{L}, \text{R}, \text{N}\}$ (D) \\ Überführungsfunktion $\delta: Z \times \Gamma \rightarrow \mathcal P(Z \times \Gamma \times \{\text{L}, \text{R}, \text{N}\})$ (ND) || total (überall Def.) |
| $z_0$ | Element | Startzustand  || $z_0 \in Z$ |
| $\square$ | Element | Blank || $\square \in \Gamma$ |
| E | Menge | | Endzustände | $E \subseteq Z$ |

== Übergang ==
$(z, \sigma) \rightarrow (z', \sigma', m)$

Für ''m''
  * **L** Links
  * **N** Neutral (stehen bleiben)
  * **R** Rechts

== Konfiguration ==
Tupel $(\alpha z \beta)$
  * $\alpha$: //Links// vom Lesekopf
  * z: Zustand
  * $\beta$: //Unterm// und //rechts// vom Lesekopf

== Linear beschränkt ==
Der Lesekopf //liest// noch //nicht// mal $\square$
  * Zu keiner Zeit
  * Bei jedem Startband

  * //Linken// Rand kann man sich //in Zustand merken// oder selber //markieren//
  * //Rechter// Rand wir mit //zusätzlichem// Zeichen //markiert//

^  Eigentlicher Bandinhalt | $a_1a_2a_3a_4$ |
^    Markierter Bandinhalt | $a_1a_2a_3a_4\hat a_4$ |