%Copyright 2013 Dirk Winkel
%This file is free software: you can redistribute it and/or modify
%it under the terms of the GNU Affero General Public License as
%published by the Free Software Foundation, either version 3 of the 
%License, or (at your option) any later version.

%This program is distributed in the hope that it will be useful,
%but WITHOUT ANY WARRANTY; without even the implied warranty of
%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%GNU Affero General Public License for more details.

%You should have received a copy of the GNU Affero General Public 
%License along with GradeMan.  If not, see 
%<http://www.gnu.org/licenses/>.
\documentclass[12pt,a4paper,oneside]{article}
% -----------------------------------------------------------------------------------------
\usepackage[latin1]{inputenc}
\usepackage[centertags]{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{newlfont}
\usepackage{amsxtra}
\usepackage{amstext}
\usepackage[ngerman]{babel}
\usepackage{latexsym}
\usepackage{geometry}
\usepackage{pifont}
\usepackage{ulem}
\usepackage{color}
\usepackage{marvosym}
\usepackage[T1]{fontenc}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{array}
\usepackage{booktabs}
\usepackage{dcolumn}
\usepackage{units}
\usepackage{rotating}
\usepackage{hyperref}
\usepackage{floatflt}
%\usepackage{makeidx}
\usepackage[usenames,dvipsnames]{pstricks}
\usepackage{epsfig}
\usepackage{pst-grad} % For gradients
\usepackage{pst-plot} % For axes
%\usepackage{qtree}

\usepackage{a4wide}
\usepackage{textcomp}
\usepackage{tikz}
\usetikzlibrary{automata}
\usepackage{mdframed}

\textheight25cm
% -----------------------------------------------------------------------------------------
\begin{document}
% -----------------------------------------------------------------------------------------
%	 Titel
% -----------------------------------------------------------------------------------------
\headheight0cm\headsep0cm\topskip0cm\footskip0cm
\begin{floatingfigure}[l]{3cm}
 \includegraphics[width=2.8cm, height=2.8cm, angle=270]{siegel}
\end{floatingfigure}
\begin{small}
Philipps-Universität Marburg

Fachbereich 12 Informatik

VL Theoretische Informatik

Prof. Rita Loogen

Wintersemester 2012/13

Zusammengefasst von: Dirk Winkel

\end{small}
\begin{center}
{\LARGE \textbf{Zusammenfassung Skript}}
\end{center}
% -----------------------------------------------------------------------------------------
%	Hauptext
% -----------------------------------------------------------------------------------------
\tableofcontents

\section{Einführung}
\begin{itemize}
\item Ein \textit{Alphabet} $\Sigma$ ist eine Menge von \textit{Zeichen}, \textit{Buchstaben} oder \textit{Symbolen}.
\item Eine \textit{formale Sprache} $L$ über einem Alphabet $\Sigma$ ist eine Teilmenge von $\Sigma^*$:
$$ L \subseteq \Sigma^* \Leftrightarrow L \in \mathfrak{P}(\Sigma^*) $$
\item Im allgemeinen sind Sprachen unendliche Mengen, die mit Hilfe von Grammatiken oder Automaten endlich beschrieben werden können.
\item Beispiel für eine induktive Definition: $\varepsilon \in \Sigma^*$; $ w \in \Sigma^*, a \in \Sigma^* \Rightarrow aw \in \Sigma^*$
\item \textit{Konkatenation} bezeichnet die Verkettung von Wörtern
\item \textit{Spiegelung} dreht das Wort um: $\overleftarrow{\varepsilon} := \varepsilon$; $\overleftarrow{wa} :=a\overleftarrow{w}$
\item \textit{Iteration} oder \textit{Potenz} bezeichnet die Vervielfachung eines Wortes: $w^0 := \varepsilon$; $w^{n+1}:=w^nw$
\item \textit{Mengenoperatoren} $\cup, \cap, \setminus$ sowie \textit{Komplexprodukt} $\cdot$, \textit{Potenz} $^n$ und \textit{Sernoperator} $^*$ sind für Sprachen wie für Mengen üblich definiert.
\item \textit{Binäre Relationen}  $\varrho$ setzten zwei Elemente einer Sprache $L$ ind Relation zu einander: $\varrho \subseteq L\times L$ (vgl. ``Funktion'').
\end{itemize}

\section*{\center{Teil I \\ Automatentheorie und Formale Sprachen}}

\section{Grammatiken und die Chomsky-Hierarchie}
\begin{itemize}
\item \textit{Grammatiken} erzeugen formale Sprachen (z.B. Backus-Naur-Form, hier aber formal wir folgt). Darin kommen vor:
\begin{itemize}
 \item \textit{Nonterminalsymbole} $N$ (Großbuchstaben $A, B, ...$), die weiter aufgelöst werden können zu
 \item \textit{Terminalsymbole}  $\in \Sigma = \{a, b, ...\}$ (Kleinbuchstaben $a, b, ...$ oder Ziffern) (nicht weiter auflösbar)
 \item \textit{Startsymbol} $S$ wo die Ableitung von Terminalwörtern (stetiges Ersetzen von Noterminalen zu Terminalen) beginnt
 \item \textit{Regeln} oder \textit{Produktionen} $P$ legen fest wie die Ableitungen zu bilden sind. Dabei sind links Nonterminale, rechts Nonterminale oder Terminale, dazwischen ein ``$\rightarrow$'' (Backus-Naur-Form: ``$::=$''). Bei mehreren Regeln zu einer gleichen linken Seite werden diese durch ``$|$'' getrennt.
\end{itemize}
\item Eine \textit{Grammatik} $G$ ist also ein Quadrupel: $G=(N, \Sigma, P, S)$
\item \textit{Satzformen} $\alpha, \beta, ...$ sind $\in N\times \Sigma$ Konkatenationen von Terminalen und Nonterminalen
\item Eine \textit{Ableitungsrelation} $\Rightarrow_G$ bezeichnet eine Ableitung $\alpha \Rightarrow_G \alpha'$ die in $G$ existiert.\\
$\Rightarrow_G^*$ ist dessen reflexive, transitive Hülle, also die Menge aller Konkatenationen von $\Rightarrow_G$.
\item Die \textit{von $G$ erzeugte Sprache} ist $L(G):= \{w\in \Sigma^* | S \Rightarrow_G^* w\}$ die Menge der von $G$ erzeugten Wörter.
\item für \textit{äquivalente Grammatiken} gilt $L(G_1)=L(G_2)$
\begin{mdframed}
\item \textit{\textbf{Chomsky-Hierarchie}: Typen der Sprachen:}
\begin{itemize}
 \item [\textbf{Typ0}] \textbf{(rekursiv aufzählbar)} Keine Einschränkung, also jede Grammatik\\
 $ \mathcal{L}_0(\Sigma) = L(\Sigma, TM) = L(\Sigma, DTM) $
 \item [\textbf{Typ1}] \textbf{(kontextsensitiv)} Für jede Produktion $\alpha_1 \rightarrow \alpha_2$ gilt $|\alpha_1| \leq |\alpha_2|$ oder $\alpha_1 =S \wedge \alpha_2=\varepsilon$ (und, falls $S \rightarrow \varepsilon \in P$, $S$ nie auf rechter Regelseite)\\
 $ \mathcal{L}_1(\Sigma) = L(\Sigma, LBA) ?\supset? L(\Sigma, DLBA) $
 \item [\textbf{Typ2}] \textbf{(kontextfrei)} Die linke Regelseite ist immer genau ein Noterminalsymbol: $A \rightarrow \alpha$\\
 $ \mathcal{L}_2(\Sigma) = L(\Sigma, PDA) \supsetneqq L(\Sigma, DPDA) $
 \item [\textbf{Typ3}] \textbf{(regulär)} einseitig linear (z.B. \textit{rechtslinear}: $A \rightarrow wB$ oder $A \rightarrow w$)\\
 $ \mathcal{L}_3(\Sigma) = L(\Sigma, NFA) = L(\Sigma, DFA) = Reg(\Sigma) $
\end{itemize} 
\end{mdframed}
\item Die Menge aller Sprachen, die durch Grammatiken des Typs $i$ erzeugt werden, bezeichnet man als $\mathcal{L}_i$ [Skript: schnörkeligeres L, nicht \LaTeX vorhanden :-(]
\item $ \mathcal{L}_3(\Sigma) \subsetneqq \mathcal{L}_2(\Sigma) \subsetneqq \mathcal{L}_1(\Sigma) \subsetneqq \mathcal{L}_0(\Sigma) $ ($ \forall |\Sigma| \geq 2$)
\item \textit{$\varepsilon$-freie Grammatiken} haben auf der rechten Regelseite kein $\varepsilon$ (oder $S \rightarrow \varepsilon$).\\
Jede kontextfreie Grammatik kann in eine $\varepsilon$-freie kontextfreie Grammatik übersetzt werden.
\item \textit{Abzählbar} ist eine Sprache, falls eine bijektive Abbildung $f : \mathbb{N} \rightarrow L$ existiert.
\item Das \textit{Wortproblem} fragt, ob ein Wort $w \in L$ ist. Es ist für Typ1-Sprachen entscheidbar.
\end{itemize}

\section{Endliche Automaten}
\begin{itemize}
\item \textit{Darstellung}: Zustände in Kreisen, Eingangszustand mit einfachem Pfeil, Endzustände in Doppelkreisen, Zustandsübergänge mit Pfeilen (beschriftet)\\
\begin{tikzpicture}[node distance=3cm,auto]
\node[initial,initial text=,state] (0) {$q_0$};
\node[state] (1) [right of=0] {$q_1$};
\node[state] (2) [right of=1] {$q_2$};
\node[state,accepting] (3) [right of=2] {$q_3$};
\path[->] (0) edge[loop above] node {0} (0);
\path[->] (0) edge[bend left] node {1} (1);
\path[->] (1) edge node {1} (2);
\path[->] (1) edge[bend left] node {0} (0);
\path[->] (2) edge[loop above] node {1} (2);
\path[->] (2) edge node {0} (3);
\path[->] (3) edge[loop above] node {0,1} (3);
\end{tikzpicture}
\item Ein \textit{\textbf{DFA (deterministischer endlicher Automat)}} ist ein Quintupel $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ mit:
\begin{itemize}
 \item $Q$ einer Menge von Zuständen $q_i$
 \item $\Sigma$ einem Eingabealphabet
 \item $\delta(q, a)=q': Q \times \Sigma \rightarrow Q$ eine Transitions- oder Übergangsfunktion, die einen Zustand in einen anderen überführt
 \item $q_0 \in Q$ dem Startzustand
 \item $F \subset Q$ der Endzustandsmenge
\end{itemize}
\item DFA($\Sigma$) ist die Menge aller DFAs, $\mathcal{L}(\Sigma, \text{DFA})$ ist die Menge aller von DFAs erkennbaren Sprachen über $\Sigma$.
\item $\overline{\delta}(q, w)$ ist die \textit{Erweiterte Transitionsfunktion}, also eine Verkettung von Transitionen.
\item Ein \textit{\textbf{NFA (nicht-deterministischer endlicher Automat)}} erlaubt im Gegensatz zum DFA zu einer Transition $\delta(q, a)$ mehrere Zustände, in die die Transition führen kann, also $\delta(q, a)=\{q', q'', ...\}$, sowie $\varepsilon$-Transitionen.
\item Eine \textit{$\varepsilon$-Transition} ist eine Transition, die der NFA zufällig ausführt (kann, muss aber nicht ausgeführt werden). Jeder NFA kann in einen $\varepsilon$-freien überführt werden.
\item Eine \textit{Konfiguration} von $\mathcal{A}$ ist ein Paar $(q, w)$.
\item Eine \textit{Einzelschrittralation} $\vdash_\mathcal{A}$ ist eine Transition von einer Konfiguration in eine andere, die reflexive, transitive Hülle $\vdash_\mathcal{A}^*$ ist die Verkettung aller möglichen Einzelschrittrelationen.
\item \textit{Äquivalent} sind zwei Automaten $\mathcal{A}_1, \mathcal{A}_2$ wenn die von ihnen erkannten Sprachen $L(\mathcal{A}_1), L(\mathcal{A}_2)$ gleich sind.
\item Als \textit{$\varepsilon$-Hülle} $\hat{\varepsilon}(T)$ einer Zustandsmenge $T$ wird die Menge aller Zustände bezeichnet, die durch $\varepsilon$-Transitionen aus $T$ erreichbar sind.
\item Die \textit{Erweiterte Transitionsfunktion $\hat{\delta}(q,w)$} eines NFA ist Verkettung aller möglichen Transitionen einschließlich der $\varepsilon$-Hülle.
\item Die \textit{\textbf{Potenzmengenkonstruktion}} ist ein Verfahren einen NFA in einen DFA zu überführen.
\begin{itemize}
 \item \textit{Erreichbar} heißt ein Zustand $q$ falls es ein Wort $w\in \Sigma^*$ gibt mit $\overline{\delta}(q_0,w)=q$
 \item Für die Menge aller mit einer Eingabe erreichbaren Zustände im NFA wird ein eigener Zustand definiert (z.B. $q_{12}$ falls durch $a$ sowohl $q_1$ als auch $q_2$ erreicht werden kann). Ursprung kann dabei ein Zustand oder eine ebensolche Zustandsmenge (= Zustand in der Potenzmengenkonstruktion) sein.
 \item Dabei ist ein \textit{Senkenzustand} $\emptyset$ möglich, aus dem keine Transition heraus führt.
\end{itemize}
\end{itemize}

\section{Reguläre Ausdrücke}
\begin{itemize}
\item $[[ \cdot ]]$ ordnet dem Regulären Ausdruck $\cdot$ als Semantik eine Sprache zu.
\item Reguläre Ausdrücke werden ähnlich wie Sprachen angegeben: $a, b, ...$ sind einzelne Elemente (``Terminale''), $\alpha, \beta$ sind längere Ausdrücke.
\item Für Reguläre Ausdrücke $\alpha, \beta \in RA(\Sigma)$ gilt:
\begin{itemize}
 \item $ [[\Lambda]] := \emptyset$ ``leerer Ausdruck'' (Achtung: $[[\Lambda^*]] = \{\varepsilon\} \neq [[\Lambda]]$!)
 \item $ [[a]] := \{a\}$ Die Sprache mit dem einzigen Wort $a$
 \item $ [[(\alpha + \beta)]] := [[\alpha]] \cup [[\beta]]$ ``(nichtexklusives) oder''
 \item $ [[(\alpha \cdot \beta)]] := [[\alpha]] \cdot [[\beta]]$ ``und''
 \item $ [[(\alpha^*)]] := [[\alpha]]^*$ beliebige Widerholung, auch 0 mal
\end{itemize}
\item Der \textit{Satz von Kleene} liefert ein Konstruktionsverfahren, um aus einem Regulären Ausdruck einen NFA zu machen. Dabei werden $+$ (``oder''), $\cdot$ (``und'') und $^*$ (``widerholungen'') durch entsprechende Automaten ersetzt.
\item \textit{Analyse eines DFA (Methode von Kleene)} (Überführen in einen Regulären Ausdruck): Sei $W_{ij}^k :=\{w \in \Sigma | w \text{ überführt } q_i \text{ in } q_j \text{ ohne Benutzung von } q_{k+1}, .., q_n\}$. Dann gilt:
$$ L(\mathcal{A}) = \bigcup_{q_j \in F} W_{1j}^n$$ sowie
$$W_{ij}^{k+1} = W_{ij}^k \cup (W_{i,k+1}^k (W_{k+1, k+1}^k)^* W_{k+1,j}^k)$$
Damit kann rekursiv die Sprache des DFA aus einfachen Mengen dargestellt werden. Diese Darstellung läßt sich schließlich in einen regulären Ausdruck überführen.
\item \textit{Analyse eines DFA (Methode mit Äquivalenzsystem)}: Zu erstellen ist ein ``Gleichungssystem'' (für alle Zustände):\\
$x_n \sim~ax_1 + bx_2 + ...$ wobei $a$ bedeutet ``So komme ich in einem Schritt von $q_n$ zu $q_1$'' und $b$ bedeutet ``So komme ich in einem Schritt von $q_n$ zu $q_2$'' etc.. Hinter dem Endzustand steht noch ``$+\Lambda^* $''.\\
Dieses Gleichungssystem ist dann zu lösen, wobei ``$+$'' ein ``oder'' bedeutet und ``$\cdot$'' ein ``und''! Dabei gilt die \textit{Resolutionsregel}:
$$x \sim \alpha x + \beta \wedge \varepsilon \notin [[\alpha]] \Rightarrow x \sim \alpha^*\beta$$
Die Lösung nach $x_1$ ist der reguläre Ausdruck, der die Sprache des DFA beschreibt.
\end{itemize}

\section{Eigenschaften regulärer Sprachen}
\begin{itemize}
\item Die \textit{Nerode-Relation} $\varrho_L \subseteq \Sigma^* \times \Sigma^*$ einer Sprache $L$ ist die Menge aller zweier Worte $u, v$ für die $uw\in L \Leftrightarrow vw\in L$ ($\rightarrow$ Zyklus!)
\item Eine \textit{Äquivalenzklasse} $[u]$ eines Wortes $u$ ist die Menge aller Wörter, die mit $u$ in einer Äquivalenzrelation stehen: $[u] := \{v \in \Sigma^* | (u, v) \in \varrho_L\}$
\item \textit{Satz von Myhill, Nerode}: Eine Sprache $L$ ist $\in L(\Sigma, DFA)$ wenn sie endliche viele Äquivalenzklassen hat: $L \in \mathcal{L}_3 \Leftrightarrow Index(\varrho_L)<\infty$\\
Endliche Sprachen sind damit immer $\in \mathcal{L}_3$.
\item Ein \textit{Äquivalenzklassenautomat} $= (Q, \Sigma, \delta, q_0, R)$ ist definiert mit:
\begin{itemize}
 \item $Q=\{[x_1], .., [x_k]\}$
 \item $q_0 := [\varepsilon]$
 \item $\delta([u], a) := [ua]$
 \item $F := \{[x_i] | [x_i] \subseteq L\}$
\end{itemize}
\item Der \textit{Minimalautomat} einer Sprache $L \in \mathcal{L}_3$ entspricht bis auf Isomorphie dem Äquivalenzklassenautomaten. Er kann bestimmt werden durch:
\begin{itemize}
 \item Elimination aller nicht erreichbaran Zustände
 \item Zusammenfassen aller äquivalenten Zustände
\end{itemize}
\item Ein \textit{reduzierter Automat} ist ein Automat, dessen nicht erreichbaren Zustände gestrichen wurden.
\item Zwei Zustände heißen \textit{$k$-äquivalent} ($\stackrel{k}{\sim}$) wenn $\forall |w| \leq k$ gilt:\\
$\bar{\delta}(q_1, w)\in F \Leftrightarrow \bar{\delta}(q_2, w) \in F$\\
Also: Nach $k$ Schritten ist man, egal mit welcher Eingabe, immer in einem Endzustand oder immer nicht darin.
\item Verfahren mit \textit{Überdeckungsmatrix} (zur Bestimmung eines Minimalautomaten):\\
Sei $r^k(q_1, q_2) = 0$ falls $q_1 \stackrel{k}{\sim} q_2$, sonst $1$\\
Dann können ab $k=0$ obere Dreiecksmatrizen $R^k:=r^k(q_i, q_j)$ angegeben werden, die ab einem $k$ immer gleich bleiben. Wo sich in der Dreiecksmatrix dann noch 0en befinden können äquivalente Zustände abgelesen werden, die zusammengefasst werden können zu einem Zustand.
\item Das \textit{\textbf{Pumping-Lemma}} weist nach, dass eine Sprache \emph{nicht} durch einen endlichen Automaten erkannt werden kann ($L \notin \mathcal{L}_3$)\\
Es besagt, dass sich, sofern $L \in \mathcal{L}_3$, für ein existierendes $n$ jedes Wort $z$ mit $|z|\geq n$ in $z=uvw$ zerlegen läßt, so dass
\begin{itemize}
 \item $|v| \geq 1$
 \item $|uv| \leq n$
 \item $uv^iw \in L \forall i \in \mathbb{N}$ (Wort läßt sich auf- und abpumpen)
\end{itemize}
denn in einem endlichen Automaten treten ab einer gewissen Wortlänge Zyklen auf (der Zustand wurde schon mal besucht).\\
Ist das Pumping-Lemma erfüllt muss die Sprache aber nicht zwingend Typ-3 sein! (Nur Ausschluss-Kriterium)
\item \textit{Leerheitsproblem}: Ist $L=\emptyset$? ($\rightarrow$ Wortproblem bis $|w|\leq n$)
\item \textit{Endlichkeitsproblem}: Ist $|L|<\infty$? ($\rightarrow$ Wortproblem $n \leq |w| < 2n$)
\item \textit{Äquivalenzproblem}: Ist $L_1=L_2$? 
\end{itemize}

\section{Kontextfreie Sprachen}
\begin{itemize}
\item \textit{Kontextfrei} sind Sprachen kontextfreier Grammatiken, also der Form $A \rightarrow \alpha$
\item Ein \textit{Ableitungs-} oder \textit{Syntaxbaum} ist eine Baumdarstellng der Grammatik mit der Wurzel $S$. Nonterminale sind dann Knoten, Terminale sind Blätter. Dabei sind unterschiedliche Ableitungen in der Regel möglich.
\item \textit{Eindeutig} ist die Grammatik, wenn genau ein Ableitungsbaum existiert.
\item \textit{Kettenregeln} sind Produktionen der Form $A \rightarrow B$, wo auf der rechten Seite nur ein Nonterminal steht. Diese können eliminiert werden, indem sie entsprechend mit der Produktion für das rechte Nonterminal (hier $B$) ersetzt werden (ggf. rekursiv).
\item Die \textit{\textbf{Chomsky-Normalform}} hat nur Produktionen der Art
\begin{itemize}
 \item $A \rightarrow BC$ (zwei Nonterminale)
 \item $A \rightarrow a$ (ein Terminal)
 \item $S \rightarrow \varepsilon$ und $S$ tritt auf keiner rechten Regelseite auf.
\end{itemize}
und stellt damit einen Binärbaum dar. Jede Typ-2-Grammatik hat eine äquivalente Grammatik dieser Form. Diese kann erzeugt werden indem man:
\begin{enumerate}
 \item Kettenregeln entfernt
 \item Für jedes rechte Terminalsymbol $a$ (auch Symbole wie z.B. ``$+$''!), das nicht alleine steht, ein Nonterminal $N_a \rightarrow a$ einführt
 \item Für jede rechte Seite, die mehr als zwei Nonterminale hat, müssen (ggf. rekursiv) weitere Regeln $C_i$ eingeführt werden (z.B. erstes stehen lassen, den Rest $C_1$ nennen usw.). 
\end{enumerate}
\item Der \textit{\textbf{CYK-Algorithmus}} löst das Wortproblem für eine Typ-2-Sprache. Dazu:
\begin{enumerate}
 \item Grammatik in CNF überführen
 \item Terminale horizontal auflisten
 \item darunter die entsprechenden Nonterminale
 \item Mit dem CYK-Algorithmus immer zwei Elemente ermitteln (hier nicht erklärt, ggf. z.B. bei YouTube nachsehen!) prüfen ob sie so auf einer rechten Regelseite der CNF auftauchen. Dabei ergibt sich schließlich eine umgedrehte Pyramide, ``Knoten'' sind Mengen erzeugender Produktionen (ggf. leere Menge). Ist die Spitze ein $S$ gilt $w \in L$, ansonsten $w \notin L$.
\end{enumerate}
\item Das \textit{\textbf{Pumping-Lemma für $\mathcal{L}_2$-Sprachen}} ist eine Erweiterung des ``kleinen'' Pumping-Lemmas: Für jedes Wort $z \in L \in \mathcal{L}_2 \exists n$ so dass alle $z$ mit der Mindestlänge $n$ sich in $z=uvwxy$ zerlegen lassen mit:
\begin{itemize}
 \item $vx \neq \varepsilon$
 \item $|vwx| \leq n$
 \item $uv^iwx^iy \in L$ (Wort läßt sich auf- und abpumpen)
\end{itemize}
\item \textit{$\mathcal{L}_2$-Eigenschaften}: Abeschlossen unter Vereinigung, Komplexprodukt, Sternoperator, jedoch nicht unter Durchschnitt und Komplement
\item \textit{\textbf{Kellerautomaten (PDA)}} erkennen Typ-2-Sprachen. Dabei wird zum einen ein Eingabewort zeichenweise gelesen. Zum andern steht dem Automaten ein Stack (= Keller) zur Speicherung von Werten zur Verfügung. Der Kellerautomat ist ein Tupel
$$ \mathcal{A} = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$$
wobei
\begin{itemize}
 \item $q, \Sigma, q_0, F$ definiert sind wie bei den anderen Automaten
 \item $\Gamma$ das Kelleralphabet (kann auch $\Sigma$ sein oder enthalten)
 \item $Z_0$ das Kellerstartsymbol
 \item $\delta: Q\times (\Sigma \cup \varepsilon) \times \Gamma \rightarrow \mathfrak{P}_f(Q\times \Gamma^*)$ die Transitionsfunktion darstellt.\\
 Beispiel: $\delta: q_0 a Z_0 \rightarrow q_1 bZ_0$ beschreibt ``Ist-Zustand $q_0$, $a$ gelesen, $Z_0$ vom Keller geholt $\rightarrow$ in Zustand $q_1$ gehen und $bZ_0$ auf Keller schreiben''
\end{itemize}
Kellerautomaten können entweder als Liste von $\delta$-Transitionen angegeben werden oder grafisch wie gewohnt dargestellt werden, wobei die Transition im obigen Beispiel mit $a, Z_0| bZ_0$ beschriftet würde.
\item Die \textit{Konfigurationsfolge} eine PDA wird angegeben durch ``(Zustand, Eingaberest, Keller)''.
\item \textit{Endkonfigurationen von Kellerautomaten} Es gibt drei mögliche Endkonfigurationen, die alle $\mathcal{L}_2$ erkennen können:
\begin{itemize}
 \item $L(\mathcal{A}, F)$: $(q, \varepsilon, \gamma)$ mit $q \in F$ (Endzustand)
 \item $L(\mathcal{A}, \varepsilon)$: $(q, \varepsilon, \varepsilon$ mit $q \in Q$ (leerer Keller)
 \item $L(\mathcal{A}, \varepsilon, F)$: $(q, \varepsilon, \varepsilon$ mit $q \in F$ (leerer Keller und Endzustand)
\end{itemize}
\item Sprachen von \textit{deterministischen Kellerautomaten (DPDA)} sind eine echte Teilmenge von $L(PDA)$ (Im Gegensatz zum DFA!). Sie terminieren per Endzustand ($q\in F$). Für sie gilt
$$|\delta(q, a, Z)|+|\delta(q,\varepsilon, Z)| \leq 1$$
Transitionen sind also eindeutig.\\
Es werden von ihnen die \textit{deterministischen kontextfreien Sprachen} erkannt.
\end{itemize}

\section{Turingmaschinen}
\begin{itemize}
\item Eine \textit{\textbf{Turingmaschine}} ist ein 7-Tupel
$$ \mathcal{A} = (Q, \Sigma, \Gamma, \delta, q_0, \bar{b}, F) $$
wobei das Arbeitsalphabet $\Gamma \supset \Sigma$ eine Übermenge des Eingabealphabetes ist und $\bar{b}$ das Leerzeichen/Blank darstellt.\\
Die Turingmaschine arbeitet auf einem unendlichen Lese- und Schreibband, welches zugleich der Eingabe dient.
\item Eine \textit{Einzelschrittrelation} ist dann: $\vdash_\mathcal{A} \subseteq \Gamma^*Q\Gamma\Gamma^* \times \Gamma^*Q\Gamma\Gamma^*$
\item Eine Transition $q_0 a A R q_1$ bedeutet: Anfangszustand $q_0$, gelesenes Zeichen $a$, geschriebenes Zeichen $A$, Positionsänderung des Lese/Schreibkopfes nach $R$ ($R$: rechts, $L$: links, $N$: keine Bewegung), Nachfolgezustand $q_1$. Eine Auflistung der Transitionen heißt \textit{Turingtafel}, die auch Kommentare enthalten kann.
\item Eine \textit{Konfigurationsfolge} zeichnet den Zustandsverlauf der Turingmaschine auf. Es wird dabei der Inhalt des Lese/Schreibbandes angegeben, der Zustand steht links neben der aktuellen Potition des Lese-/Schreibkopfes. Beispiel (vgl. oben): $\alpha q_0a\beta$.
\item $L(\Sigma, TM) =L(\Sigma, DTM) = \mathcal{L}_0$
\item \textit{Linear beschränkte Automaten (LBA)} sind Turingmaschinen mit einem endlichen Lese-/Schribband, das durch \textcent und \$ beschränkt wird. Es gilt $L(LBA)=\mathcal{L}_1$
\end{itemize}

\section*{\center{Teil II \\ Berechenbarkeitstheorie und Komplexitätstheorie}}

\section{Formalisierung des Berechenbarkeitsbegriffes}
\begin{itemize}
\item Eine Funktion $f=f_\mathcal{A}$ heißt \textit{Turing-Berechenbar} wenn eine Turingmaschine existiert die das Ergebnis von $f$ berechnet und auf das Band schreibt. Dabei muss gelten:
$$ f_\mathcal{A}(w) = v \Leftrightarrow q_0w\bar{b} \vdash_\mathcal{A}^* \alpha q v \bar{b}\beta$$
Das Ergebnis ist also von der Position des Lese/Schribkopfes bis zu einem $\bar{b}$ auf dem Band. Die DTM muss hier anhalten.
\item Die \textit{semi-charakteristische Funktion} einer Sprache L ist definiert als\\
$\chi_L'(w)=\varepsilon$ falls $w \in L$, $n.d.$ sonst.\\
$L\in \mathcal{L}_0 \Leftrightarrow \chi_L'$ ist Turing-berechenbar $\Leftrightarrow$ $L$ ist semi-entscheidbar (Denn wenn $w\notin L$ terminiert $\mathcal{A}$ nicht)
\item Die \textit{Church'sche These} nimmt an, dass eine Funktion genau dann berechenbar ist, wenn sie Turing-Berechenbar ist. Bewiesen sind bislang die Äquivalenzen von Turing-, While-, Goto-Berechenbarkeit, $\mu$-Rekursivität und $\lambda$-Definierbarkeit (und weitere).
\item \textit{\textbf{LOOP-Berechenbare Funktionen}} sind eine echte Teilmenge der Turing-berechenbaren Funktionen.
\item Ein \textit{LOOP-Programm} ist definiert durch
$$\mathcal{P}_{LOOP} = \{ \mathtt{in}(X_1, ..X_n);\mathtt{ istvar}(X_n+1,..,X_m);\alpha,\mathtt{out}X_1 | m\geq 1\}$$
wobei $X_i$ Variablen (Zahlen) sind und $\alpha \in \mathcal{A}$ eine oder mehrere (auch verschachtelte) der folgenden Anweisungen:
\begin{itemize}
 \item Wertzuweisung $\mathcal{W} : X_i:=X_j+1$ oder $X_i:=0$
 \item ``Verkettung'' $\alpha; \beta$
 \item $\mathtt{loop} V (\alpha);$ eine $V$-malige widerholung der Anweisung(en) $\alpha$
\end{itemize}
\item Die \textit{Semantik von LOOP} besteht aus
\begin{itemize}
 \item der \textit{Eingabeabbildung} $\mathtt{in}^{(n)}_m: (a_1, .., a_n) \rightarrow (a_i, .., a_n, 0, .., 0)$
 \item der \textit{Ausgabeabbildung} $\mathtt{out}^{(m)}_1: (a_1, .., a_m) \rightarrow a_1$
 \item sowie der \textit{Zustandstransformation} $[[\alpha]]^{(m)}:\mathbb{N}^m \rightarrow \mathbb{N}^m$, induktiv definiert durch
 \begin{itemize}
  \item $[[X_i:=X_j+1]]^{(m)}(a_1,..,a_m):=(a_1,..,a_{i-1},a_j+1,a_{i+1},..,a_m)$\\
  $[[X_i:=0]]^{(m)}(a_1,..,a_m):=(a_1,..,a_{i-1},0,a_{i+1},..,a_m)$
  \item $[[\alpha; \beta]]^{(m)}:=[[\beta]]^{(m)} \circ [[\alpha]]^{(m)}$
  \item $[[\mathtt{loop} X_i(\alpha)]]^{(m)}(a_1,..,a_m):=([[\alpha]]^{(m)})^{a_i}(a_1,..,a_m)$
 \end{itemize}
\end{itemize}
Damit kann die Semantik (Funktion) des LOOP-Programmes bestimmt werden.
\item \textit{primitiv-Rekursive Grundfunktionen}:
\begin{itemize}
 \item \textit{Nachfolgerfunktion} $S : a \rightarrow a+1$
 \item \textit{Nullkonstante} $0: () \rightarrow 0$
 \item \textit{Projektion} $pr^{(n)}_i : (a_1, .., a_n) \rightarrow a_i$
\end{itemize}
\item \textit{Primitiv rekursive Funktionen} werden durch
\begin{itemize}
 \item \textit{Komposition} ($f \circ f' = f(f')$)\\
und
 \item \textit{primitiver Rekursion}:\\
 $h(a_1, .., a_n, 0) := f(a_1, .., a_n)$\\
 $h(a_1, .., a_n, a+1) := g(a_1, .., a_n, a, h(a_a, .., a_n, a))$\\
\end{itemize}
erzeugt. $f$ ist genau dann primitiv rekursiv, wenn $f$ LOOP-berechenbar ist.
\item \textit{\textbf{WHILE-Programme}} unterscheiden sich von LOOP-Programmen durch
\begin{itemize}
 \item zwei weitere \textit{Wertzuweisungen}:\\
 $\mathcal{W}:=\{X_i:=X_j+1, X_i:=X_j-1, X_i:=X_j, X_i:=0\}$ sowie
 \item die Schleife $\mathtt{while} X_i \neq 0 \mathtt{do} \alpha \mathtt{od} \in \mathcal{A}$
\end{itemize}
für die Semantik gilt gleiches wie für das LOOP-Programm sowie\\
$[[\mathtt{while} X_i \neq 0 \mathtt{do} \alpha \mathtt{od}]]^{(m)}(a_1,..,a_m) := ([[\alpha]]^{(m)})^k(a_1, .., a_m)$\\
für $k$ minimal, so dass der Term $=0$ ist (ggf. nicht definiert)
\item Eine \textit{\textbf{Minimalisierung}} einer Funktion $f: \mathbb{N}^{n+1}\rightarrow\mathbb{N}$ ist definiert als\\
$\mu(f)(a_1, .., a_n):=\begin{cases}
                        b &\text{ falls }f(a_1,..,a_n,b)=0\text{ mit $b$ minimal } \\
                        n.d. &\text{ sonst}
                       \end{cases}$
\item \textit{$\mu$-rekursive Funktionen} sind durch primitive Grundfunktionen in endlichen Schritten durch Komposition, primitive Rekursion oder Minimalisierung erzeugbar. Sie sind mit höchstens einer While-Schleife berechenbar.
\end{itemize}

\section{Entscheidbarkeit, Aufzählbarkeit, Berechenbarkeit}
\begin{itemize}
\item Die \textit{charakteristische Funktion} ist gegeben durch
$$\chi_L(w)=
\begin{cases}
\varepsilon & \text{ falls } w \in L\\
a_1 & \text{ sonst}
\end{cases}$$
Wenn diese Turing-Berechenbar ist heißt $L$ \textit{entscheidbar}\\
 $\Leftrightarrow$ $L$ und $\Sigma^*\setminus L$ rek. aufzählbar  $\Leftrightarrow$ $\Sigma^*\setminus L$ entscheidbar
\item \textit{$L$ rekursiv aufzählbar} $\Leftrightarrow$ $L=\emptyset \vee \exists f: Bild(f)=\{f(w)|w\in \Sigma^*\}=L$ wobei $f$ total (``beidseitig eindeutig'') und berechenbar sein muss \\
$\Leftrightarrow$ \textit{Semi-entscheidbar} $\Leftrightarrow$ $\chi_L'$ berechenbar $\Leftrightarrow$ $L\in \mathcal{L}_0$
\item $\mathcal{L}_1(\Sigma) \subsetneqq \{L\subseteq \Sigma^* | L \text{ entscheidbar}\} \subsetneqq \mathcal{L}_0(\Sigma)$
\item $L_1$ ist auf $L_2$ \textit{reduzierbar} $\Leftrightarrow$ $L_1 \leq L_2$ genau dann, wenn\\
eine totale und berechenbare Funktion $f$ existiert mit $w\in L_1 \Leftrightarrow f(w) \in L_2 \forall w\in \Sigma^*$\\
Ist dann $L_2$ (semi-)entscheidbar, so ist auch $L_1$ (semi-)entscheidbar.
\item Der \textit{Satz von Rice} besagt, dass eine Eigenschaft entweder für alle rekursiv aufzählbaren Sprachen entscheidbar, oder für alle nicht-entscheidbar ist (= nichttriviale Eigenschaft $P$).
\item Die \textit{Universelle Sprache}, das \textit{Halteproblem} und das \textit{Postsche Korrespondenzproblem} sind nicht entscheidbare Probleme.
\end{itemize}


% -----------------------------------------------------------------------------------------
%	Literaturverzeichnis
% -----------------------------------------------------------------------------------------
%\include{Literatur}
\end{document}