Theo

Teil 1: Formale Sprachen

1. Grundbegriffe:

• Alphabet
  $\mathrm{\Sigma }$: Endliche Menge
• Wort / String über
  $\mathrm{\Sigma }$: endliche Folge von Zeichen aus
  $\mathrm{\Sigma }$
• |w|: Länge des Wortes w
• Leeres Wort:
  $ϵ$
• u, v: wörter -> uv: Konkatenation
• w: wort, wⁿ definiert durch: w⁰ =
  $ϵ$, wⁿ⁺¹ = wwⁿ
• ${\mathrm{\Sigma }}^{\ast }$: Menge aller Wörter über
  $\mathrm{\Sigma }$
• Teilmenge
  $L\subseteq {\mathrm{\Sigma }}^{\ast }$: (formale) Sprache

Operationen auf Sprachen

Seien

$A,B\subseteq {\mathrm{\Sigma }}^{\ast }$

• Konkatenation: AB =
  $\{uv|u\in A\wedge v\in B\}$
• Merke: {ab,b}
  $\times$ {a,bb} = {(ab,a),(ab,bb),(b,a),(b,bb)}
• $A^n$ =
  $\{w_1\cdots w_n|w_1,\dots ,w_n\in A\}$ =
  $A\cdots A$
• $A^{\ast }$ =
  $\{w_1\cdots w_n|n\ge 0\wedge w_1,\dots ,w_n\in A$} =
  $\bigcup _{n\in \mathbb{N}}{A}^n$
• $A^{+}$ =
  $A{A}^{\ast }$ =
  $\bigcup _{n\ge 1}{A}^n$
  Achtung: für alle A:
  $ϵ\in A^{\ast }$,
  ${\mathrm{\varnothing }}^{\ast }=\{ϵ\}$

Einige Rechenregeln

• $\mathrm{\varnothing }A=\mathrm{\varnothing }$
• $\{ϵ\}A=A$
• $A(B\cup C)=AB\cup AC$
• $(A\cup B)C=AC\cup BC$
• $A^{\ast }{A}^{\ast }=A^{\ast }$
  Achtung: i.A. gilt
  $A(B\cap C)=AB\cap AC$ nicht.

1.1 Grammatiken

Eine Grammatik ist ein 4-Tupel G = (V,

$\mathrm{\Sigma }$, P, S), wobei:

• V: endliche Menge von Nichtterminalen
• $\mathrm{\Sigma }$: endliche Menge von Terminalen, disjunkt von V, auch Alphabet genannt
• $P\subseteq (V\cup \mathrm{\Sigma }{)}^{\ast }\times (V\cup \mathrm{\Sigma }{)}^{\ast }$: Endliche Menge von Produktionen
• S
  $\in$ V: Startsymbol

Eine Grammatik G = (V,

$\mathrm{\Sigma }$, P, S) induziert eine Ableitungsrelation

${\to }_G$ auf Wörtern über V

$\cup \mathrm{\Sigma }$

$\alpha {\to }_G{\alpha }^{\prime }⟺\mathrm{\exists }$ eine Regel

$\beta \to {\beta }^{\prime }$ in P und Wörter

${\alpha }_1,{\alpha }_2$, sodass:

$\alpha ={\alpha }_1\beta {\alpha }_2$ und

${\alpha }^{\prime }={\alpha }_1{\beta }^{\prime }{\alpha }_2$
Eine Sequenz

${\alpha }_1{\to }_G\cdots {\to }_G{\alpha }_n$ ist eine Ableitung von

${\alpha }_n$ aus

${\alpha }_1$
Wenn

${\alpha }_1=S$ und

${\alpha }_n\in {\mathrm{\Sigma }}^{\ast }$, dann erzeugt G das wort

${\alpha }_n$
Sprache von G: L(G): Menge aller wörter, die von G erzeugt werden

1.2 Chomsky-Hierarchie

Eine Grammatik G ist vom
Typ 0: Immer
Typ 1: falls für jede Produktion

$\alpha \to \beta$ außer

$S\to ϵ$ gilt:

$|\alpha |\le |\beta |$
Typ 2: falls G vom Typ 1 ist und für jede Produktion

$\alpha \to \beta$ gilt:

$\alpha \in V$
Typ 3: falls G vom Typ 2 ist und für jede Produktion

$\alpha \to \beta$ außer

$S\to ϵ$ gilt:

$\beta \in \mathrm{\Sigma }\cup \mathrm{\Sigma }V$
Offensichtlich: Typ 3

$\subset$ Typ 2

$\subset$ Typ 1

$\subset$ Typ 0

Grammatiken und Sprachklassen:
Typ 3: Rechtslineare Grammatik: Reguläre Sprachen
Typ 2: Kontextfreie Grammatik: Kontextfreie Sprachen
Typ 1: Kontextsensitive Grammatik: Kontextsens. Sprachen
Typ 0: Phasenstrukturgrammatik: Rekursiv aufzählbare Sprachen

L(Typ 3)

$\subset$ L(Typ 2)

$\subset$ L(Typ 1)

$\subset$ L(Typ 0)

2. Reguläre Sprachen

2.1 Deterministische endliche Automaten (DFAs)

Ein DFA

$M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ besteht aus:

• einer endlichen Menge an Zuständen Q
• einem (endlichen) Eingabealphabet
  $\mathrm{\Sigma }$
• einer (totalen) Übergangsfunktion
  $\delta :Q\times \mathrm{\Sigma }\to Q$
• einem Startzustand
  $q_0\in Q$
• einer Menge
  $F\subseteq Q$ von Endzuständen
• TODO: carlos camino DFA
  Eine Sprache ist regulär gdw. sie von einem DFA akzeptiert wird

2.2 Nichtdeterministische endliche Automaten (NFAs)

Ein NFA ist ein 5-Tupel

$N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$, so dass:

• $Q,\mathrm{\Sigma },q_0$ und
  $F$ sind wie bei einem DFA
• $\delta :Q\times \mathrm{\Sigma }\to P(Q)$
  
  $P(Q)$ = Menge aller Teilmengen von
  $Q=2^Q$
  Alternative: Relation
  $\delta \subseteq Q\times \mathrm{\Sigma }\times Q$
• TODO: carlos camino NFA

2.3 Äquivalenz von NFA und DFA

Für jeden NFA N gibt es einen DFA M mit L(N) = L(M)
Für einen NFA mit n Zuständen kann der entsprechende DFA bis zu 2ⁿ Zustände haben

2.4 NFAs mit

$ϵ$-Übergängen

• Diese Erweiterung von NFAs macht sie nicht mächtiger
• Aber man kann manche Sprachen einfacher beschreiben als nur mit NFAs

Ein NFA mit

$ϵ$-Übergängen auch

$ϵ$-NFA ist ein NFA mit einem speziellen Symbol

$ϵ\notin \mathrm{\Sigma }$ und mit

$\delta :Q\times (\mathrm{\Sigma }\cup \{ϵ\})\to P(Q)$
Ein

$ϵ$-Übergang darf ausgeführt werden, ohne dass ein Eingabezeichen gelesen wird
Formal:

$ϵ$-NFA

$N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ als kompakte Repräsentation eines

$ϵ$-freien NFA

$N^{\prime }=(Q,\mathrm{\Sigma },{\delta }^{\prime },q_0,F^{\prime })$
Per Definition: Jeder

$ϵ$-NFA ist äquivalent zu einem NFA

• TODO: carlos camino EDFA

Fazit: Die Automatentypen

• DFA
• NFA
• $ϵ$-NFA

sind gleich mächtig

2.5 Rechtslineare Grammatiken

rechtslineare Grammatiken haben nur Produktionen der Form

$A\to a,A\to aB$ und

$S\to ϵ$
Für jeden DFA M gibt es eine rechtslineare Grammatik G mit

$L(M)=L(G)$
Für jede rechtslineare Grammatik G gibt es einen NFA M mit

$L(G)=L(M)$

$\to$ das bedeutet auch: für jede rechtslineare Grammatik G gibt es einen DFA M mit

$L(G)=L(M)$

• TODO: carlos camino RLG

2.6 Reguläre Ausdrücke

Reguläre Ausdrücke sind eine weitere Notation für die Definition von formalen Sprachen, und sind induktiv definiert:

• $\mathrm{\varnothing }$ ist ein RE
• $ϵ$ ist ein RE
• für jedes
  $a\in \mathrm{\Sigma }$ ist a ein regulärer Ausdruck
• Wenn
  $\alpha$ und
  $\beta$ reguläre ausdrücke sind, dann auch:
  • $\alpha \beta$
  • $\alpha |\beta$, (oft
    $\alpha +\beta$ geschrieben)
  • ${\alpha }^{\ast }$

Nichts sonst ist ein regulärer Ausdruck
Notation:

• Reguläre Ausdrücke können bzw. müssen geklammert werden
• Bindungsstärke: * stärker als Konkatenation stärker als |
• $a{b}^{\ast }=a(b^{\ast })\ne (ab{)}^{\ast }$
• $ab|c=(ab)|c\ne a(b|c)$

Sprache

$L(\gamma )$ eines regulären Ausdrucks

$\gamma$ ist rekursiv definiert:

• $L(\mathrm{\varnothing })=\mathrm{\varnothing }$
• $L(ϵ)=\{ϵ\}$
• $L(a)=\{a\}$
• $L(\alpha \beta )=L(\alpha )L(\beta )$
• $L(\alpha |\beta )=L(\alpha )\cup L(\beta )$
• $L({\alpha }^{\ast })=L(\alpha {)}^{\ast }$

Satz von Kleene: Eine Sprache

$L\subseteq {\mathrm{\Sigma }}^{\ast }$ ist genau dann durch einen regulären Ausdruck darstellbar, wenn sie regulär ist.

• TODO: NFA Konstruktion, Carlos Camino Cleene

Konversionen auf einen Blick:

• $ϵ$-NFA
  $\to$ NFA: Q ~> Q
• NFA
  $\to$ DFA: n Zustände ~> O(2ⁿ) Zustände
• NFA / DFA
  $\to$ RE: n Zustände ~> RE der Länge O(n4ⁿ)
• RE
  $\to$
  $ϵ$-NFA: RE der Länge n ~> O(n) Zustände

2.7 Abschlusseigenschaften regulärer Sprachen

Seien

$R,R_1,R_2\subseteq {\mathrm{\Sigma }}^{\ast }$ Reguläre Sprachen. Dann sind auch:

• $R_1{R}_2$
• $R_1\cup R_2$
• $R^{\ast }$
• $\bar{R}$
  $(:={\mathrm{\Sigma }}^{\ast }\mathrm{\setminus }R)))$
• $R_1\cap R_2$
• $R_1\mathrm{\setminus }{R}_2$

Reguläre Sprachen.
Bemerkung: Komplementierung

$(\bar{R})$ durch vertauschen von Endzuständen und Nicht-Endzuständen funktioniert nur bei DFAs, nicht bei NFAs!

Produkt-Konstruktion: Durchschnitt direkt auf DFAs, ohne Umweg via de Morgan. Beide DFAs laufen synchron parallel, Wort wird akzeptiert wenn beide DFAs akzeptieren.
Parallelismus = Kreuzprodukt der Zustandsräume

Die Umkehrung (Spiegelung) von

$w=a_1\dots a_n$ ist

$w^R:=a_n\dots a_1$
Die Umkehrung einer Sprache

$A$ ist

$A^R:=\{w^R|w\in A\}$
Ist

$A$ eine reguläre Sprache, dann auch

$A^R$

2.8 Rechnen mit regulären Ausdrücken

Zwei reguläre Ausdrücke sind äquivalent gdw. sie die gleiche Sprache darstellen:

$$\alpha \equiv \beta :⟺L(\alpha )=L(\beta )$$

Null und Eins

• $\mathrm{\varnothing }|\alpha \equiv \alpha |\mathrm{\varnothing }\equiv \alpha$
• $\mathrm{\varnothing }\alpha \equiv \alpha \mathrm{\varnothing }\equiv \mathrm{\varnothing }$
• $ϵ\alpha \equiv \alpha ϵ\equiv \alpha$
• ${\mathrm{\varnothing }}^{\ast }\equiv ϵ$
• ${ϵ}^{\ast }\equiv ϵ$

Assoziativität:

• $(\alpha |\beta )|\gamma \equiv \alpha |(\beta |\gamma )$
• $(\alpha \beta )\gamma \equiv \alpha (\beta \gamma )$

Kommutativität

• $\alpha |\beta \equiv \beta |\alpha$

Distributivität

• $\alpha (\beta |\gamma )\equiv \alpha \beta |\alpha \gamma$
• $(\alpha |\beta )\gamma \equiv \alpha \gamma |\beta \gamma$

Idempotenz:

• $\alpha |\alpha \equiv \alpha$

Stern:

• $ϵ|\alpha {\alpha }^{\ast }\equiv {\alpha }^{\ast }$
• ${\alpha }^{\ast }\alpha \equiv \alpha {\alpha }^{\ast }$
• $({\alpha }^{\ast }{)}^{\ast }\equiv {\alpha }^{\ast }$

Satz von Redko: Es gibt keine endliche Menge von gültigen Äquivalenzen aus denen sich alle gültigen Äquivalenzen herleiten lassen.

2.9 Pumping Lemma für Reguläre Sprachen

AKA: Wie zeigt man, dass eine Sprache nicht regulär ist?

Sei

$R\subseteq {\mathrm{\Sigma }}^{\ast }$ regulär. Dann gibt es ein n > 0, so dass sich jedes

$z\in R$ mit

$|z|\ge n$ so in

$z=uvw$ zerlegen lässt, dass:

• $v\ne ϵ$
• $|uv|\le n$
• $\mathrm{\forall }i\ge 0.u{v}^{i}w\in R$
• TODO: understand pumping lemma, carlos camino pumping lemma

Bemerkung:
Es gibt nicht-reguläre Sprachen, für die das Pumping-Lemma gilt!

$⟹$ Pumping-Lemma hinreichend aber nicht notwendig um Nicht-Regularität zu zeigen
regulär

$\subset$ Pumping-Lemma gilt

$\subset$ alle Sprachen

2.10 Entscheidungsverfahren

Entscheidungsprobleme für reguläre Sprachen, d.h. Probleme der Gestalt

• Eingabe: Ein oder mehrere Objekte, die reguläre Sprachen beschreiben (DFA, NFA, RE, Typ 3 Grammatik, etc.)
• Frage: Haben diese Objekte die Eigenschaft X?

Ein (Entscheidungs)Problem ist entscheidbar, wenn es einen Algorithmus gibt, der bei jeder Eingabe in endlicher Zeit die richtige Antwort gibt.
Nicht alle Entscheidungsprobleme für Grammatiken sind entscheidbar

Sei D ein DFA, NFA, RE, rechtslineare Grammatik, etc.

• Wortproblem: Gegeben w und D, gilt
  $w\in L(D)$?
  • Entscheidbar in
    $O(|w|+|M|)$ für Wort w und DFA M
  • Entscheidbar in
    $O(|Q{|}^2|w|+|N|)$ für Wort w und NFA N
• Leerheitsproblem: Gegeben D, gilt
  $L(D)=\mathrm{\varnothing }$?
  • Entscheidbar in
    $O(|Q||\mathrm{\Sigma }|)/O(|Q^2||\mathrm{\Sigma }|)$ für DFAs/NFAs
• Endlichkeitsproblem: Gegeben D, ist L(D) Endlich?
  • Entscheidbar für DFAs oder NFAs
• Äquivalenzproblem: Gegeben
  $D_1,D_2$, gilt
  $L(D_1)=L(D_2)$?
  • Entscheidbar für DFAs in Zeit
    $O(|Q_1||Q_2||\mathrm{\Sigma }|)$
  • Entscheidbar für NFAs in Zeit
    $O(2^{|Q+1|+|Q_2|})$, bei fixem $\Sigma
  • Entscheidbar für reguläre Ausdrücke

Fazit: Die Kodierung der Eingabe (DFA, NFA, RE, etc.) kann entscheidend für die Komplexität eines Problems sein

2.11 Automaten und Gleichungssysteme

Ardens Lemma:
Sind

$A,B$ und

$X$ Sprachen mit

$ϵ\notin A$, so gilt

$$X=AX\cup B⟹X=A^{\ast }B$$

Korollar
Sind

$\alpha ,\beta$ und

$X$ reguläre Ausdrücke mit

$ϵ\notin L(\alpha )$, so gilt

$$X\equiv \alpha X|\beta ⟹X\equiv {\alpha }^{\ast }\beta$$
Bemerkungen:

• $X=ϵX\cup B$ hat keine eindeutige Lösung: jede Sprache
  $X\supseteq B$ ist Lösung
• $X\equiv aXb|ϵ$ hat keine reguläre Lösung

2.12 Minimierung endlicher Automaten

Jede reguläre Sprache hat einen einzigen minimalen DFA

Algorithmus zur Minimierung eines DFA

• Entferne alle von
  $q_0$ aus nicht erreichbaren Zustände
• Berechne die äquivalenten Zustände des Automaten
• Kollabiere den Automaten durch Zusammenfassung aller äquivalenten Zustände

Zustäde p und q sind unterscheidbar wenn es

$w\in {\mathrm{\Sigma }}^{\star }$ gibt mit

$\hat{\delta }(p,w)\in F$ und

$\hat{\delta }(q,w)\notin F$
Zustände sind äquivalent wenn sie nicht unterscheidbar sind, d.h. wenn für alle

$w\in {\mathrm{\Sigma }}^{\ast }$ gilt:

$$\hat{\delta }(p,w)\in F⟺\hat{\delta }(q,w)\in F$$

• gilt

  $p\in F$ und
  $q\notin F$, dann sind p und q unterscheidbar

• sind

  $\delta (p,a)$ und
  $\delta (q,a)$ unterscheidbar, dann auch p und q
  
  $⟹$ unterscheidbarkeit pflanzt sich rückwärts fort

• Todo: Folie 107 tabellendings grafik erstellen, einsetzen, algorithmus U

Eine weitere Anwendung: Äquivalenztest von DFAs

• Gegeben DFAs A und B, bilde disjunkte Vereinigung. ("Male A und B nebeneinander")
• Berechne Menge der äquivalenten Zustände
• L(A) = L(B) gdw. die beiden Startzustände äquivalent sind

Formale Definition des "kollabierten Automaten"

Eine Relation

$\approx \subseteq A\times A$ ist eine Äquivalenzrelation falls

• Reflexivität:
  $\mathrm{\forall }a\in A.a\approx a$
• Symmetrie:
  $\mathrm{\forall }a,b\in A.a\approx b⟹b\approx a$
• Transitivität:
  $\mathrm{\forall }a,b,c\in A.a\approx b\wedge b\approx c⟹a\approx c$

Äquivalenzklasse:

$$[a{]}_{\approx }:=\{b|a\approx b\}$$

Es gilt:

$$[a{]}_{\approx }=[b{]}_{\approx }⟺a\approx b$$

Quotientenmenge:

$$A/\approx :=\{[a{]}_{\approx }|a\in A\}$$

Äquivalenz von Zuständen

Intuition: Zwei Zustände sind äquivalent gwd. sie dieselbe sprache erkennen.
Wir schreiben

$\equiv$ statt

${\equiv }_M$ wenn M klar ist
Einfache Fakten:

• ${\equiv }_M$ ist eine Äquivalenzrelation
• $p{\equiv }_{M}q⟹\delta (p,a){\equiv }_M\delta (q,a)$
• Algorithmus U liefert die unterscheidbaren Zustände, also
  $\not\equiv$.

In der weiteren Analyse wird direkt auf

$\equiv$ bezogen, nicht mehr auf den Algorithmus

Die "Kollabierung" von M bzgl.

$\equiv$ ist der Quotientenautomat:

$$\begin{gathered} M/\equiv :=(Q/\equiv ,\mathrm{\Sigma },{\delta }^{\prime },[q_0{]}_{\equiv },F/\equiv ) \\ {\delta }^{\prime }([p{]}_{\equiv },a):=[\delta (p,a){]}_{\equiv } \end{gathered}$$

Die Definition von

${\delta }^{\prime }$ ist wohlgeformt da unabhängig von der Wahl des Repräsentanten p:

$$[p{]}_{\equiv }=[p^{\prime }{]}_{\equiv }⟹p\equiv p^{\prime }⟹\delta (p,a)\equiv \delta (p^{\prime },a)⟹[\delta (p,a){]}_{\equiv }=[\delta (p^{\prime },a){]}_{\equiv }$$
Lemma:

$$L(M/\equiv )=L(M)$$

Minimalität des Quotientenautomaten

Jede Sprache

$L\subseteq {\mathrm{\Sigma }}^{\ast }$ induziert eine Äquivalenzrelation

${\equiv }_L\subseteq {\mathrm{\Sigma }}^{\ast }\times {\mathrm{\Sigma }}^{\ast }$:

$$\hat{\delta }(q_0,u){\equiv }_M\hat{\delta }(q_0,v)⟺u{\equiv }_{L(M)}v$$

Achtung:

• $p{\equiv }_{M}q$ ist eine Relation auf Zuständen von M
• $u{\equiv }_{L}v$ ist eine Relation auf Wörtern

Ist M ein DFA ohne unerreichbare Zustände, so ist der von Algorithmus U berechnete Quotientenautomat

$M/\equiv$ ein minimaler DFA für L(M)

Alle Quotientenautomaten

$M/{\equiv }_M$ für die gleiche Sprache L(M) haben die gleiche Struktur, d.h. sie unterscheiden sich nur durch eine Umbenennung der Zustände.

Daher werden die Zustände des kanonischen Minimalautomaten für eine Sprache L mit

${\equiv }_L$ Äquivalenzklassen beschriftet.

Satz von Myhill-Nerode

Eine Sprache

$L\subseteq {\mathrm{\Sigma }}^{\ast }$ ist genau dann regulär, wenn

${\equiv }_L$ endlich viele Äquivalenzklassen hat.

Vollständige Methode um Nichtregularität von L zu zeigen:
Gib unendliche Menge

$w_1,w_2\dots$ an, mit

$w_i{\not\equiv }_L{w}_j$ falls

$i\ne j$

Bemerkung: Eindeutigkeit des minimalen Automaten (modulo Umbenennung der Zustände) gilt nur bei DFAs, nicht bei NFAs!

3. Kontextfreie Sprachen

3.1 Kontextfreie Grammatiken

(folie 126 maybe)
Eine Kontextfreie Grammatik

$G=(V,\mathrm{\Sigma },P,S)$ ist ein 4-Tupel:

$V$: endliche Menge, Nichtterminale

$\mathrm{\Sigma }$: Alphabet, Terminale, disjunkt von V

$P\subseteq V\times (V\cup \mathrm{\Sigma }{)}^{\ast }$: Endliche Menge, Produktionen

$S\in V$: Startsymbol

Eine Kontextfreie Grammatik

$G=(V,\mathrm{\Sigma },P,S)$ induziert eine Ableitungsrelation

${\to }_G$ auf wörtern über

$V\cup \mathrm{\Sigma }$:

$$\alpha {\to }_G\beta$$

gdw es eine Regel

$A\to \gamma$ in P gibt, und Wörter

${\alpha }_1,{\alpha }_2$, sodass

$\alpha ={\alpha }_{1}A{\alpha }_2$ und

$\beta ={\alpha }_1\gamma {\alpha }_2$

$${\alpha }_1{\to }_G{\alpha }_2{\to }_G\cdots {\to }_G{\alpha }_n$$

wird als eine Linksableitung bezeichnet, gdw. in jedem Schritt das linkeste Nichtterminal ersetzt wird

Kontextfreie Sprache

Eine kontextfreie Grammatik

$G=(V,\mathrm{\Sigma },P,S)$ erzeugt die Sprache

$$L(G):=\{w\in {\mathrm{\Sigma }}^{\ast }|S{\to }_G^{\ast }w\}$$

Eine Sprache

$L\subseteq {\mathrm{\Sigma }}^{\ast }$ ist kontextfrei gdw. es eine kontextfreie Grammatik G gibt mit L = L(G)

Abkürzungen:

• CFG: Kontextfreie Grammatik (context-free grammar)
• CFL: Kontextfreie Sprache (context-free language)

Konvention:
Ist G aus dem Kontext eindeutig ersichtlich, so schreibt man auch nur

$\alpha \to \beta$ statt

$\alpha {\to }_G\beta$

Linearität:

• Eine CFG ist rechtslinear gdw. jede Produktion der Form
  $A\to aB$ oder
  $A\to ϵ$ ist
• Eine CFG ist linkslinear gdw. jede Produktion der Form
  $A\to Ba$ oder
  $A\to ϵ$ ist
• Die rechtslinearen und linkslinearen Grammatiken erzeugen jeweils genau die regulären Sprachen.
• -> Die regulären Sprachen sind somit eine echte Teilklasse der kontextfreien Sprachen

Todo:

• TODO: Dekompositionslemma folie 134

3.2 Induktive Definitionen, Syntaxbäume und Ableitungen

• Produktionen (
  $\to$) erzeugen Wörter top-down: von einem Nichtterminal zu einem Wort hin
• Induktive Definitionen (
  $⟹$) erzeugen Wörter bottom-up: von kleineren Wörtern zu größeren
• Induktive Definition betrachtet nur Wörter aus
  ${\mathrm{\Sigma }}^{\ast }$

Definitionen:

• Präfix:
  $u⪯w:⟺\mathrm{\exists }v.uv=w$
• Anzahl der Vorkommen:
  ${\mathrm{\#}}_a(w):=$ Anzahl der Vorkommen von a in w

Beweisvarianten:

• "
  $w\in L_G(S)⟹P(w)$" wird immer schematisch mit Induktion über die Erzeugung von w
• "
  $P(w)⟹w\in L_G(S)$" wird oft mit Induktion über
  $|w|$ bewiesen, erfordert meist Kreativität

TODOs:

• TODO: Folie 146 idk

Syntaxbaum

Ein Syntaxbaum für eine Ableitung mit einer Grammatik G ist ein Baum, sodass:

• jedes Blatt mit einem Zeichen aus
  $\mathrm{\Sigma }\cup \{ϵ\}$ beschriftet ist
• jeder innere Knoten mit einem
  $A\in V$ beschriftet ist, und falls die Nachfolger (von links nach rechts) mit
  $X_1,\dots ,X_n\in V\cup \mathrm{\Sigma }\cup \{ϵ\}$, dann ist
  $A\to X_1\dots X_n$ eine Produktion in P
• ein Blatt
  $ϵ$ der einzige Nachfolger seines Vorgängers ist

Für eine CFG und ein

$w\in {\mathrm{\Sigma }}^{\ast }$ sind folgende Bedingungen äquivalent:

• $A{\to }_G^{\ast }w$
• $w\in L_G(A)$ (gemäß induktiver Definition)
• Es gibt einen Syntaxbaum mit Wurzel A dessen Rand das wort W ist (Rand = Blätter von links nach rechts gelesen)

Mehrdeutigkeit:

• Ein CFG G ist mehrdeutig gdw. es ein
  $w\in L(G)$ gibt, das zwei verschiedene Syntaxbäume hat, also zwei verschiedene Syntaxbäume mit Wurzel S und Rand w
• Eine CFL L heißt inhärent mehrdeutig gdw jede CFG G mit
  $L(G)=L$ mehrdeutig ist

3.3 Die Chomsky-Normalform

Eine kontextfreie Grammatik G ist in Chomsky-Normalform gdw. alle Produktionen eine der Formen

$A\to a$ oder

$A\to BC$ haben.

Zu jeder CFG G kann man eine CFG G' in Chomsky-Normalform konstruieren mit

$L(G^{\prime })=L(G)\mathrm{\setminus }\{ϵ\}$
Wer auf

$ϵ\in L(G^{\prime })$ nicht verzichten möchte: Füge am Ende wieder

$S\to ϵ$ hinzu.

$A\to ϵ$ wird auch als

$ϵ$-Produktion bezeichnet

Zu jeder CFG

$G=(V,\mathrm{\Sigma },P,S)$ kann man eine CFG G' konstruieren, die keine

$ϵ$-Produktionen enthält, sodass gilt:

$L(G^{\prime })=L(G)\mathrm{\setminus }\{ϵ\}$

$A\to B$ wird Kettenproduktion genannt

Zu jeder CFG

$G=(V,\mathrm{\Sigma },P,S)$ kann man eine CFG G' konstruieren, die keine Kettenproduktionen enthält, sodass gilt

$L(G^{\prime })=L(G)$

Konstruktion einer Chomsky-Normalform

Eingabe: Eine kontextfreie Grammatik

$G=(V,\mathrm{\Sigma },P,S)$

• Füge für jedes
  $a\in \mathrm{\Sigma }$ das in einer rechten Seite der Länge
  $\ge$ 2 vorkommt ein neues Nichtterminal
  $A_a$ zu V hinzu, ersetze a in allen rechten Seiten der Länge
  $\ge$ 2 durch
  $A_a$ und füge
  $A_a\to a$ zu P hinzu
• Ersetze jede Produktion der Form
  
  $$A\to B_1{B}_2\cdots B_k(k\ge 3)$$
  durch
  
  $$A\to B_1{C}_2,C_2\to B_2{C}_3,\dots ,C_{k-1}\to B_{k-1}{B}_k$$
  wobei
  $C_2,\dots ,C_{k-1}$ neue Nichtterminale sind
• Eliminiere alle
  $ϵ$-Produktionen
• Eliminiere alle Kettenproduktionen

Greibach-Normalform

Eine CFG ist in Greibach-Normalform falls jede Produktion von der Form

$$A\to a{A}_1\dots A_n$$

ist

Zu jeder CFG G gibt es eine CFG G' in Greibach-Normalform mit

$L(G^{\prime })=L(G)\mathrm{\setminus }\{ϵ\}$

3.4 Das Pumping-Lemma für kontextfreie Sprachen

Für jede kontextfreie Sprache L gibt es ein n

$\ge$ 1, so dass sich jedes Wort

$z\in L$ mit

$|z|\ge n$ zerlegen lässt in

$$z=uvwxy$$

mit

• $vx\ne ϵ$
• $|vwx|\le n$
• $\mathrm{\forall }i\in \mathbb{N}.u{v}^{i}w{x}^{i}y\in L$

Siehe Folie 164

3.5 Algorithmen für kontextfreie Grammatiken

$G=(V,\mathrm{\Sigma },P,S)$ ist eine CFG
Ein Symbol

$X\in V\cup \mathrm{\Sigma }$ ist:

• Nützlich gdw es eine Ableitung
  $S{\to }_G^{\ast }w\in {\mathrm{\Sigma }}^{\ast }$ gibt, in der
  $X$ vorkommt
• erzeugend gdw es eine Ableitung
  $X{\to }_G^{\ast }w\in {\mathrm{\Sigma }}^{\ast }$ gibt.
• erreichbar gdw es eine Ableitung
  $S{\to }_G^{\ast }\alpha X\beta$ gibt.

Nützlich: Nützliche Symbole sind erzeugend und erreichbar, aber nicht notwendigerweise umgekehrt.
Folgliches Ziel: Elimination der unnützen Symbole und der Produktionen, in denen sie vorkommen

Eliminiert man aus einer Grammatik

$G$

• alle nicht erzeugenden Symbole, mit Resultat
  $G_1$ und
• aus
  $G_1$ alle unerreichbaren Symbole, mit Resultat
  $G_2$, dann enthält
  $G_2$ nur noch nützliche Symbole und
  $L(G_2)=L(G)$

Die Menge der erzeugenden Symbole einer CFG ist berechenbar
Die Menge der erreichbaren Symbole einer CFG ist berechenbar
Das Wortproblem (

$w\in L(G)?$) ist für eine CFG G entscheidbar

3.6 Der Cocke-Younger-Kasami-Algorithmus (CYK)

Der CYK-Algorithmus entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform.

Eingabe: Grammatik

$G=(V,\mathrm{\Sigma },P,S)$ in Chomsky-Normalform,

$w=a_1\dots a_n\in {\mathrm{\Sigma }}^{\ast }$

$$V_{ij}:=\{A\in V|A{\to }_G^{\ast }{a}_i\dots a_j\}$$
für

$i\le j$
Damit gilt:

$$w\in L(G)⟺S\in V_{1n}$$

Der CYK-Algorithmus berechnet die

$V_{ij}$ rekursiv nach wachsendem

$j-i$:

$$\begin{gathered} V_{ii}=\{A\in V|(A\to a_i)\in P\} \\ {V}_{ij}=\{A\in V|\mathrm{\exists }i\le k\le j,B\in V_{ik},C\in V_{k+1,j}.(A\to BC)\in P\} \end{gathered}$$
für

$i<j$

Der CYK-Algorithmus entscheidet das Wortproblem

$w\in L(G)$ für eine fixe CFG G in Chomsky-Normalform in Zeit

$O(|w{|}^3)$

Erweiterung: Der CYK-Algorithmus kann so erweitert werden, dass er nicht nur das Wortproblem entscheidet, sondern auch die Menge der Syntaxbäume für die Eingabe berechnet.
Realisierung:

• $V_{ij}$ ist die Menge der Syntaxbäume mit Rand
  $a_i\dots a_j$
• Statt A enthält
  $V_{ij}$ die Syntaxbäume, dessen Wurzel mit A beschriftet ist.

Vorschau:
Für CFGs sind folgende Probleme nicht entscheidbar:

• Äquivalenz
• Schnittproblem
• Regularität
• Mehrdeutigkeit

3.7 Abschlusseigenschaften

Seien kontextfreie Grammatiken

$G_1=(V_1,{\mathrm{\Sigma }}_1,P_1,S_1)$ und

$G_2=(V_2,{\mathrm{\Sigma }}_2,P_2,S_2)$ gegeben. Dann kann man in linearer Zeit CFGs für

• $L(G_1)\cup L(G_2)$
• $L(G_1)L(G_2)$
• $(L(G_1){)}^{\ast }$
• $(L(G_1){)}^R$
  konstruieren. Die Klasse der kontextfreien Sprachen ist also unter Vereinigung, Konkatenation, Stern und Spiegelung abgeschlossen.

$⟹$ Verallgemeinerte kontextfreie Grammatiken mit Produktionen der Gestalt

$X\to r$, wobei r ein regulärer Ausdruck über

$(V\cup T)$ ist, erzeugen kontextfreie Sprachen.

Die Menge der kontextfreien Sprachen ist nicht abgeschlossen unter Durchschnitt oder Komplement
Wegen de Morgan können die CFLs daher auch nicht unter Komplement abgeschlossen sein.

3.8 Kellerautomaten

Anwendungsgebiete:

• Syntaxanalyse von Programmiersprachen
• Analyse von Programmen mit Rekursion

Definition

Ein (nichtdeterministischer) Kellerautomat (PDA = Pushdown Automaton)

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },q_0,Z_0,\delta ,F)$ besteht aus:

• Q: Endliche Menge von Zuständen
• $\mathrm{\Sigma }$ endliches Eingabealphabet
• $\mathrm{\Gamma }$ endliches Kelleralphabet
• $q_0\in Q$ Anfangszustand
• $Z_0\in \mathrm{\Gamma }$ initialer Kellerinhalt
• $\delta$: Übergangsfunktion:
  $\delta :Q\times (\mathrm{\Sigma }\cup \{ϵ\})\times \mathrm{\Gamma }\to P_e(Q\times {\mathrm{\Gamma }}^{\ast })$,
  $P_e$ = mente aller endlichen Teilmengen
• $F\subseteq Q$ Endzustände

Intuitive Bedeutung von

$(q^{\prime },\alpha )\in \delta (q,a,Z)$:
Wenn sich M in Zustand q befindet, das Eingabezeichen a liest und Z das oberste Kellerzeichen ist, so kann M im nächsten Schritt in q' übergehen und Z durch

$\alpha$ ersetzen

Achtung:

• $\alpha$ kann die Länge 0, 1 und mehr haben
• Falls a =
  $ϵ$: kein Eingabezeichen wird gelesen

Eine Konfiguration eines Kellerautomaten M ist ein Tripel

$(q,w,\alpha )$ mit

$q\in Q,w\in {\mathrm{\Sigma }}^{\ast }$ und

$\alpha \in {\mathrm{\Gamma }}^{\ast }$.
Die Anfangskonfiguration von M für die Eingabe

$w\in {\mathrm{\Sigma }}^{\ast }$ ist

$(q_0,w,Z_0)$
Intuitiv stellt eine Konfiguration

$(q,w,\alpha )$ eine "Momentaufnahme" des Kellerautomaten dar:

• Der momentane Zustand ist q
• Der noch zu lesende Teil der Eingabe ist w
• Der aktuelle Kellerinhalt ist
  $\alpha$ (das oberste Kellerzeichen ganz links stehend)

Die Transitionsrelation

${\to }_M$ zwischen Konfigurationen:

• $(q,aq,Z\alpha ){\to }_M(q^{\prime },w,\beta \alpha )$ falls
  $(q^{\prime },\beta )\in \delta (q,a,Z)$
• $(q,w,Z\alpha ){\to }_M(q^{\prime },w,\beta \alpha )$ falls
  $(q^{\prime },\beta )\in \delta (q,ϵ,Z)$

Intuitive Bedeuting von

$(q,w,\alpha ){\to }_M(q^{\prime },w^{\prime },{\alpha }^{\prime })$:
Wenn M sich in der Konfiguration

$(q,w,\alpha )$ befindet, dann kann er in einen Schritt in die Nachfolgerkonfiguration

$(q^{\prime },w^{\prime },{\alpha }^{\prime })$ übergehen.
Achtung: Eine Konfiguration kann mehrere Nachfolger haben (Nichtdeterminisumus)

Akzeptanz

Ein PDA M akzeptiert

$w\in {\mathrm{\Sigma }}^{\ast }$ mit Endzustand gdw

• $(q_0,w,Z_0){\to }_M^{\ast }(f,ϵ,\gamma )$ für ein
  $f\in F,\gamma \in {\mathrm{\Gamma }}^{\ast }$
• $L_F(M):=\{w|\mathrm{\exists }f\in F,\gamma \in {\mathrm{\Gamma }}^{\ast }.(q_0,w,Z_0){\to }_M^{\ast }(f,ϵ,\gamma )\}$

Ein PDA M akzeptiert

$w\in {\mathrm{\Sigma }}^{\ast }$ nit leeren Keller gdw

• $(q_0,w,Z_0){\to }_M^{\ast }(q,ϵ,ϵ)$ für ein
  $q\in Q$
• $L_{ϵ}(M):=\{w|\mathrm{\exists }q\in Q.(q_0,w,Z_0){\to }_M^{\ast }(q,ϵ,ϵ)\}$

Konvention:
Die F-Komponente von M wird ausgeblendet, wenn nur

$L_{ϵ}(M)$ von interesse ist.

Bemerkungen: PDAs und das Wortproblem

• Mit einem NFA A kann man
  $w\in L(A)$ durch pararllele Verfolgung aller Berechnungspfade entscheiden, da sie alle endlich sind.
• Bei einem PDA kann es wegen
  $ϵ$-Übergängen auch unendliche Berechnungen
  ${\to }_M$ geben, z.B.
  $\delta (q,ϵ,Z)=(q,ZZ):$
  
  $$(q,w,Z){\to }_M(q,w,ZZ){\to }_M(q,w,ZZZ){\to }_M\dots$$
  Diese sind wegen des möglicherweise wachsenden oder pulsierenden Kellers nicht einfach zu eliminieren.
• Daher ist es a priori unklar, wie man mit einem PDA das Wortproblem entscheidet.

Ziel: Akzeptanz durch Endzustände und leeren Keller gleich mächtig
Endzustand

$\to$ Leerer Keller:
Zu jedem PDA

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },q_0,Z_0,\delta ,F)$ kann man in linearer Zeit einen PDA

$M^{\prime }=(Q^{\prime },\mathrm{\Sigma },{\mathrm{\Gamma }}^{\prime },q_0^{\prime },Z_0^{\prime },{\delta }^{\prime })$ konstruieren mit

$L_F(M)=L_{ϵ}(M^{\prime })$

$$(q_0,w,Z_0){\to }_M^{\ast }(f,ϵ,\gamma )⟺(q_0^{\prime },w,Z_0^{\prime }){\to }_{M^{\prime }}^{\ast }(q,ϵ,ϵ)$$
Leerer Keller

$\to$ Endzustand
Zu jedem PDA

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },q_0,Z_0,\delta )$ kann man in linearer Zeit einen PDA

$M^{\prime }=(Q^{\prime },\mathrm{\Sigma },{\mathrm{\Gamma }}^{\prime },q_0^{\prime },Z_0^{\prime },{\delta }^{\prime },F)$ konstruieren mit

$L_{ϵ}(M)=L_F(M^{\prime })$

beweishilfen:

Erweiterungslemma:

$$(q,u,\alpha ){\to }_M^n(q^{\prime },u^{\prime },{\alpha }^{\prime })⟹(q,uv,\alpha \beta ){\to }_M^n(q^{\prime },u^{\prime }v,{\alpha }^{\prime }\beta )$$
Zerlegungssatz:
Wenn

$(q,w,Z_{1\dots k}){\to }_M^n(q^{\prime },ϵ,ϵ)$, dann gibt es

$u_i,p_i,n_i$, so dass:

$$(p_{i-1},u_i,Z_i){\to }_M^{n_i}(p_i,ϵ,ϵ)(i=1,\dots ,k)$$
und

$w=u_1\dots u_k,p_0=q,p_k=q^{\prime },\sum n_i=n$.

3.9: Äquivalenz von PDAs und CFGs

CFG

$\to$PDA

Zu jeder CFG G kann man einen PDA M konstruieren, der mit leerem Keller akzeptiert, so dass

$L_{ϵ}(M)=L(G)$
Konstruktion:
Zuerst werden alle Produktionen G in die Form

$$A\to b{B}_1\dots B_k$$
gebracht, wobei

$b\in \mathrm{\Sigma }\cup \{ϵ\}$
Methode: Für jedes

$a\in \mathrm{\Sigma }$

• füge ein neues
  $A_a$ zu V hinzu
• ersetze a rechts in P durch
  $A_a$ (außer am Kopfende)
• füge eine neue Produktion
  $A_a\to a$ hinzu

Alle Produktionen in

$G=(V,\mathrm{\Sigma },P,S)$ haben jetzt die Form

$$A\to b{B}_1\dots B_k$$

Der PDA wird wie folgt definiert:

$$M:=(q,\mathrm{\Sigma },V,q,S,\mathrm{\Delta })$$

wobei

$$(A\to b\beta )\in P⟹\delta (q,b,A)\ni (q,\beta )$$

also für alle

$b\in \mathrm{\Sigma }\cup \{ϵ\}$ und

$A\in V$:

$$\delta (q,b,A):=\{(q,\beta )|(A\to b\beta )\in P\}$$

Jetzt gilt:

• Für alle
  $u,v\in {\mathrm{\Sigma }}^{\ast }$ und
  $\gamma \in V^{\ast }$ und
  $A\in V$ gilt:
  $A{\to }_G^{n}u\gamma$ mit Linksableitung gdw
  $(q,uv,A){\to }_M^n(q,v,\gamma )$
• $L(G)=L_{ϵ}(M)$

PDA

$\to$ CFG

Zu jedem PDA

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },q_0,Z_0,\delta ,F)$, der mit leerem Keller akzeptiert, kann man eine CFG G konstruieren mit

$L(G)=L_{ϵ}(M)$
Konstruktion:

$G:=(V,\mathrm{\Sigma },P,S)$ mit

$V:=Q\times \mathrm{\Gamma }\times Q\cup \{S\}$, wobei die Tripel mit [., ., .] notiert werden und P die folgenden Produktionene enthält:

• $S\to [q_0,Z_0,q]$ für alle
  $q\in Q$
• Für alle
  $\delta (q,b,Z)\ni (r_0,Z_1\dots Z_k)$ und für alle
  $r_1,\dots ,r_k\in Q$:
  
  $$[q,Z,r_k]\to b[r_0,Z_1,r_1][r1,Z_2,r_2]\dots [r_k-1,Z_k,r_k]$$

idee:

$[q,Z,r_k]{\to }_G^{\ast }w$ gdw.

$(q,w,Z){\to }_M^{\ast }(r_k,ϵ,ϵ)$
Die

$r_1\dots r_k$ sind potenzielle Zwischenzustände beim Akzeptieren der Teilwörter von

$b{u}_1\dots u_k=w$, die zu

$Z_1\dots Z_k$ gehören. (Zerlegungssatz)

Lemma:

$[q,Z,p]{\to }_G^{n}w$ gdw

$(q,w,Z){\to }_M^n(p,ϵ,ϵ)$

Eine Sprache ist kontextfrei gdw. sie von einem Kellerautomaten akzeptiert wird.

3.10 Deterministische Kellerautomaten

Ein PDA ist deterministisch (DPDA) gdw. für alle

$q\in Q,a\in \mathrm{\Sigma }$ und

$Z\in \mathrm{\Gamma }$

$$|\delta (q,a,Z)|+|\delta (q,ϵ,Z)|\le 1$$

Eine CFL ist deterministisch (DCFL) gdw. sie von einem DPDA akzeptiert wird.
Man kann zeigen: Die CFL

$\{w{w}^R|w\in \{0,1{\}}^{\ast }\}$ ist nicht deterministisch, da man jeden DFA leicht mit einem DPDA simulieren kann:
fakt: jede reguläre Sprache ist eine DCFL

Eine Sprache erfüllt die Präfix-Bedingung gdw sie keine zwei Wörter enthält, so dass eine ein echtes präfix eines anderen ist.

Lemma:

$\mathrm{\exists }DPDAM.L=L_{ϵ}(M)⟺\mathrm{\exists }DPDAM.L=L_F(M)$ und L erfüllt die präfix-bedingung

Weitere Eigenschaften

• Die Klasse der DCFLs ist unter Komplement abgeschlossen.
  -> Da die CFLs nicht unter Komplement abgeschlossen sind sind DCFLs eine echte Teilklasse der CFLs
• Die Klasse der DCFLs ist weder unter Schnitt noch unter Vereinigung abgeschlossen.
• Jede DCFL ist nicht inhärent mehrdeutig, d.h. sie wird von einer nicht-mehrdeutigen Grammatik erzeugt.
• Das Wortproblem ist für DCFLs in linearer Zeit lösbar.

3.11 Tabellarischer überblick

Abschlusseigenschaften

	Schnitt	Vereinigung	Komplement	Produkt	Stern
Regulär	ja	ja	ja	ja	ja
DCFL	nein	nein	ja	nein	nein
CFL	nein	ja	nein	ja	ja

Entscheidbarkeit

	Wortproblem	Leerheit	Äquivalenz	Column 3
DFA	$O(n)$	ja	ja	ja
DPDA	$O(n)$	ja	ja	nein $(\ast )$
CFG	$O(n^3)$	ja	nein $(\ast )$	nein $(\ast )$

Teil 2: Berechenbarkeit, Entscheidbarkeit, Komplexität

4. Berechenbarkeit, Entscheidbarkeit

Überblick:

• Was kann man berechnen?
  • Welche Funktionen kann man in endlicher Zeit berechnen?
  • Welche Eigenschaften von Objekten können in endlicher Zeit entschieden werden?
• Mit welchen Sprachen / Maschinen?
• Was kann man in polynomieller Zeit berechnen?

4.1 Der Begriff der Berechenbarkeit

Eine Funktion

$f:{\mathbb{N}}^k\to \mathbb{N}$ ist intuitiv berechenbar, wenn es einen Algorithmus gibt, der bei Eingabe

$(n_1,\dots ,n_k)\in {\mathbb{N}}^k$

• nach endlich vielen Schritten mit Ergebnis
  $f(n_1,\dots ,n_k)$ hält, falls
  $f(n_1,\dots ,n_k)$ definiert ist,
• und nicht terminiert, falls
  $f(n_1,\dots ,n_k)$ nicht definiert ist.

Achtung: Berechenbarkeit setzt zwei verschiedene Dinge in Beziehung:

• Algorithmen, d.h. endliche Wörter
• Mathematische Funktionen, d.h. Mengen von Paaren.

Terminologie: Eine Funktion

$f:A\to B$ ist

• Total gdw.
  $f(a)$ für alle
  $a\in A$ definiert ist.
• partiell gdw.
  $f(a)$ auch undefiniert sein kann
• echt partiell gdw
  $f(a)$ nicht total ist

Es gibt nicht-berechenbare Funktionen

$\mathbb{N}\to \{0,1\}$

Erinnerung: Eine Menge

$M$ ist abzählbar, falls es eine injektive Funktion

$M\to \mathbb{N}$ gibt.
Äquivalente Definitionen:

• Entweder gibt es eine Bijektion
  $M\to \{0,\dots ,n\}$ für ein
  $n\in \mathbb{N}$, oder eine Bijektion
  $M\to \mathbb{N}$
• Es gibt eine Nummerierung der Elemente von M.

Eine Menge ist Überabzählbar wenn sie nicht abzählbar ist

Abzählbarkeiten:

• ${\mathrm{\Sigma }}^{\ast }$ ist abzählbar, falls
  $\mathrm{\Sigma }$ endlich ist.
• Die Menge der Algorithmen ist Abzählbar
• Die Menge aller Funktionen
  $\mathbb{N}\to \{0,1\}$ ist überabzählbar
• Wenn Algorithmen als endliche Wörter kodiert werden können, dann gibt es nicht-berechenbare Funktionen
  $\mathbb{N}\to \{0,1\}$

Church-Turing-These

Der formale Begriff der Berechenbarkeit mit Turing-Maschinen (bzw.

$\lambda$-Kalkül, etc.) stimmt mit dem intuitiven Berechenbarkeitsbegriff überein.
Dies ist keine formale Aussage und nicht beweisbar, wird aber allgemein akzeptiert.

4.2 Turingmaschinen

Definition

Eine Turingmaschine ™ ist ein 7-Tupel

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,◻,F)$ mit:

• $Q$: Endliche Menge an Zuständen
• $\mathrm{\Sigma }$: Endliche menge des Eingabealphabets
• $\mathrm{\Gamma }$: Endliche Menge des Bandalphabets mit
  $\mathrm{\Sigma }\subset \mathrm{\Gamma }$
• $\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R,N\}$ ist die Übergangsfunktion.
  $\delta$ darf partiell sein.
• $q_0\in Q$ ist der Startzustand
• $◻\in \mathrm{\Gamma }\mathrm{\setminus }\mathrm{\Sigma }$ ist das Leerzeichen
• $F\subseteq Q$ ist die Menge der akzeptierenden oder endzustände

Annahme:

$\delta (q,a)$ ist nicht definiert für alle

$q\in F$ und

$a\in \mathrm{\Gamma }$
Eine nichtdeterministische Turingmaschine hat eine Übergangsfunktion

$\delta :Q\times \mathrm{\Gamma }\to P(Q\times \mathrm{\Gamma }\times \{L,R,N\})$

Intuitive Bedeutung:

$\delta (q,a)=(q^{\prime },b,D)$:

• Wenn sich M im Zustand q befindet
• und auf dem Band a liest
• so geht M im nächsten Schritt in den Zustand q' über
• überschreibt a mit b
• und bewegt danach den Schreib-/Lesekopf nach rechts (falls D = R), nach links (falls D = L) oder nicht (falls D = N)

Konfiguration:

Eine Konfiguration einer Turingmaschine ist ein Tripel

$(\alpha ,q,\beta )\in {\mathrm{\Gamma }}^{\ast }\times Q\times {\mathrm{\Gamma }}^{\ast }$, welches modelliert:

• Bandinhalt:
  $\dots ◻\alpha \beta ◻\dots$
• Zustand: q
• Kopf auf dem ersten Zeichen von
  $\beta ◻$

Die Startkonfiguration der Turingmaschine bei Eingabe

$w\in {\mathrm{\Sigma }}^{\ast }$ ist

$(ϵ,q_0,w)$

• TODO: slide 232???

Akzeptanz

Eine Turingmaschine M akzeptiert die Sprache

$$L(M)=\{w\in {\mathrm{\Sigma }}^{\ast }|\mathrm{\exists }q\in F,\alpha ,\beta \in {\mathrm{\Gamma }}^{\ast }.(ϵ,q_0,w){\to }_M^{\ast }(\alpha ,q,\beta )\}$$

Eine Funktion

$f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$ ist Turing-berechenbar gdw es eine Turingmaschine M gibt, so dass für alle

$u,v\in {\mathrm{\Sigma }}^{\ast }$ gilt

$$f(u)=v⟺\mathrm{\exists }r\in F.(ϵ,q_0,u){\to }_M^{\ast }(◻\dots ◻,r,v◻\dots ◻)$$

Eine Funktion

$f:{\mathbb{N}}^k\to \mathbb{N}$ ist Turing-berechenbar gdw. es eine Turingmaschine M gibt, so dass für alle

$n_1,\dots ,n_k,m\in \mathbb{N}$ gilt

$$f(n_1,\dots ,n_k)=m⟺\mathrm{\exists }r\in F.(ϵ,q_0,bin(n_1)\mathrm{\#}bin(n_2)\mathrm{\#}\dots \mathrm{\#}bin(n_k)){\to }_M^{\ast }(◻\dots ◻,r,bin(m)◻\dots ◻)$$

wobei bin(n) die binärdarstellung der Zahl n ist.

Satz:
Die von Turingmaschinen akzeptierten Sprachen sind genau die Typ-0-Sprachen der Chomsky-Hierarchie.

Halten/Terminieren

Eine TM hält wenn sie eine Konfiguration

$(\alpha ,q,\alpha \beta )$ erreicht und

$\delta (q,a)$ nicht definiert oder (bei einer nichtdeterministischen TM)

$\delta (q,a)=\mathrm{\varnothing }$.
Nach Annahme hält eine TM immer, wenn sie einen Endzustand erreicht. Damit ist die von einer TM berechnete Funktion wohldefiniert.
Eine TM kann auch halten, bevor sie einen Endzustand erreicht.

Weiteres

Nichtdeterministische TMs
Zu jeder nichtdeterministischen TM N gibt es eine deterministische TM M mit

$L(N)=L(M)$

Mehrband-TMs / K-Band-TMs
Jede k-Band-TM kann effektiv durch eine 1-Band-TM simuliert werden

4.3 Programmieren mit Turingmaschinen

Die folgenden Basismaschinen sind leicht programmierbar:

• Band i := Band i+1
• Band i := Band i-1
• Band i = 0
• Band i = Band j

Seien

$M_i=(Q_i,\mathrm{\Sigma },{\mathrm{\Gamma }}_i,{\delta }_i,q_i,◻,F_i),i=1,2$
Die sequentielle Komposition (hintereinanderschaltung) von

$M_1$ und

$M_2$ wird wie folgt bezeichnet

$$\to M_1\to M_2\to$$

Sie ist wie folgt definiert:

$$M:=(Q_1\cup Q_2,\mathrm{\Sigma },{\mathrm{\Gamma }}_1\cup {\mathrm{\Gamma }}_2,\delta ,q_1,◻,F_2)$$

wobei (oE)

$Q_1\cap Q_2=\mathrm{\varnothing }$ und

$$\delta :={\delta }_1\cup {\delta }_2\cup \{(f_1,a)\mapsto (q_2,a,N)|f_1\in F_1,a\in {\mathrm{\Gamma }}_1\}$$

Fallunterscheidung
Sind

$f_1$ und

$f_2$ Endzustände von M so bezeichnet

eine Fallunterscheidung, d.h. eine TM, die vom Endzustand

$f_1$ von

$M$ nach

$M_1$ übergeht, und von

$f_2$ aus nach

$M_2$

"Band = 0?"
Die Folgende TM wird "Band=0?" bzw. "Band i = 0?" genannt:

$$\begin{gathered} \delta (q_0,0)=(q_0,0,R) \\ \delta (q_0,◻)=(ja,◻,L) \\ \delta (q_0,a)=(nein,a,N)\mathbb{f}\mathbb{ü}\mathbb{r}a\ne 0 \end{gathered}$$

wobei ja und nein Endzustände sind.

Schleife
Analog zur Fallunterscheidung kann man auch eine TM für eine Schleife konstruieren

die sich wie while Band

$i\ne 0$do

$M$ verhält.

Fazit:
Mit TM kann man imperativ programmieren:

• :=
• ;
• if
• while

4.4 WHILE- und GOTO-Berechenbarkeit

WHILE

$\equiv$ strukturierte Programme mit while-Schleifen
GOTO

$\equiv$ Assembler

WHILE- und GOTO-Berechenbarkeit werden definiert und dessen Äquivalenz mit Turing-berechenbarkeit wird gezeigt.

WHILE-Programme:

Syntax von WHILE-Programmen:

wobei

$X$ eine der Variablen

$x_0,x_1,\dots$ und C eine der Konstanten

$0,1,\dots$ sein kann.

Die modifizierte Differenz ist

$m\dot{-}n:=\{\begin{array}{ll}m-n& \text{falls }m\ge n\\ 0& \text{sonst }\end{array}$

Semantik von WHILE-Programmen (informell):

• $x_i:=x_j+n$: Neuer Wert von
  $x_i$ ist
  $x_j+n$
• $x_i:=x_j-n$: Neuer Wert von
  $x_i$ ist
  $x_j\dot{-}n$
• $P_1;P_2$: Führe zuerst
  $P_1$ und dann
  $P_2$ aus
• WHILE
  $x_i\ne 0$ DO
  $P$ END: Führe
  $P$ aus bis die Variable
  $x_i$ (wenn je) den Wert 0 annimmt.

Syntaktische Abkürzungen:

• $x_i:=x_j\equiv x_i:=x_j+0$
• $x_i:=n\equiv x_i:=x_j+n$ (wobei
  $x_j$ nirgends zugewiesen wird)
• TODO: finish

While-Berechenbarkeit

Eine Funktion

$f:{\mathbb{N}}^k\to \mathbb{N}$ ist WHILE-berechenbar gdw. es ein WHILE-Programm P gibt, sodass für alle

$n_1,\dots ,n_k\in \mathbb{N}$:
P, gestartet mit

$n_1,\dots ,n_k$ in

$x_1,\dots ,x_k$ (0 in den anderen Variablen)

• Terminiert mit
  $f(n_1,\dots ,n_k)$ in
  $x_0$, falls
  $f(n_1,\dots ,n_k)$ definiert ist,
• terminiert nicht, falls
  $f(n_1,\dots ,n_k)$ undefiniert ist.

Turingmaschinen können WHILE-Programme simulieren:

WHILE

$\to$ TM

Jede WHILE-berechenbare Funktion ist auch Turing-berechenbar, da:

• jede Programmvariable auf 1 Band speichern
• alle Konstrukte der WHILE-Sprache sind von Mehrband-TMs simulierbar
• Mehrband-TMs sind von einband-TMs simulierbar.

GOTO-Programme:

Ein GOTO-Programm ist eine Sequenz von markierten Anweisungen:

$$M_1:A_1;M_2:A_2;\dots ;M_k:A_k$$

(wobei alle Marken verschieden und Optional sind)

Mögliche Anweisungen

$A_i$ sind:

• $x_i:=x_j+n$
• $x_i:=x_j-n$
• GOTO
  $M_i$
• IF
  $x_i=n$ GOTO
  $M_j$
• HALT

Die Semantik ist wie erwartet.

WHILE

$\to$ GOTO

Jedes WHILE-Programm kann durch ein GOTO-Programm simuliert werden.

GOTO

$\to$ WHILE

Jedes GOTO-Programm kann durch ein WHILE-Programm simuliert werden.
Für beweis: siehe Slide 253

Korollar:
WHILE- und GOTO-Berechenbarkeit sind äquivalent
Kleensche Normalform:
Jedes WHILE-Programm ist zu einem WHILE-Programm mit genau einer WHILE-Schleife äquivalent

TM

$\to$ GOTO

Jede TM kann durch ein GOTO-Programm simuliert werden.
Übersetzung siehe Folien 256,257

LOOP-Berechenbarkeit / LOOP-Programme

Statt while-Schleifen werden nun for-Schleifen betrachtet.
LOOP-Programme haben die gleiche Syntax wie WHILE-Programme, aber statt der WHILE-Schleifen gibt es nur LOOP-Schleifen mit folgender Syntax:

$$\text{LOOP }X\text{ DO }P\text{ END}$$
Semantik: Führe P genau n mal aus, wobei n der Anfangswert von X ist.
Zuweisungin an X in P ändern die Anzahl n der Schleifendurchläufe nicht.

Loop-berechenbarkeit

Eine Funktion

$f:{\mathbb{N}}^k\to \mathbb{N}$ ist LOOP-berechenbar gdw. es ein LOOP-Programm P gibt, so dass für alle

$n_1,\dots ,n_k\in \mathbb{N}$:
P, gestartet mit

$n_1,\dots ,n_k$ in

$x_1,\dots ,x_k$ (0 in den anderen Variablen) terminiert mit

$f(n_1,\dots ,n_k)$ in

$x_0$

Alle LOOP-berechenbaren Funktionen sind total, beweis via Induktion über die Syntax der LOOP-Programme.

FAKT: WHILE-Schleifen können LOOP-Schleifen simulieren, aber LOOP-Schleifen können WHILE-Schleifen nicht simulieren

4.5 Unentscheidbarkeit des Halteproblems

Ziel: Es ist unentscheidbar, ob ein Programm terminiert.

Definition:

Eine Menge

$A(\subseteq \mathbb{N}\text{ oder }{\mathrm{\Sigma }}^{\ast })$ ist entscheidbar gdw ihre charakteristische Funktion

$${\chi }_A(x):=\{\begin{array}{ll}1& \text{falls }x\in A\\ 0& \text{falls }x\notin A\end{array}$$

berechenbar ist.

Eine Eigenschaft/Problem P(x) ist entscheidbar gdw.

$\{x|P(x)\}$ entscheidbar ist.

Komplement:
Die entscheidbaren Mengen sind abgeschlossen unter Komplement: Ist

$A$ entscheidbar, so auch

$\bar{A}$

Kodierung einer TM als Wort über

$\mathrm{\Sigma }=\{0,1\}$:
Siehe Folie 300

Nicht jedes Wort über

$\{0,1{\}}^{\ast }$ kodiert eine TM.
Sei

$\hat{M}$ eine beliebige feste TM:
Die zu einem Wort

$w\in \{0,1{\}}^{\ast }$ gehörige TM

$M_w$ ist

$$M_w:=\{\begin{array}{ll}M& \text{falls }w\text{ Kodierung von }M\text{ ist}\\ \hat{M}& \text{sonst}\end{array}$$

Die Kondierung von syntaktischen Objekten (Programmen, Formeln, etc.) als Zahlen wird Gödelisierung genannt. Die Zahlen werden als Gödelnummern bezeichnet.

Definitionen:

• $M[w]$ ist abgekürzt für "Maschine
  $M$ mit Eingabe
  $w$"
• $M[w]\downarrow$ bedeutet, dass
  $M[w]$ terminiert/hält

Spezielles Halteproblem

Gegeben: Ein Wort

$w\in \{0,1{\}}^{\ast }$
Problem: Hält

$M_w$ bei Eingabe w?
Als Menge:

$K:=\{w\in \{0,1{\}}^{\ast }|M_w[w]\downarrow \}$

Das Spezielle Halteproblem K ist nicht entscheidbar.
Beweis: Folie 303, 304

(Allgemeines) Halteproblem

Gegeben: Wörter

$w,x\in \{0,1{\}}^{\ast }$
Problem: Hält

$M_w$ bei Eingabe x?
Als Menge:

$H:=\{w\mathrm{\#}x|M_w[x]\downarrow \}$

Das Halteproblem H ist nicht entscheidbar.
Beweis: Wäre H entscheidbar, dann trivialerweise auch K:

$${\chi }_K(w)={\chi }_H(w,w)$$

Reduktion

Eine Menge

$A\subseteq {\mathrm{\Sigma }}^{\ast }$ ist reduzierbar auf eine Menge

$B\subseteq {\mathrm{\Gamma }}^{\ast }$ gdw. es eine totale und berechenbare Funktion

$f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ gibt mit

$$\mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast }.w\in A⟺f(w)\in B$$

Es wird dann

$A\le B$ geschrieben
Intuition:

• $B$ ist mindestens so schwer zu lösen wie
  $A$.
• ist
  $A$ unlösbar, dann auch
  $B$.
• Ist
  $B$ lösbar, dann erst recht A.

Lemma:
Falls

$A\le B$ und

$B$ ist entscheidbar, so ist auch

$A$ entscheidbar.
Falls

$A\le B$ und

$A$ ist unentscheidbar, so ist

$B$ auch unentscheidbar.

Halteproblem auf leerem Band

Das Halteproblem auf leerem Band,

$H_0$, ist unentscheidbar.

$$H_0:=\{w\in \{0,1{\}}^{\ast }|M_w[ϵ]\}$$

Fazit:

Es gibt keine allgemeine algorithmische Methode, um zu entscheiden, ob ein Programm terminiert.
Die Unentscheidbarkeit vieler Fragen über die Ausführung von Programmen folgt durch Reduktion des Halteproblems:

• Kann ein WHILE-Programm mit einer bestimmten Eingabe einen bestimmten Programmpunkt erreichen?
  Der Spezialfall Programmpunkt = Programmende ist das Halteproblem
• Kann Variable
  $x_7$ bei einer bestimmten Eingabe je den Wert
  $2^{32}$ erreichen?
  Redunktion: Ein Programm P hält gdw während der ausführung von
  
  $P;x_7:=2^{32}$
  Variable
  $x_7$ den Wert
  $2^{32}$ erreicht.
  (OE:
  $x_7$ kommt in P nicht vor)

Hilberts 10. Problem:
Es ist unentscheidbar, ob ein Polynom in n Variablen mit ganzzahligen Koeffizienten eine ganzzahlige Nullstelle hat

$(\in {\mathbb{Z}}^n)$
Beweis:

$H\le H_{10}$
-> Es müssen nicht immer TMs sein

Bemerkungen

• Nicht alle unentscheidbaren Probleme sind gleich schwer
• Z.B. gilt: Das Äquivalenzproblem
  
  $E_q:=\{u\mathrm{\#}v|M_u\text{ berechnet die gleiche Funktion wie }{M}_v\}$
  ist schwerer als das Halteproblem:

4.6 Semi-Entscheidbarkeit

Definition

Eine Menge

$A(\subseteq \mathbb{N}\text{ oder }{\mathrm{\Sigma }}^{\ast })$ ist semi-entscheidbar (s-e) gdw.

$${\chi }_a^{\prime }(x):=\{\begin{array}{ll}1& \text{falls }x\in A\\ \mathrm{\perp }& \text{falls }x\notin A\end{array}$$

berechenbar ist.

Entscheidbarkeit:
Eine Menge

$A$ ist entscheidbar gdw. sowohl

$A$ als auch

$\bar{A}$ s-e sind.

Rekursiv Aufzählbar

Eine Menge A ist rekursiv aufzählbar (recursively enumerable) gdw.

$A=\mathrm{\varnothing }$ oder es eine berechenbare totale Funktion

$f:\mathbb{N}\to A$ gibt, so dass

$$A=\{f(0),f(1),f(2),\dots \}$$

Bemerkung:

• Es dürfen Elemente doppelt auftreten
  $(f(i)=f(j)\text{ für }i\ne j)$
• Die Reihenfolge ist beliebig

Warnung:

• Rekursiv aufzählbar
  $\ne$ Abzählbar
• Aber: Rekursiv aufzählbar
  $⟹$ abzählbar
• Aber nicht umgekehrt: Jede Sprache ist abzählbar, aber nicht jede Sprache ist rekursiv aufzählbar (siehe unten)

Lemma:
Eine Menge

$A$ ist rekursiv aufzählbar gdw. sie semi-entscheidbar ist.
Beweis: 317, 318

Äquivalente Aussagen

• $A$ ist Semi-entscheidbar
• $A$ ist rekursiv aufzählbar
• ${\chi }_A^{\prime }$ ist berechenbar
• $A=L(M)$ für eine TM
  $M$
• $A$ ist Definitionsbereich einer berechenbaren Funktion
• $A$ ist Wertebereich einer berechenbaren Funktion

K ist Semi-entscheidbar
Die Menge

$K=\{w|M_w[w]\downarrow \}$ ist semi-entscheidbar.
Beweis:
Die funktion

${\chi }_k^{\prime }$ ist wie folgt Turing-berechenbar:
Bei Eingabe w simuliere die Ausführung von

$M_w[w]$; gib 1 aus

Komplement

$\bar{K}$ ist nicht semi-entscheidbar.
Semi-entscheidbarkeit ist nicht abgeschlossen unter Komplement

4.7: Die Sätze von Rice und Shapiro

Die von der TM

$M_w$ berechnete Funktion wird als

${\phi }_w$ bezeichnet.
Es werden implizit nur einstellige Funktionen betrachtet.

Der Satz von Rice

Sei F eine Menge berechenbarer Funktionen.
Es gelte weder

$F=\mathrm{\varnothing }$ noch

$F=\text{alle berechenbaren Funktionen}$ ("F nicht trivial")
Dann ist unentscheidbar, ob die von einer gegebenen TM

$M_w$ berechnete Funktion Element F ist, d.h. ob

${\phi }_w\in F$
Alle nicht-trivialen semantischen Eigenschaften von Programmen sind unentscheidbar.

Warnung:
Im Satz von Rice geht es um die von einem Programm berechnete Funktion (Semantik), nicht um den Programmtext (Syntax). Beispielsweise ist es entscheidbar, ob ein Programm

• länger als 5 Zeilen ist
• Eine Zuweisung an die Variable
  $x_{17}$ enthält.

Der Satz von Rice-Shapiro

Sei

$F$ eine Menge berechenbarer Funktionen.
Ist

$C_F:=w|{\phi }_w\in F$ semi-entscheidbar,
so gilt für alle berechenbaren

$f$:

$f\in F⟺$ es gibt eine endliche Teilfunktion

$g\subseteq f$ mit

$g\in f$

Terminierend:

Ein Programm ist terminierend gdw. es für alle eingaben hält.

• Die Menge der terminierenden Programme ist nicht semi-entscheidbar
• Die Menge der nicht-terminierenden Programme ist nicht semi-entscheidbar

Grenzen automatischer Terminationsanalyse von Programmen

• Termination ist unentscheidbar (Rice): Klare Ja/Nein Antwort unmöglich.
• Termination ist nicht semi-entscheidbar (Rice-Shapiro) Es gibt kein Zertifizierungs-programm das alle terminierenden Programme erkennt.
• Nicht-Termination ist nicht semi-entscheidbar (Rice-Shapiro): Es gibt keinen perfekten bug finder der alle nicht-terminierenden Programme erkennt.

Aber es gibt mächtige heuristische Verfahren, die für relativ viele Programme aus der Praxis (Gerätetreiber)

• Termination beweisen können, oder
• Gegenbeispiele finden können.

4.8: Das Postsche Korrespondenzproblem

Definition

Postsche Korrespondenzproblem, Post's Correspondence Problem, PCP:
Gegeben: Eine endliche Folge

$(x_1,y_1),\dots ,(x_k,y_k)$, wobei

$x_i,y_i\in {\mathrm{\Sigma }}^{+}$
Problem: Gibt es eine Folge von Indizes

$i_i,\dots ,i_n\in \{1,\dots ,k\}$,

$n>0$, mit

$x_{i_1}\dots x_{i_n}=y_{i_1}\dots y_{i_n}$?
Dann wird

$i_1,\dots ,i_n$ als eine Lösung der Instanz

$(x_1,y_1),\dots ,(x_k,y_k)$ des PCP Problems bezeichnet.

Entscheidbarkeit des PCP

Das PCP ist semi-entscheidbar
Beweis:
Die möglichen Lösungen werden der Länge nach aufgezählt und auf korrektheit überprüft.

Modifiziertes PCP, MPCP

Gegeben: wie beim PCP
Problem: Gibt es eine Lösung

$i_1,\dots ,i_n$ mit

$i_1=1$?

Reduzierbarkeit des MPCP

$MPCP\le PCP$

$H\le MPCP$

Unentscheidbarkeit des PCP
Aus

$H\le PCP$ folgt direkt, dass das PCP unentscheidbar ist
Das PCP ist auch für

$\mathrm{\Sigma }=\{0,1\}$ unentscheidbar.

Weitere bemerkungen:

• Das PCP ist entscheidbar falls
  $|\mathrm{\Sigma }|=1$
• Das PCP ist entscheidbar falls
  $k\le 2$
• Das PCP ist unentscheidbar falls
  $k\ge 5$
• Für
  $k=3,4$ ist noch offen, ob das PCP unentscheidbar ist.

4.9 Unentscheidbare CFG-Probleme

• Für DFAs ist fast alles entscheidbar:
  $L(A)=\mathrm{\varnothing },L(A)=L(B),\dots$
• Für TMs ist fast nichts entscheidbar:
  $L(M)=\mathrm{\varnothing },L(M_1)=L(M_2),\dots$
• Für CFGs ist manches entscheidbar
  $(L(G)=\mathrm{\varnothing },w\in L(G))$, und manches unentscheidbar

Unentscheidbare Probleme:

Für CFGs

$G_1,G_2$ sind folgende Probleme unentscheidbar:

• $P_1$: ist
  $L(G_1)\cap L(G_2)=\mathrm{\varnothing }$? -> Beweis: Folie 340
• $P_2$: ist
  $|L(G_1)\cap L(G_2)|=\mathrm{\infty }$? -> Beweis: Folie 343
• $P_3$: ist
  $L(G_1)\cap L(G_2)$ kontextfrei? -> Beweis: Folie 343
• $P_4$: ist
  $L(G_1)\subseteq L(G_2)$? -> Beweis: Folie 344
• $P_5$: ist
  $L(G_1)=L(G_2)$? -> Beweis: Folie 344

Da

$L(G_1)$ und

$L(G_2)$ aus dem Beweis zu

$P_1$ DCFL sind, gilt sogar, dass die Probleme

$P_1$ bis

$P_4$ bereits für DCFLs unentscheidbar sind.

Für zwei DPDAs

$M_1$ und

$M_2$ ist

$L(M_1)=L(M_2)$ jedoch entscheidbar.

Weitere unentscheidbare Probleme:

Für eine CFG

$G$ sind folgende Probleme unentscheidbar:

• Ist
  $G$ mehrdeutig?
• Ist
  $L(G)$ regulär?
• Ist
  $L(G)$ deterministisch (DCFL)?

Für eine CFG

$G$ und einen RE

$\alpha$ ist

$L(G)=L(\alpha )$ unentscheidbar

4.10 Primitiv Rekursive Funktionen

Es werden Funktionen

${\mathbb{N}}^k\to \mathbb{N},k\ge 0$ betrachtet.

${\mathbb{N}}^0\to \mathbb{N}$ wird mit

$\mathbb{N}$ identifiziert,

$c()$ mit

$c$.
Definition der primitiv rekursiven Funktionen

• Fixe Basisfunktion: z.B.
  $s(x)=x+1$
• Funktionskomposition: z.B.
  $f(x,y)=g(x,h(x,y))$
• Fixe Art der Rekursion: z.B.
  $$\begin{gathered} f(0)=1 \\ f(n+1)=n\ast f(n) \end{gathered}$$

Basisfunktionen

• Die konstante Funktion 0
• Die Nachfolgerfunktion
  $s(n)=n+1$
• Die Projektionsfunktionen
  ${\pi }_i^k:{\mathbb{N}}^k\to \mathbb{N},1\le i\le k:$
  
  $${\pi }_i^k(x_1,\dots ,x_k)=x_i$$

Komposition

Die Komposition von

$g$ und

$h_1,\dots ,h_k$ erzeugt die Funktion

$f$

$$f(\overline{x})=g(h_1(\overline{x}),\dots ,h_k(\overline{x}))$$

wobei

$\overline{x}=(x_1,\dots ,x_n)$ und

$$\begin{gathered} f:{\mathbb{N}}^n\to \mathbb{N} \\ g:{\mathbb{N}}^k\to \mathbb{N} \\ {h}_i:{\mathbb{N}}^n\to \mathbb{N}(i=1,\dots ,k) \end{gathered}$$

Primitive Rekursion

Das Schema der primitiven Rekursion erzeugt aus

$g$ und

$h$ die Funktion

$f$

$$\begin{gathered} f(0,\overline{x})=g(\overline{x}) \\ f(m+1,\overline{x})=h(f(m,\overline{x}),m,\overline{x}) \end{gathered}$$

wobei

$\overline{x}=(x_1,\dots ,x_n)$ und

$$\begin{gathered} f:{\mathbb{N}}^{n+1}\to \mathbb{N} \\ g:{\mathbb{N}}^n\to \mathbb{N} \\ h:{\mathbb{N}}^{n+2}\to \mathbb{N} \end{gathered}$$

Primitiv Rekursive Funktionen

Die Menge PR der primitiv rekursiven Funktionen ist die folgende induktiv definierte Teilmenge aller Funktionen

${\mathbb{N}}^k\to \mathbb{N},k\ge 0$:

• Die Basisfunktinen 0,
  $s$, und
  ${\pi }_i^k$ sind primitiv rekursiv
• Sind
  $g$ und
  $h_i$ primitiv rekursiv, dann auch ihre Komposition
  
  $$f(\overline{x})=g(h_1(\overline{x}),\dots ,h_k(\overline{x}))$$
• Sind
  $g$ und
  $h$ primitiv rekursiv, dann auch die mit primitver Rekursion definierte Funktion
  
  $$\begin{gathered} f(0,\overline{x})=g(\overline{x}) \\ f(m+1,\overline{x})=h(f(m,\overline{x}),m,\overline{x}) \end{gathered}$$

Jede primitiv-rekursive Funktion ist total

Erweiterte Komposition

$f$ ist eine erweiterte Komposition der Funktionen

$g_1,\dots ,g_k$ falls

$$f(x_1,\dots ,x_n)=t$$
so dass

$t$ ein Ausdruck ist, der nur aus den Funktionen

$g_1,\dots ,g_k$ und den Variablen

$x_1,\dots ,x_n$ besteht.
Eine erweiterte Komposition von PR Funktionen ist wieder PR

Das erweiterte Schema der primitiven Rekursion erlaubt

$$\begin{gathered} f(0,\overline{x})=t_0 \\ f(m+1,\overline{x})=t \end{gathered}$$

wobei

• $t_0$ enthält nur PR Funktionen und die
  $x_i$
• $t$ enthält nur
  $f(m,\overline{x})$, PR Funktionen,
  $m$ und die
  $x_i$

Das erweiterte Schema der primitiven Rekursion führt nicht aus PR hinaus.

Moral:
Primitive Rekursion erlaubt

$f(m+1,\overline{x})=\dots f(m,\overline{x})\dots$

Prädikate

Sei

$P(x)$ ein Prädikat, d.h. ein logischer Ausdruck, der in Abhängigkeit von

$x\in {\mathbb{N}}_0$ den Wert true oder false liefert.
Dann kann P in natürlicher Weise eine Funktion

$$\hat{P}:\mathbb{N}\to \{0,1\}$$
zugeordnet werden:

$\hat{P}(x)=1$ gdw.

$P(x)=$ true

$P$ ist primitiv rekursiv genau dann, wenn

$\hat{P}$ primitiv rekursiv ist.

Ist

$P$ primitiv rekursiv, dann auch der beschränkte max-Operator

$$max\{x\ge n|P(x)\}=:q(n)$$
wobei

$max\mathrm{\varnothing }:=0$

Ist

$P$ primitiv rekursiv, dann auch der beschränkte Existenzquantor

$$\mathrm{\exists }x\le n.P(x)=:Q(x)$$

4.11 PR = LOOP

Hauptproblem bei LOOP

$\to$ PR:
Kodierung aller Variablen eines LOOP-Programms in einer Zahl

Cantorsche Paarungsfunktion

Die Cantorsche Paarungsfunktion

$$c(x,y):=(\genfrac{}{}{0ex}{}{x+y+1}{2})+x=(x+y)(x+y+1)/2+x$$

ist eine Bijektion zwischen

${\mathbb{N}}^2$ und

$\mathbb{N}$

Die funktion

$x\mapsto (\genfrac{}{}{0ex}{}{x}{2})$ ist PR:

$$\begin{gathered} (\genfrac{}{}{0ex}{}{0}{2})=0 \\ (\genfrac{}{}{0ex}{}{n+1}{2})=(\genfrac{}{}{0ex}{}{n}{2})+n \end{gathered}$$

Mit Komposition ist auch

$c$ PR:

$$c(x,y)=(\genfrac{}{}{0ex}{}{x+y+1}{2})+x$$

Mit

$c$ kodiert man

$k+1$ Tupel:

$$⟨n_0,n_1,\dots ,n_k⟩:=c(n_0,c(n_1,\dots ,c(n_k,0)\dots ))$$

Die umkehrfunktionen

$p_1$ und

$p_2$ von c werden gebraucht:

$$p_1(c(x,y))=x{p}_2(c(x,y))=y$$

Damit können Projektionsfunktionen auf Tupeln definiert werden

$$\begin{gathered} d_0(n):=p_1(n) \\ {d}_1(n):=p_1(p_2(n)) \\ ⋮ \\ {d}_k(n):=p_1(p_2\dots p_2(n)\dots ),\text{k-mal }{p}_2 \end{gathered}$$

Sind

$p_1,p_2$ PR, so auch

$d_0,\dots ,d_k$

Die Umkehrfunktionen von

$c$ sind PR definierbar:

$$\begin{gathered} p_1(n)=max\{x\le n|\mathrm{\exists }y\le n.c(x,y)=n\} \\ {p}_2(n)=max\{y\le n|\mathrm{\exists }x\le n.c(x,y)=n\} \end{gathered}$$

PR = LOOP:
Die Primitiv rekursiven sind genau die LOOP-berechenbaren Funktionen.

Reversible Kodierung von Zahlenfolgen als Zahlen

• $\{0,\dots ,k{\}}^{\ast }$: Kodiere
  $(i_1,\dots ,i_n)$ als Zahl
  $i_1\dots i_n$ zur Basis
  $k+1$
• ${\mathbb{N}}^n$: Mit iterierter Paarfunktion
  $c:⟨i_1,\dots ,i_n⟩$
  NB: n muss beim Dekodieren bekannt sein, denn z.B.
  $1=c(0,1)=c(0,c(0,1))$
• ${\mathbb{N}}^{\ast }$: Auch mit
  $⟨\dots ⟩$ reversibel kodierbar
• ${\mathbb{N}}^{\ast }$: Kodiere
  $(i_1,\dots ,i_n)$ als
  $2^{i_1}{3}^{i_2}\cdots p_n^{i_n}$, wobei
  $p_n$ die n-te Primzahl ist. Dekodierung = Primzahlzerlegung

4.12 Die

$\mu$-rekursiven Funktionen

• Mit PR kann man nur beschränkt suchen:
  $n,\dots ,0$
• Die unbeschränkte Suche
  $0,\dots$ erfordert so etwas wie
  
  $$f(n)=\dots f(n+1)\dots$$
• Der
  $\mu$-Operator formalisiert diese Art der Suche
• Damit erhält man alle berechenbaren Funktionen
• Andere Such- byw. Rekursionsschemata sind (im Prinzip!) nicht notwendig.

Notation:

$f(n)=\mathrm{\perp }$ bedeutet "

$f(n)$ ist undefiniert"

$\mu$-Operator

Sei

$f:{\mathbb{N}}^k+1\to \mathbb{N}$ eine (nicht notwendigerweise totale) Funktion. Die durch Anwendung des

$\mu$-Operators entstehende Funktion

$\mu f:{\mathbb{N}}^k\to \mathbb{N}$ ist definiert durch:

$$\bar{x}\mapsto \{\begin{array}{ll}min\{n\in \mathbb{N}|f(n,\bar{x})=0& \text{falls ein solches }n\text{ existiert und }f(m,\bar{x})\ne \mathrm{\perp }\text{für alle }m\le n\\ \mathrm{\perp }& \text{sonst}\end{array}$$

Intuitiv:

$$\begin{gathered} \mu f(\bar{x})=find(0,\bar{x}) \\ find(n,\bar{x})=\text{if }f(n,\bar{x})=0\text{ then }n\text{ else }find(n+1,\bar{x}) \end{gathered}$$

$\mu$-rekursiv

Die Menge der

$\mu$-rekursiven Funktionen ist induktiv wie folgt definiert:

• Die Basisfunktionen
  $0,+1,{\pi }_i^k$ sind
  $\mu$-rekursiv/
• Wenn eine Funktion durch Komposition, primitive Rekursion oder den
  $\mu$-Operator aus
  $\mu$-rekursiven Funktionen definiert werden kann, ist sie
  $\mu$-rekursiv

$\mu$R=WHILE

Die

$\mu$-rekursiven sind genau die WHILE-berechenbaren Funktionen.

Kleene:
Für jede n-stellige

$\mu$-rekursive Funktion

$f$ gibt es zwei

$n+1$-stellige PR Funktionen

$h$ und

$h^{\prime }$, so dass

$$f(\bar{x})=h(\mu h^{\prime }(\bar{x}),\bar{x})$$

4.12 Die Ackermann-Funktion

$$\begin{gathered} a(0,n)=n+1 \\ a(m+1,0)=a(m,1) \\ a(m+1,n+1)=a(m,a(m+1,n)) \end{gathered}$$

• Dies ist keine PR Definition
• Aber:
  $\nRightarrow a$ ist nicht PR
• Ziel: a ist berechenbar, total, aber nicht PR

Fakt:
Die Ackermann-Funktion ist (OCaml-)berechenbar.

Lemma:
Die Ackermann-Funktion ist total.

Lexikographische Ordnung

$$(m,n)>(m^{\prime },n^{\prime }):\iff m>m^{\prime }\vee (m=m^{\prime }\wedge n>n^{\prime })$$

Die lexikographische Ordnung auf

$\mathbb{N}\times \mathbb{N}$ terminiert

Warnung: Kein Beweise der Totalität einer rekursiven Funktion:
"denn in jedem rekursiven Aufruf wird eines der Argumente kleiner"

Lemma:
Für jede PR-Funktion

$f:{\mathbb{N}}^k\to \mathbb{N}$ gibt es ein

$t\in \mathbb{N}$, so dass

$$\mathrm{\forall }\bar{x}\in {\mathbb{N}}^k.f(\bar{x})<a(t,max\bar{x})$$

Satz:
Die Ackermann-Funktion ist nicht PR

Oberflächlich intuitiv: Die Ackermann-Funktion wächst schneller als alle PR-Funktionen
Genauer: Die Funktion

$n\mapsto a(n,n)$ wächst schneller als alle PR funktionen
Intuitiver Grund:

• Für fixes
  $t$ ist
  $n\mapsto a(t,n)$ PR, denn dies ist
  $A_t$
• $A_t$ bracht aber eien PR Definition der Länge
  $O(t)$
• Um
  $n\mapsto a(n,n)$ PR zu berechnen, müsste die Länge der PR Definition dynamisch mit der Eingabe wachsen

Da die Ackermann-Funktion total, berechenbar und nicht PR ist wurde gezeigt, dass die PR Funktionen eine echte Teilklasse der berechenbaren totalen funktionen ist.

5. Komplexitätstheorie

• Was ist mit beschränkten Mitteln (zeit & platz) berechenbar?
• Wieviel Zeit&Platz braucht man, um ein bestimmtes Problem / Sprache zu entscheiden?
• Komplexität eines Problems, nicht eines Algorithmus

Zentrale Frage:
Für welche Probleme gibt es / gibt es keine polynomielle Algorithmen?

Komplexitätsklasse P:
P = die von DTM in polynomieller Zeit lösbaren Probleme, = die "leichten" Probleme (feasible problems)

• $A\in P$ wird durch Angabe eines Algorithmus bewiesen, z.B. CYK beweist:
  
  $$\{(G,w)|G\in \text{CFG},w\in L(G)\}\in P$$
• $A\notin P$ zu zeigen ist viel schwieriger! Für sehr viele Probleme ist es nicht bekannt, ob sie zu P gehören oder nicht.

Viele der wichtigsten Probleme der Informatik sind der Gestalt:

$$\text{Gegeben }X,\text{ gibt es }Y\text{ mit }R(X,Y)?$$

• SAT:
  $X$ = Boole'sche Formel,
  $Y$ = Belegung der Variablen von
  $X$,
  $R(X,Y):=\text{"Y erfüllt X"}$
• HAMILTONKREIS:
  $X$ = Graph,
  $Y$ = Kreis von
  $X$,
  $R(X,Y):=\text{"Y besucht alle Knoten von X genau einmal"}$
• EULERKREIS:
  $X$ = Graph,
  $Y$ = Kreis von
  $X$,
  $R(X,Y):=\text{"Y besucht alle Kanten von X genau einmal"}$

Die

$Y$ sind "Lösungskandidaten". In allen diesen Problemen:

• Prüfen ob ein Kandidat tatsächlich eine Lösung ist, ist in P.
• Es gibt jedoche exponentiell viele Kandidaten.
• Deshalb hat ein naiver Suchalgorithmus, der alle Kandidaten aufzählt und prüft, exponentielle Laufzeit.

Für kein solches Problem ist es bewiesen worden, dass es nicht in P liegt.
Die Frage, ob alle solche Probleme in P liegen, ist die wichtigste offene Frage der Informatik.

Äquivalente Formulierung
Diese Probleme können nichtdeterministisch in polynomieller Zeit gelöst werden: Wähle einen Kandidaten und prüfe, ob er eine Lösung ist.

Komplexitätsklasse NP:
NP = die von NTM in polynomieller Zeit lösbaren Probleme

Zentrale Frage:
P = NP ?

5.1 Die Komplexitätsklasse P

Berechnungsmodell:
DTM: deterministische Mehrband-TM

Definition:

$tim{e}_M(w):=$ Anzahl der Schritte bis die DTM

$M[w]$ hält

$\in \mathbb{N}\cup \{\mathrm{\infty }\}$
Sei

$f:\mathbb{N}\to \mathbb{N}$ eine totale Funktion.
Klasse in der Zeit

$f(n)$ entscheidbaren Sprachen:

$$TIME(f(n)):=\{A\subseteq {\mathrm{\Sigma }}^{\ast }|\mathrm{\exists }\text{ DTM }M.A=L(M)\wedge \mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast }.{\text{time}}_M(w)\le f(|w|)\}$$

Merke:

• $n$ ist implizit die Länge der Eingabe
• Die DTM entscheidet die Sprache
  $A$ in
  $\le f(n)$ Schritten

Es werden nun Polynome mit Koeffizienten

$a_k,\dots ,a_0\in \mathbb{N}$ betrachtet:

$$p(n)=a_k{n}^k+\cdots +a_{1}n+a_0$$
Definition:

$$P:=\bigcup _{pPolynom}TIME(p(n))$$

Damit gilt auch

$$P=\bigcup _{k\ge 0}TIME(O(n^k))$$

wobei

$$TIME(O(f)):=\bigcup _{g\in O(f)}TIME(g)$$

Bemerkungen

• $O(n\log n)\subset O(n^2)$
• $n^{\log n},2^n\notin O(n^k)$ für alle
  $k$

Analog zu Sprachen nennen wir eine Funktion

$f:\mathbb{N}\to \mathbb{N}$ in polynomieller Zeit berechenbar, gdw. es eine DTM

$M$ gibt, die

$f$ berechnet und

$tim{e}_m(w)\le p(|w|)$ für ein Polynom

$p$

• Warum P und nicht (z.B.)
  $O(n^{17})$?
  Um robust bzgl. Maschinenmodell zu sein:
  1-Band DTM braucht
  $O(t^2)$ Schritte um t schritte einer k-Band DTM zu simulieren.
  fast alle bekannten "vernünftigen" Maschinenmodelle lassen sich von einer DTM in polynomieller Zeit simulieren.
  Offen: Quantencomputer
• Warum TM?
  Historisch. Ebenfalls möglich: (z.B.) WHILE.
  Aber zwei mögliche Kostenmodelle:
  • Uniform:
    $x_i:=x_j+n$ kostet 1 Zeiteinheit
  • Logarithmisch:
    $x_i:=x_j+n$ kostet
    $\log x_j$ Zeiteinheiten

5.2 Die Komplexitätsklasse NP

Berechnungsmodell:
NTM = nichtdeterministische Mehrband-TM

• NP ist die Klasse der Sprachen, die von einer NTM in polynomieller Zeit akzeptiert werden
• D.h. Eine Sprache A liegt in NP gdw. es ein Polynom
  $p(n)$ und eine NTM M gibt sodass:
  • $L(M)=A$ und
  • für alle
    $w\in A$ kann
    $M[w]$ in
    $\le p(|w|)$ Schritten akzeptieren, d.h. einen Endzustand erreichen.

Definition

$$ntim{e}_m(w):=\{\begin{array}{ll}\text{minimale Anzahl der Schritte bis NTM }M[w]\text{ akzeptiert}& \text{falls }w\in L(M)\\ 0& \text{falls }w\notin L(M)\end{array}$$

Sei

$f:\mathbb{N}\to \mathbb{N}$ eine totale Funktion

$$\begin{gathered} NTIME(f(n)):=\{A\subseteq {\mathrm{\Sigma }}^{\ast }|\mathrm{\exists }\text{NTM }M.A=L(M)\wedge \mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast }.ntim{e}_M(w)\le f(|w|)\} \\ NP:=\bigcup _{pPolynom}NTIME(p(n)) \end{gathered}$$

bemerkungen:

• $P\subseteq NP$
• Seit etwa 1970 ist offen ob P = NP.

Weitere Bemerkungen zur Definition von NP:
Akzeptierende NTM

$M$

• braucht für
  $w\notin L(M)$ nicht zu halten
• kann für
  $w\in L(M)$ auch beliebig lange berechnungsfolgen haben.

Äquivalente Definition NP' von NP
Die NTM

$M[w]$ muss nach maximal

$p(|w|)$ schritten halten.
NP'

$\subseteq$ NP: Klar
NP

$\subseteq$ NP': falls

$A\in$ NP mit Polynom

$p$ und NTM

$M$, so kann ein NTM

$M^{\prime }$ konstruiert werden mit

$L(M^{\prime })=A$, so dass

$M^{\prime }[w]$ immer innerhalb von polynomieller Zeit hält.

• Eingabe
  $w$
• Schreibe
  $p(|w|)$ auf ein getrenntes Band ("timer")
• Simuliere
  $M[w]$, aber dekrementiere timer nach jedem Schritt
• Wird timer = 0, ohne dass
  $M$ gehalten hat, halte in einem nicht-Endzustand ("timeout")

Erinnerung:
Viele Probleme sind von der Art, dass

• schwer ist, zu entscheiden, ob sie lösbar sind,
• leicht ist, zu entscheiden, ob ein Lösungsvorschlag eine Lösung ist.

Formalisierung:
Definition:
Sei

$M$ eine DTM mit

$L(M)\subseteq \{w\mathrm{\#}c|w\in {\mathrm{\Sigma }}^{\ast },c\in {\mathrm{\Delta }}^{\ast }\}$

• Falls
  $w\mathrm{\#}c\in L(M)$, so heißt
  $c$ Zertifikat für
  $w$
• $M$ ist ein polynomiell beschränkter Verifikator für die Sprache
  $\{w\in {\mathrm{\Sigma }}^{\ast }|\mathrm{\exists }c\in {\mathrm{\Delta }}^{\ast }.w\mathrm{\#}c\in L(M)\}$ falls es ein Polynom
  $p$ gibt, so dass
  $tim{e}_M(w\mathrm{\#}c)\le p(|w|)$

NB (merke):
In Zeit

$p(n)$ kann M maximal die ersten p(n) Zeichen von

$c$ lesen. Daher genügt für

$w$ ein Zertifikat der Länge

$\le p(w)$

Satz:

$A\in$ NP gdw. es einen polynomiell beschränkten Verifikator für A gibt

Fazit:

• P sind die Sprachen, bei denen
  $w\in L$ schnell entschieden werden kann
• NP sind die Sprachen, bei denen ein Zertifikat für
  $w\in L$ schnell verifiziert/überprüft werden kann.

Intuition:
Es ist leichter, eine Lösung zu verifizieren als zu finden.
Aber:
Noch wurde von keiner Sprache bewiesen, dass sie in NP\P liegt

5.3 NP-Vollständigkeit

• Polynomielle Reduzierbarkeit
  ${\le }_p$
• NP-vollständige Probleme = härteste Probleme in NP, alle anderen Probleme in NP darauf polznomiell reduzierbar
• SAT ist NP-vollständig

Definition

Sei

$A\subseteq {\mathrm{\Sigma }}^{\ast }$ und

$B\subseteq {\mathrm{\Gamma }}^{\ast }$
Dann ist

$A$ polynomiell reduzierbar auf

$B$,

$A{\le }_{p}B$, gdw. es eine totale und von einer DTM in polynomieller Zeit berechenbare Funktion

$f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ gibt, so dass für alle

$w\in {\mathrm{\Sigma }}^{\ast }$

$$w\in A⟺f(w)\in B$$

Die Relation

${\le }_p$ ist transitiv, da $p_2(p_1(n)) ein Polynom ist falls

$p_1$ und

$p_2$ polynome sind.

Die Klassen P und NP sind unter polynomieller Reduzierbarkeit nach unten abgeschlossen:

$$A{\le }_{p}B\in P/NP⟹A\in P/NP$$

NP-Schwer:
Ein Problem ist NP-Schwer, wenn es mindestens so schwer wie alles in NP ist:

• Eine Sprache
  $L$ ist NP-Schwer gdw.
  $A{\le }_{p}L$ für alle
  $A\in NP$
• Eine Sprache
  $L$ ist NP-Vollständig gdw.
  $L$ NP-schwer ist und
  $L\in NP$
• NP-Vollständige Probleme sind die schwierigsten Probleme in NP: alle Probleme in NP sind polynomiell auf sie reduzierbar

Lemma:
Es gilt P=NP gdw. ein NP-vollständiges Problem in P liegt.

Starke vermutung:

• P
  $\ne$ NP
• d.h. kein NP-vollständiges Problem ist in P

Aussagenlogik

Syntax der Aussagenlogik:

• Variablen:
  $X\to x|y|z|\dots$
• Formeln:
  $F\to X|\mathrm{\neg }F|(F\wedge F)|(F\vee F)|X$

Man darf einige Klammern weglassen:

• Äußerste Klammern:
  $(x\vee y)\wedge z$ statt
  $((x\vee y)\wedge z)$
• Assoziativität:
  $(x\vee y\vee z)\wedge \mathrm{\neg }x$ statt
  $((x\vee y)\vee z)\wedge \mathrm{\neg }x$

Abkürzungen

• $F_1\to F_2\equiv \mathrm{\neg }{F}_1\vee F_2$
• $\underset{i=1}{\overset{n}{\bigwedge }}{F}_i\equiv F_1\wedge \cdots \wedge F_n$

Semantik der Aussagenlogik:

• Eine Belegung ist eine Funktion von Variablen auf
  $\{0,1\}$.
  Bsp:
  $\sigma =\{x\mapsto 0,y\mapsto 1,z\mapsto 0,\dots \}$
• Belegungen werden mittels Wahrheitstabellen auf Formeln erweitert.
  Bsp:
  $\sigma ((\mathrm{\neg }x\wedge y)\vee (x\wedge \mathrm{\neg }z))=1$
• Eine Formel F ist erfüllbar gdw. es eine Belegung
  $\sigma$ gibt mit
  $\sigma (F)=1$

SAT

Gegeben: Eine aussagenlogische Formel F
Problem: ist F erfüllbar?

Lemma:
SAT

$\in$ NP

Satz: (Cook, 1971)
SAT ist NP-vollständig

Von der Lösbarkeit zur Lösung

Die Berechnung einer erfüllenden Belegung kann auf SAT "reduziert" werden.
Sei

$F$ eine Formel mit den Variablen

$x_1,\dots ,x_k$:

wobei

$F[x:=b]=F$ mit

$x$ ersetzt durch

$b$

Entscheidung von SAT in Zeit

$O(f(n))$

$⟹$ Berechnung einer erf. Bel. in Zeit

$O(n\ast (f(n)+n))$, falls es eine gibt.

$$\begin{gathered} f(n)\text{ polynomiell }⟹n\ast (f(n)+n)\text{ polynomiell} \\ f(n)\text{ exponentiell }⟹n\ast (f(n)+n)\text{ exponentiell} \end{gathered}$$

Bemerkungen:

• Die Redunktion der Lösungsberechnung auf SAT ist eine rein theoretische Konstruktion
• Sie zeigt, dass man sich auf SAT beschränken kann, wenn man nur an polynomiell/exponentiell interessiert ist
• Alle bekannten Entscheidungsverfahren für SAT berechnen auch eine Lösung

Von NP-schwer zu "NP-leicht"

• Bis vor ca. 20 Jahren: NP-vollständig -> Todesurteil
• in den letzten 15 jahren: Spektakuläre fortschritte bei der implementierung von SAT-Lösern
  Stand der Kunst: Erfüllbar bis 10⁵ variablen, Unerfüllbar bis 10³ variablen
• Jetzt: NP-vollständig -> Hoffnung durch SAT
• Paradigma: SAT (Logik!) als universelle Sprache zur Kodierung kombinatorischer Probleme
  Reduktion auf SAT manchmal schneller als problemspezifische Löser, und fast immer einfacher.

doc todos

• TODO: Folien 98-103 verstehen
• vorherige TODOs machen
• TODO: Folie 97: keine reguläre Lösung???
• TODO: bei Problemen nochmal die Beweise anschauen
• TODO: Pumping-Lemma again
• TODO: 261-299: Primitiv-Rekursive Funktionen bis Ackerman-Funktion

tags: Theo