Inhaltsverzeichnis

Sprachen

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

(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
		Typ 0	Typ 1	ND	D	Typ 3
Name		Alle Grammatiken	Kontextsensitiv	Kontextfrei		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$	uvw muss existieren
$\|uv\| \le n$	uvw mindestens n lang
$uv^iw \in L \forall i \ge 0$	uvw pumpbar

Beweisidee

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

Minimalautomat

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$	uvwxy eins von beiden muss existieren
$\|vwx\| \le n$	uvwxy mindestens n lang
$uv^iwx^iy \in L \forall i \ge 0$	uvwxy 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

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	Eingabealphabet	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	Eingabealphabet	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	Eingabealphabet	Konstanten / Terminalsymbolen
$\Gamma$	Menge	Kelleralphabet		$\# \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'\ldots)$

$(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'\ldots)$	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, \ldots)$

$(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	Eingabealphabet	Konstanten / Terminalsymbolen	$\Sigma \subset \Gamma$
$\Gamma$	Menge	Arbeitsalphabet		$\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$