%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[10pt,twoside,german]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=20mm,bmargin=20mm,lmargin=20mm,rmargin=20mm,headheight=5mm,headsep=5mm,footskip=5mm}
\pagestyle{headings}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{varioref}
\usepackage{amsmath}
\usepackage{makeidx}
\makeindex
\usepackage{amssymb}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{gastex}
%\renewcommand{\thesubsubsection}{\alph{subsubsection})}
\usepackage[linktocpage,pdfpagelabels,colorlinks,hyperindex]{hyperref}
\usepackage[T1]{fontenc}
\usepackage{ae,aecompl}

\usepackage{babel}
\makeatother
\begin{document}

\title{Formelsammlung\\
theoretische Informatik I}


\author{<Marco.Moeller@macrolab.de>}


\date{Stand: 27.05.2005 - Version: 1.0.3\\
\noun{Erhältlich unter \url{http://privat.macrolab.de}}}

\maketitle
Diese Formelsammlung basiert auf der Vorlesung {}``Theoretische Informatik
1'' von Prof. Dr. Heinrich Werner an der Universität Kassel im Sommersemester
2004.

Die folgende Formelsammlung steht zum kostenlosen Download zur Verfügung.
Das Urheberrecht und sonstige Rechte an dem Text verbleiben beim Verfasser,
der keine Gewähr für die Richtigkeit und Vollständigkeit der Inhalte
übernehmen kann.

\tableofcontents{}

Die hinter den Überschriften angegebenen Nummern beziehen sich auf
die Seitenzahlen des Buches {}``Theoretische Informatik - kurzgefasst''
von Uwe Schöning (4. Auflage).

Grundlagen der Logik und der Mengenlehre sind in meiner {}``Formelsammlung
Mathe I/II für Informatiker'' nachzuschlagen.


\section{Mathematische Grundlagen\index{Häufungspunkt} \textsf{\textmd{\small 185}}}


\subsection{Alphabet\index{Alphapet} und Symbole\index{Symbole} \textsf{\textmd{\small 185}}}


\subsubsection{Definition}

Als \emph{Alphabet\index{Alphabet}} bezeichnen wir eine endliche,
nicht-leere Menge $\Sigma$. Elemente aus $w\in\Sigma$ heißen \emph{Zeichen\index{Zeichen}}
oder \emph{Symbole\index{Symbole}}.

\begin{itemize}
\item $\Sigma^{*}=$ Menge aller Wörter, die sich aus $\Sigma$ bilden lassen
incl. leerem Wort $\varepsilon$
\item $\Sigma^{+}=$ Menge aller Wörter, die sich aus $\Sigma$ bilden lassen
ohne $\varepsilon$
\item $\left|\Sigma\right|=$ Anzahl der verschiedenen Symbole in $\Sigma$
(Mächtigkeit\index{Mächtigkeit} der Menge $\Sigma$)
\end{itemize}

\subsubsection{Konkatenation\index{Konkatenation}}

Sei $\circ$ ein Symbol für die Konkatenation, dann ist die algebraische
Struktur $\left(\Sigma^{*},\circ\right)$ eine \emph{Halbgruppe\index{Halbgruppe}
mit neutralem Element}, ein so genanntes \emph{Monoid\index{Monoid}.}

\begin{itemize}
\item Abgeschlossenheit\index{Abgeschlossenheit} \\
$x\in\Sigma^{*}\wedge y\in\Sigma^{*}\Rightarrow x\circ y=xy\in\Sigma^{*}$
\item Assoziativität\index{Assoziativität} \\
$\left(x\circ y\right)\circ z=x\circ\left(y\circ z\right)=xyz$
\item neutrales~Element\index{neutrales Element} \\
$\varepsilon\circ x=x\circ\varepsilon=x$
\end{itemize}

\subsubsection{Wort\index{Wort}}

Ein Wort (mathm. ein Tupel\index{Tupel}) entsteht durch hintereinanderschreiben
(Konkatenation\index{Konkatenation}) von Symbolen aus $\Sigma$.
$\varepsilon$ steht für das leere Wort (eine art neutrales Element).

\begin{itemize}
\item $w^{n}=\underbrace{ww\ldots w}_{n-mal}\quad\left(n\in\mathbb{N}_{0}\right)$
\item $w^{0}=\varepsilon$
\end{itemize}

\subsubsection{Länge eines Wortes}

Für ein Wort $w$ bezeichnet $\left|w\right|$ seine Länge, d.h. die
Anzahl der in ihm enthaltenen Zeichen.

\begin{itemize}
\item $\left|\varepsilon\right|=0$
\item $\left|uv\right|=\left|u\right|+\left|v\right|$
\item $\left|w^{n}\right|=n\left|w\right|$
\end{itemize}
Diese Regeln haben eine gewisse Ähnlichkeit mit derer der Logarithmus
Funktion.


\subsection{Sprachen\index{Sprachen} \textsf{\textmd{\small 186}}}


\subsubsection{Definition}

Eine Teilmenge von $\Sigma^{*}$ wird als \emph{Sprache\index{Sprache}}
Bezeichnet. ($A\in\Sigma^{*}$)


\subsubsection{Rechenregeln}

Da es sich bei Sprachen um Mengen handelt, gelten für sie (fast) alle
Operatoren und Regeln der Mengen.

Eine Sprache lässt sich aus anderen Sprachen zusammensetzen (ähnlich
Konkatenation). Dies bedeutet, das der ein Wort aus der neuen Sprache,
aus den Teilen der anderen Sprachen zusammengesetzt wird. 

\begin{itemize}
\item $A^{0}=\left\{ \varepsilon\right\} $
\item $A^{1}=A$
\item $A^{n+1}=AA^{n}$
\item $A^{i}A^{j}=A^{i+j}$
\item $\left(A^{i}\right)^{j}=A^{ij}$
\item $A^{*}=\cup_{n\geq0}A^{n}$
\item $A^{+}=\cup_{n\geq1}A^{n}$
\item Menge aller Sprachen (Potenzmenge über $\Sigma^{*}$)\\
$\mathcal{P}\left(\Sigma^{*}\right)=2^{\Sigma^{*}}=\left\{ A|A\subseteq\Sigma^{*}\right\} $
\end{itemize}

\subsubsection{Relationen\index{Relationen} auf Sprachen \textsf{\textmd{\small 187}}}

Eine zweistellige Relation zwischen $a$ und $b$ $\left(aRb\right)$
mit $R\subset\Sigma^{*}\times\Sigma^{*}$ ist wahr, wenn $\left(a,b\right)\in R$
und falsch, wenn $\left(a,b\right)\notin R$.

\begin{itemize}
\item Hintereinandschreiben von Relationen:\\
$RS=\left\{ \left(x,y\right)|\exists_{\Sigma}^{z}:xRz\wedge zSz\right\} $
\item $R^{0}=\left\{ x,x|x\in\Sigma^{*}\right\} =$ Identität
\item $R^{n+1}=RR^{n}$
\item $R=\cup_{n\geq0}R^{n}$
\item $R^{+}=\cup_{n\geq1}R^{n}$
\item $R$ heißt \emph{reflexiv\index{reflexiv}} wenn:\\
$\forall_{\Sigma}^{x}:xRx$
\item $R$ heißt \emph{transitiv\index{transitiv}} wenn:\\
$xRy\wedge yRz\Rightarrow xRz$
\item $R^{*}$ ist die kleinste reflexive und transitive Relation, die $R$
umfasst (die reflexive und transitive \emph{Hülle\index{Hülle}} von
$R$)

\begin{itemize}
\item kleiner als hoch $*$ geht es nicht, da $R$ sonst nicht transitiv
wäre (es muss jede Hintereinanderausführung von zwei Realtionen enthalten)
\item $R^{0}$ muss enthalten sein, damit auch die Reflexivität gilt.
\end{itemize}
\item $R$ heißt \emph{symmetrisch\index{symmetrisch}} wenn:\\
$xRy\Leftrightarrow yRx$
\item $R$ heißt \emph{Äquivalenzrelation\index{Äquivalenzrelation}} wenn:\\
$R$ ist reflexiv und transitiv und symmetrisch
\end{itemize}

\subsubsection{\label{sub:=C4quivalenzklassen-&-Index}Äquivalenzklassen\index{Äquivalenzklassen}
\& Index\index{Index}}

Jedem Element aus dem Grundbereich (hier: $\Sigma^{*}$) kann die
Menge der Elemente zugeordnet werden, die zu $x$ äquivalent sind.
Diese werden mit $\left[x\right]_{R}$ bezeichnet.\[
\left[x\right]_{R}=\left\{ y|yRx\right\} =\left\{ y|xRy\right\} \]


Wenn $R$ aus dem Kontext hervorgeht, schreiben wir auch einfach $\left[x\right]$.
Diese Mengen heißen \emph{Äquivalenzklassen}.

Die Grundmenge $\Sigma^{*}$ lässt sich in Äquivalenzklassen zerlegen:\[
\Sigma^{*}=\dot{\cup}_{k=0}^{n}\left[x_{k}\right]\quad\mathrm{Index}\left(R\right)=n\]


Mit $\mathrm{Index}\left(R\right)$ bezeichnen wir die Anzahl der
verschiedenen Äquivalenzklassen, die $R$ hat. 

\begin{itemize}
\item $\mathrm{Index}\left(R\right)$ ist die maximale Anzahl von Elementen
$x_{1},x_{2},\ldots,x_{n},\ldots$ mit $\neg\left(x_{i}Rx_{j}\right)\ \left(i\neq j\right)$
\item Falls $\mathrm{Index}\left(R\right)<\infty$ gilt, so sagen wir: $R$
hat einen endlichen Index
\end{itemize}

\subsection{Komplexitätsfunktionen\index{Komplexitätsfunktionen} (O-Notation\index{O-Notation})
\textsf{\textmd{\small 189 / AlgoDS Skript Seite 13}}}

Diese dienen zum abschätzen des (asymptotischen\index{asymptotischen})
Verhaltens einer Funktion. Eigentlich werden hiermit Mengen von Funktionen
angegeben, aber es hat sich eingebürgert trotzdem $=$ zu schreiben
(wenn das $O$ rechts steht). Z.B: \[
5n^{2}+1000n+10^{100}=O\left(n^{2}\right)\]



\subsubsection{Obere Schranke\index{Obere Schranke}\index{Schranke}}

\[
O\left(g\left(n\right)\right)=\left\{ f\left(n\right)|\exists c>0\exists n_{0}>0\forall n>n_{0}:0\leq f\left(n\right)\leq cg\left(n\right)\right\} \]



\subsubsection{Untere Schranke\index{Untere Schranke}\index{Schranke}}

\[
\Omega\left(g\left(n\right)\right)=\left\{ f\left(n\right)|\exists c>0\exists n_{0}>0\forall n>n_{0}:0\leq cg\left(n\right)\leq f\left(n\right)\right\} \]



\subsubsection{Genaue Schranke\index{Genaue Schranke}\index{Schranke}}

\[
\theta\left(g\left(n\right)\right)=O\left(g\left(n\right)\right)\cap\Omega\left(g\left(n\right)\right)\]


Wenn die Untere und Obere Schranke übereinstimmen, kann man dies als
Genaue Schranke angeben.


\subsubsection{Ergänzung\index{Ergänzung}}

\[
o\left(g\left(n\right)\right)=\left\{ f\left(n\right)|\forall c>0\exists n_{0}>0\forall n>n_{0}:0\leq f\left(n\right)<cg\left(n\right)\right\} \]


Gibt eine Funktion an, die \emph{auf jeden Fall} größer ist als die
Eingabefunktion. Sie ist also von einem Höheren Grad als $O\left(g\left(n\right)\right)$.


\section{Allgemeines zu Sprachen}


\subsection{Grammatiken\index{Grammatik} \textsf{\textmd{\small 13}}}


\subsubsection{Definition \textsf{\textmd{\small 13}}}

Eine \emph{Grammatik\index{Grammatik}} ist ein $4$-Tupel $G=\left(V,\Sigma,P,S\right)$,
das folgende Bedingungen erfüllt.

\begin{itemize}
\item $V$ ist eine endliche Menge, die Menge der \emph{Variablen}\index{Variablen}
\item $\Sigma$ ist eine endliche Menge, das \emph{Terminalalphabet\index{Terminalalphabet}}
\item $V\cap\Sigma=\emptyset$
\item $S\in V$ \emph{Startsymbol}\index{Startsymbol}
\item $P$ ist die endliche Menge der \emph{Produktionen}\index{Produktionen}
oder \emph{Regeln\index{Regeln}}. Formal: $P\subset\left(V\cup\Sigma\right)^{+}\times\left(V\cup\Sigma\right)^{*}$
ist endlich.
\item $\forall_{P}^{l\rightarrow r}:\left|l\right|_{V}\geq1$
\end{itemize}
Seien $u,v\in\left(V\cup\Sigma\right)^{*}$. Wir definieren die Relation
$u\Rightarrow_{G}v$ ($u$ geht unter $G$ unmittelbar über in $v$),
falls

\begin{itemize}
\item $\exists_{\left(V\cup\Sigma\right)^{*}}^{x,y}:u=xyz\wedge v=xy'z$
\item $\left(y\rightarrow y'\right)\in P$
\end{itemize}
Wenn klar, ist welche Grammatik gemeint ist, so schreiben wir einfach
$u\Rightarrow v$ 

Beispiel für Schreibweise (mit erweiterter Schreibweise / Backus-Naur-Form\index{Backus-Naur-Form}):\begin{eqnarray*}
G & := & \left(V,\Sigma,P,S\right)\\
V & := & \left\{ S,N,Z\right\} \\
\Sigma & := & \left\{ 0,1,2,3,4,5,6,7,8,9,-,\epsilon\right\} \\
P & := & \{ S\rightarrow ZN;\\
 &  & Z\rightarrow\epsilon|-;\\
 &  & N\rightarrow1|2|3|4|5|6|7|8|9|NN\}\end{eqnarray*}



\subsubsection{Ableitungen \textsf{\textmd{\small 14}}}

Eine Folge von Wörtern $\left(w_{0},w_{1},\ldots,w_{n}\right)$ mit
$w_{0}=S,w_{n}\in\Sigma^{*}$ und $w_{0}\Rightarrow w_{1}\Rightarrow\ldots\Rightarrow w_{n}$
heißt \emph{Ableitung}\index{Ableitung} von $w_{n}$.

Ein Wort $w\in\left(V\cup\Sigma\right)^{*}$, das also noch Variablen
enthält (wie es typischerweise im Verlauf einer Ableitung vorkommt)
heißt auch \emph{Satzform}\index{Satzform}.

Ein Wort $w\in\left(\Sigma\right)^{*}$, das ausschließlich \emph{Terminale}
enthält heißt auch \emph{Terminalwort}\index{Terminalwort}.

\begin{itemize}
\item Ableiten ist ein \emph{nichtdeterministischer\index{nichtdeterministisch}}
Prozess (es steht im allgemeinen nicht fest, auf was etwas abgeleitet
werden muss).
\end{itemize}

\subsubsection{Sprache\index{Sprache} einer Grammatik \textsf{\textmd{\small 14}}}

Die von $G=\left(V,\Sigma,P,S\right)$ dargestellte (erzeugte, definierte)
\emph{Sprache} ist:\[
L\left(G\right)=\left\{ w\in\Sigma^{*}|S\Rightarrow_{G}^{*}w\right\} \]


Dies bedeutet, das man mit einer beliebigen Kombination von Ableitungen,
irgendwie zu dem Wort $w$ kommen können muss.


\subsubsection{Darstellung von Ableitungen \textsf{\textmd{\small 16}}}

Graphisch kann man sich das Ableiten wie ein endlich verzweigter,
aber im allgemeinen unendlich großen Baum vorstellen. Mit $S$ als
Wurzel, und Wörtern der Sprache als Blätter.


\subsection{Chomsky-Hierarchie\index{Chomsky-Hierarchie} \textsf{\textmd{\small 17}}}

Die Menge aller Grammatiken (und der dazugehörigen Sprachen) lässt
sich in folgende Kategorien unterteilen. Die Sprachen werden abgekürzt
mit $\mathcal{L}_{n}$. Dabei gilt:\[
\mathcal{P}\left(\Sigma^{*}\right)\supset\mathcal{L}_{0}\supset\mathcal{L}_{1}\supset\mathcal{L}_{2}\supset\mathcal{L}_{3}\]



\subsubsection{Typ 0 oder rekursiv aufzählbar\index{rekursiv aufzählbar}}

Jede Grammatik ist automatisch vom Typ 0. Es gibt hier also keine
Einschränkungen. (Außer das es eine korrekte Grammatik sein muss)

\begin{itemize}
\item sind nicht \emph{entscheidbar}\index{entscheidbar} (ob ein Wort in
der Sprach liegt oder nicht, siehe Wortproblem)
\end{itemize}

\subsubsection{Typ 1 oder kontextsensitiv\index{kontextsensitiv}}

wenn: $\forall_{P}^{\left(w_{1}\rightarrow w_{2}\right)}:\left|w_{1}\right|\leq\left|w_{2}\right|$

\begin{itemize}
\item Typ 1 Grammatiken sind monoton, das heißt, das die Satzformen nie
kürzer werden können.
\item $\varepsilon\notin\mathcal{L}_{1}$ gilt nach der aktuellen Definition.
Wenn dies doch erwünscht, dann muss folgende Sonderregel erlaubt werden:

\begin{itemize}
\item $\left(S\rightarrow\varepsilon\right)\in P$ wenn gilt: $\forall_{P}^{\left(l\rightarrow r\right)}:r\neq S$
\item falls $S$ doch auf rechten Seiten vorkommt, einfach ein neues $S'$
definieren, als neue Startvariable benutzen, und folgende Regeln aufnehmen:
$\left(S'\rightarrow S\right)$;$\left(S'\rightarrow\varepsilon\right)$
\end{itemize}
\end{itemize}

\subsubsection{Typ 2 oder kontextfrei\index{kontextfrei}}

wenn: $\forall_{P}^{\left(w_{1}\rightarrow w_{2}\right)}:w_{1}\in V$

\begin{itemize}
\item \label{ite:Entfernen epsilon Regeln(Typ2)}Wenn Regeln der Form $A\rightarrow\varepsilon$
existieren kann man diese aus Grammatik entfernen um sie kontextfrei
zu machen, indem die Regeln entsprechend angepasst werden. (\textsf{\small Buch
S. 19}):

\begin{itemize}
\item Zerlegen der Menge der Variablen $V$ in $V_{1}$ und $V_{2}$, so
dass für alle $A\in V_{1}$ (und nur für diese) gilt $A\Rightarrow^{*}\varepsilon$.
Dabei wie folgt vorgehen:

\begin{itemize}
\item Wenn $\left(A\rightarrow\varepsilon\right)\in P$, so ist $A\in V_{1}$
\item Weitere Variablen findet man sukzessive dadurch, dass es in $P$ eine
Regel $B\rightarrow A_{1}\ldots A_{k},k\geq1$, gibt mit $A_{i}\in V_{1}\left(i=1,\ldots,k\right)$.
Nach endlich vielen Schritten hat man $V_{1}$gefunden
\item Entfernen der Form $\left(A\rightarrow\varepsilon\right)\in P$ und
fügen für jede Regel der Form $B\rightarrow xAy$ mit $B\in V,A\in V_{1},xy\in\left(V\cup\Sigma\right)^{+}$
eine weitere Regel der Form $B\rightarrow xy$ zu $P$ hinzu. Dies
muss entsprechend oft durchgeführt werden.
\item Ergebnis ist eine von $\varepsilon$-Regeln befreite Grammatik $G'$
\end{itemize}
\end{itemize}
\item Wenn ein Wort $x$ auf verschieden Arten erzeugt werden kann, ist
die Grammatik \emph{mehrdeutig\index{mehrdeutig}}.
\item Eine kontextfreie Sprache $A$ heißt \emph{inhärent mehrdeutig\index{inhärent mehrdeutig}},
wenn jede Grammatik mit $L\left(G\right)=A$ mehrdeutig ist.
\end{itemize}

\subsubsection{Typ 3 oder regulär\index{regulär}}

wenn: $\forall_{P}^{\left(w_{1}\rightarrow w_{2}\right)}:w_{1}\in V\wedge w_{2}\in\left(\Sigma\cup\Sigma V\right)$

\begin{itemize}
\item Es gibt keine reguläre Sprache, die \emph{inhärent Mehrdeutig\index{inhärent Mehrdeutig}}
ist
\end{itemize}

\subsection{Wortproblem\index{Wortproblem} \textsf{\textmd{\small 21}}}

Das \emph{Wortproblem\index{Wortproblem}} für Typ 1-Sprachen (und
damit auch für Typ 2 ,3) ist entscheidbar. Es gibt einen Algorithmus,
der bei Eingabe einer kontextsensitiven Grammatik $G=\left(V,\Sigma,P,S\right)$
und eines Wortes $x\in\Sigma^{*}$ in \emph{endlicher} Zeit entscheidet,
ob $x\in L\left(G\right)$ oder $x\notin L\left(G\right)$.


\subsubsection{Algorithmus zum Lösen des Wortproblems bei Typ 1 - Grammatiken}

Vorweg zur Notation: Bei $T_{n}^{m}$ handelt es sich um die Menge
aller Satzformen, die maximal $m$ Symbole haben, und in maximal $n$
Ableitungsschritten aus dem Startsymbol $S$ ableitbar sind.

Um das Wortproblem für ein Wort $w\in\Sigma^{*}$ mit der Länge $\left|w\right|=m$
zu lösen, muss geprüft werden, ob es in der Menge $T_{n}^{m}$ (mit
genügend großem $n$) enthalten ist. $T_{n}^{m}$ lässt sich wie folgt
konstruieren: 

\begin{itemize}
\item Die nullte Ableitung ist hier als identische Ableitung definiert.
D. h., dass nur $S$ selber als Element der Menge $T_{0}^{m}$ infrage
kommt: $T_{0}^{m}=\left\{ S\right\} $
\item Die folgenden Schritte können nun alle nach dem gleichen (iterativen)
Schema ablaufen, und zwar solange, bis keine Änderung an $T_{n}^{m}$
mehr auftritt ($T_{n}^{m}=T_{n+1}^{m}$).

\begin{itemize}
\item Nehme die letzte Menge ($T_{n-1}^{m}$), und ziehe die vorletzten
Menge ($T_{n-2}^{m}$) und alle Terminalwörter ab
\item bilde alle Ableitungen dieser Menge.
\item Dies Vereinigt mit der letzten Menge ($T_{n-1}^{m}$) ergibt die neue
Menge ($T_{n}^{m}$)
\item das ganze Formal:\[
T_{n+1}^{m}=T_{n}^{m}\cup\mathrm{Abl}_{m}\left(T_{n}^{m}\backslash\left(T_{n-1}^{m}\cup\Sigma^{*}\right)\right)\]
 Unter $\mathrm{Abl}_{m}\left(X\right)$ versteht man die Menge aller
Ableitungen von Elementen aus $X$ die maximal $m$ Symbole besitzen.
Formal%
\footnote{Diese Definitionen entsprechen nicht ganz den Angaben in der Literatur,
sind aber leichter handhabbar, da die Ableitung nur für eine viel
kleiner Menge durchgeführt werden muss.%
}:\[
\mathrm{Abl}_{m}\left(X\right)=\left\{ w\in\left(V\cup\Sigma\right)^{*}|\left|w\right|\leq m\wedge\exists_{X}^{w'}:w'\Rightarrow w\right\} \]

\end{itemize}
\item Das Wortproblem für $w$ ist nun gelöst: $w\in T_{n}^{m}\Leftrightarrow w\in L\left(G\right)$
\end{itemize}
Dieser Algorithmus hat eine Laufzeit von $O\left(c^{n}\right)$


\subsection{Syntaxbäume\index{Syntaxbäume} \textsf{\textmd{\small 23}}}

Einer Ableitung eines Wortes $x$ in einer Typ 2 (oder 3) Grammatik
$G$ kann man einen \emph{Syntaxbaum\index{Syntaxbaum}} oder \emph{Ableitungsbaum\index{Ableitungsbaum}}
zuordnen. Sei $x\in L\left(G\right)$ und sei $S\Rightarrow x_{0}\Rightarrow x_{1}\Rightarrow\ldots\Rightarrow x_{n}=x$
eine Ableitung eines Wortes $x$. Um den Baum zu erstellen gehe wie
folgt vor:

\begin{itemize}
\item Beschrifte die Wurzel des Syntaxbaumes mit der Startvariable $S$
\item Für $i=1,\ldots,n$ gehe man wie folgt vor:

\begin{itemize}
\item Falls im $i$-ten Ableitungsschritt (also beim Übergang von $x_{i-1}$
nach $x_{i}$) gerade die Variable $A$ durch ein Wort $z$ ersetzt
wird (wegen $\left(A\rightarrow Z\right)\in P$):

\begin{itemize}
\item Sehe im Syntaxbaum $\left|z\right|$ viele Söhne von $A$ vor
\item beschrifte diese mit den einzelnen Zeichen von $z$
\end{itemize}
\end{itemize}
\end{itemize}
Auf diese Weise erhält man eine Baum mit den Symbolen aus $x$ an
den Blättern.

\begin{itemize}
\item Verschiedene Ableitungen können den selben Syntaxbaum besitzen
\item \emph{Linksableitung}\index{Linksableitung}: Immer am weitesten Links
stehende Variable zuerst ableiten
\item \emph{Rechtsableitung\index{Rechtsableitung}:} Immer am weitesten
Rechts stehende Variable zuerst ableiten
\item Für ein und das selbe Wort kann es verschiedene Syntaxbäume geben.
Die Grammatik ist dann \emph{mehrdeutig\index{mehrdeutig}}.
\item Eine kontextfreie Sprache $A$ heißt \emph{inhärent mehrdeutig\index{inhärent mehrdeutig}},
wenn jede Grammatik mit $L\left(G\right)=A$ mehrdeutig ist.
\end{itemize}

\subsection{Backus-Naur-Form\index{Backus-Naur-Form} \textsf{\textmd{\small 25}}}

Hierbei handelt es sich um einen Formalismus zum kompakten niederschreiben
von Typ 2-Grammatiken. Kurz \emph{BNF}\index{BNF}. Folgende neue
Schreibweisen für Produktionen werden eingeführt:

\begin{itemize}
\item Metaregel\index{Metaregel} ({}``$|$'' = Metasymbol\index{Metasymbol})\\
$A\rightarrow\beta_{1};\; A\rightarrow\beta_{2};\;\ldots;\; A\rightarrow\beta_{n}=$\\
$A\rightarrow\beta_{1}|\beta_{2}|\ldots|\beta_{n}$
\end{itemize}
Folgende Schreibweisen gehören zusätzlich zur \emph{erweiterten BNF\index{erweiterte BNF}}
(\emph{EBNF}\index{EBNF}):

\begin{itemize}
\item Eventueller Teil:\\
$A\rightarrow\alpha\left[\beta\right]\gamma=$\\
$A\rightarrow\alpha\beta\gamma;\; A\rightarrow\alpha\gamma$
\item Beliebig häufige Wiederholung:\\
$A\rightarrow\alpha\left\{ \beta\right\} \gamma=$\\
$A\rightarrow\alpha\gamma;\; A\rightarrow\alpha B\gamma;\; B\rightarrow\beta;\; B\rightarrow\beta B$
\end{itemize}
Durch die \emph{(E)BNF} werden exakt die Typ 2 - Sprachen dargestellt.


\section{Reguläre Sprachen\index{Reguläre Sprachen} (Typ 3) \textsf{\textmd{\small 27}}}


\subsection{Deterministische (endliche) Automaten\index{Deterministische Automaten}\index{endliche Automaten}}


\subsubsection{Definition \textsf{\textmd{\small 27}}}

Ein deterministischer (endlicher) Automat, kurz DFA\index{DFA} (deterministic
finite automation), wird auf ein Eingabewort\index{Eingabewort} angesetzt
und erkennt, bzw. akzeptiert dieses Wort, oder auch nicht. Ein DFA
M wird spezifiziert durch ein $5$-Tupel\[
M=\left(Z,\Sigma,\delta,z_{0},E\right)\]


\begin{itemize}
\item $Z$ Menge der \emph{Zustände}\index{Zustände}
\item $\Sigma$ \emph{Eingabealphabet}\index{Eingabealphabet}
\item $Z\cap\Sigma=\emptyset$ 
\item $z_{0}\in Z$ \emph{Startzustand}
\item $E\subseteq Z$ Menge der \emph{Endzustände\index{Endzustände}}
\item $\delta:Z\times\Sigma\rightarrow Z$ \\
\emph{(Zustands-)Überführungsfunktion}\index{Zustandsüberführungsfunktion}\index{Überführungsfunktion}
\end{itemize}

\subsubsection{\label{sub:Zustandsgraph DFA}Zustandsgraph\index{Zustandsgraph}
\textsf{\textmd{\small 27}}}

Darstellen lässt sich ein Automat durch einen \emph{Zustandsgraphen},
(gerichtet und beschrifteter Graph\index{Graph}) der sich wie folgt
konstruieren lässt:

\begin{itemize}
\item Zeichne für jeden Zustand $z_{n}$ aus der Menge $z_{n}\in Z$ einen
Kreis, und beschrifte ihn mit $z_{n}$
\item Umkreise alle Kreise (doppelt Umkreisen) die einen $z_{n}\in E$ Endzustand
enthalten
\item Markiere den Startzustand $z_{0}$ mit einem nicht beschrifteten Pfeil
der auf ihn Zeigt (entspringt aus dem Nichts)
\item Für jede Überführungsvorschrift: $\delta\left(z_{n},a\right)=z_{m}$

\begin{itemize}
\item Zeichen einen Pfeil von $z_{n}$ nach $z_{m}$ (wenn noch nicht vorhanden)
\item beschrifte ihn (zusätzlich) mit $a$
\end{itemize}
\end{itemize}

\subsubsection{Sprache eines DFA \textsf{\textmd{\small 29}}}

Zu einem gegebenen DFA $M=\left(Z,\Sigma,\delta,z_{0},E\right)$ definieren
wir eine Funktion $\hat{\delta}:Z\times\Sigma^{*}\rightarrow Z$ durch
eine induktive Definition wie folgt (erweitert die Definition von
$\sigma$ von Einzelzeichen zu ganzen Wörtern):

Mit $z\in Z,\; x\in\Sigma^{*},\; a\in\Sigma$\begin{eqnarray*}
\hat{\delta}\left(z,\varepsilon\right) & = & z\\
\hat{\delta}\left(z,ax\right) & = & \hat{\delta}\left(\delta\left(z,a\right),x\right)\end{eqnarray*}


Die Menge der akzeptierten Wörter bildet die durch den Automaten dargestellte
oder definierte Sprache: \[
T\left(M\right)=\left\{ x\in\Sigma^{*}|\hat{\delta}\left(z_{0},x\right)\in E\right\} \]


\begin{itemize}
\item eine Sprache $L$ wird durch einen endlichen Automaten erkannt $\Leftrightarrow$
die Sprache ist regulär ($L\in\mathcal{L}_{3}$)
\item das lösen des Wortproblems ist mit Hilfe eines DFA in $O\left(n\right)$
möglich.
\end{itemize}

\subsubsection{Grammatik zu einem gegebenen DFA \textsf{\textmd{\small 30}}}

Aus einem DFA $M=\left(Z,\Sigma,\delta,z_{0},E\right)$ lässt sich
wie folgt eine (reguläre / Typ 3) Grammatik $G=\left(V,\Sigma,P,S\right)$
konstruieren:

\begin{itemize}
\item $\Sigma$ die Mengen der Terminale sind gleich
\item $Z=V$ die Menge der Variablen entspricht der Menge der Zustände
\item $S=z_{0}$ die Startvariable ist der Startzustand des Automaten
\item Für jede Überführungsvorschrift: $\delta\left(z_{n},a\right)=z_{m}$ 

\begin{itemize}
\item falls $z_{m}\in E$:

\begin{itemize}
\item füge eine Produktion $\left(z_{n}\rightarrow a\right)$ zu $P$ (der
Menge der Produktionen) hinzu
\item wenn es eine Regel in $\sigma$ gibt, die von $z_{m}$ fortführt ($\exists_{Z}^{z_{k}}:\exists_{\Sigma}^{b}:\delta\left(z_{m},b\right)=z_{k}$)

\begin{itemize}
\item füge eine Produktion $\left(z_{n}\rightarrow az_{m}\right)$ zu $P$
(der Menge der Produktionen) hinzu
\end{itemize}
\end{itemize}
\item falls $z_{m}\notin E$:

\begin{itemize}
\item füge eine Produktion $\left(z_{n}\rightarrow az_{m}\right)$ zu $P$
(der Menge der Produktionen) hinzu
\end{itemize}
\end{itemize}
\end{itemize}
$M$ und $G$ beschreiben die gleiche Sprache: \[
T\left(M\right)=L\left(G\right)\]



\subsection{Nichtdeterministische (endliche) Automaten\index{Nichtdeterministische Automaten}\index{endliche Automaten}}


\subsubsection{Definition \textsf{\textmd{\small 30}}}

Bei einem nichtdeterministischen (endlichen) Automaten (\emph{NFA\index{NFA}}
nondeterministic finite automation) ist es zugelassen, dass vom selben
Zustand $z\in Z$ aus mehrere (oder auch garkeine) Pfeile ausgehen,
die mit $a\in\Sigma$ beschriftet sind.

Ein NFA $M$ ist ein $5$-Tupel $M=\left(Z,\Sigma,\delta,S,E\right)$:

\begin{itemize}
\item $Z$ \emph{Zustandsmenge\index{Zustandsmenge}} (endlich)
\item $\Sigma$ \emph{Eingabealphabet}\index{Eingabealphabet} (endlich)
\item $Z\cap\Sigma=\emptyset$
\item $\delta:Z\times\Sigma\rightarrow\mathcal{P}\left(Z\right)$\emph{}\\
\emph{(Zustands-)Überführungsfunktion\index{Zustandsüberführungsfunktion}\index{Überführungsfunktion}}
\item $S\subseteq Z$ \emph{Startzustandsmenge\index{Startzustandsmenge}}
\item $E\subseteq Z$ \emph{Endzustandsmenge\index{Endzustandsmenge}}
\end{itemize}

\subsubsection{Zustandsgraph}

Vom Prinzip her wie beim DFA (siehe \vref{sub:Zustandsgraph DFA}).
Einzige Unterschiede sind:

\begin{itemize}
\item Es gibt mehrere Startsustände
\item Es kann von einem Zustand zwei Pfeile mit der gleichen Beschriftung
zu unterschiedlichen Zuständen geben
\end{itemize}

\subsubsection{Sprache des NFA \textsf{\textmd{\small 31}}}

Zu einem gegebenen NFA $M=\left(Z,\Sigma,\delta,S,E\right)$ definieren
wie eine Funktion $\hat{\delta}:\mathcal{P}\left(Z\right)\times\Sigma^{*}\rightarrow\mathcal{P}\left(Z\right)$
durch eine induktive Definition wie folgt (erweitert die Definition
von $\sigma$ von Einzelzeichen zu ganzen Wörtern):

\begin{eqnarray*}
\hat{\delta}\left(Z',\varepsilon\right) & = & Z'\qquad\forall Z'\subseteq Z\\
\hat{\delta}\left(Z',ax\right) & = & \cup_{z\in Z'}\hat{\delta}\left(\delta\left(z,a\right),x\right)\end{eqnarray*}


Die Menge der akzeptierten Wörter bildet die durch den NFA akzeptierte
Sprache: \[
T\left(M\right)=\left\{ x\in\Sigma^{*}|\hat{\delta}\left(S,x\right)\cap E\neq\emptyset\right\} \]


\begin{itemize}
\item eine Sprache $L$ wird durch einen endlichen Automaten erkannt $\Leftrightarrow$
die Sprache ist regulär ($L\in\mathcal{L}_{3}$)
\item Jede von einem NFA akzepierbare Sprache ist auch durch einen DFA akzeptierbar
\end{itemize}

\subsubsection{Vom NFA zum DFA - Potenzmengenkonstruktion \textsf{\textmd{\small 32}}}

Sei $M=\left(Z,\Sigma,\delta,S,E\right)$ ein gegebener NFA. Wir konstruieren
einen DFA $M'=\left(Z',\Sigma,\delta',z_{0}',E'\right)$, der ebenfalls
die gleiche Sprache erkennt $T\left(M\right)=T\left(M'\right)$ wie
folgt (der neue DFA hat Mengen als Zustände):

\begin{itemize}
\item Terminalalphabet $\Sigma$ bleibt unverändert.
\item $Z'=\mathcal{P}\left(Z\right)$ \\
die neuen Zustände sind alle möglichen Teilmengen der alten Zustandsmenge
\item $z_{0}=S$ \\
die Startzustandsmenge ist der neue Startzustand
\item $E'=\left\{ Z'\subseteq Z|Z'\cap E\neq\emptyset\right\} $\\
Alle Zustandsmengen, die Endzustände enthalten sind auch neue Endzustände
\item $\delta'\left(Z_{k},a\right)=\cup_{z\in Z_{k}}\delta\left(z,a\right)=\hat{\delta}\left(Z_{k},a\right)\quad\left(Z_{k}\in Z'\right)$\\
Das Bild eines Urbildes, ist die Menge von allen möglichen Ableitungen
von Elementen aus dem Urbild.
\end{itemize}
Hierbei entstehen in der Regel sehr viele unnötige Zustände und Überführungsfunktionen.
Besser ist den Algorithmus aus \vref{sub:Vom-NFA-zumDFA-efficient}
zu nutzen.

Der Laufzeitkomplexität ist dieses Algorithmus ist $O\left(c^{n}\right)$.


\subsubsection{\label{sub:Vom-NFA-zumDFA-efficient}Vom NFA zum DFA - effizientere
Methode}

Bei folgenden Algorithmus bietet es sich an, zunächst einen Graphen
von $M$ zu zeichnen, und anhand diesem den Graphen von $M'$ anhand
des Algorithmusses zu erstellen. Diesen Graphen sollte man dann erst
zum Schluss als Funktion nierderschreiben.

Sei $M=\left(Z,\Sigma,\delta,S,E\right)$ ein gegebener NFA. Wir konstruieren
einen DFA $M'=\left(Z',\Sigma,\delta',z_{0}',E'\right)$, der ebenfalls
die gleiche Sprache erkennt $T\left(M\right)=T\left(M'\right)$ wie
folgt (der neue DFA hat Mengen als Zustände):

\begin{itemize}
\item Terminalalphabet $\Sigma$ bleibt unverändert.
\item $z_{0}'=S$\\
die Startzustandsmenge ist der neue Startzustand
\item Folgendes solange ausführen, bis sich an $\delta$ und $Z'$ nichts
mehr ändert.

\begin{itemize}
\item Für jedes Element $z_{x}\in Z'$:

\begin{itemize}
\item Für jedes Terminal $t\in\Sigma$:

\begin{itemize}
\item Bestimme für jedes Element $a$ der Menge die den akt. Zustand $z_{x}$
bildet, die Menge der neuen Zustände bezüglich dem Terminal $t$.
$\cup_{a\in z_{x}}\left\{ b\in Z|\delta\left(a,t\right)=b\right\} $ 
\item Fasse diese zu einer neuen Menge $z_{neu}$ zusammen. $z_{neu}=\cup_{a\in z_{x}}\left\{ b\in Z|\delta\left(a,t\right)=b\right\} $
\item Wenn $z_{neu}$ noch nicht in $Z'$ enthalten $\left(z_{neu}\notin Z'\right)$,
füge es in die Zustandsmenge $Z'$ hinzu. $Z'\cup\left\{ z_{neu}\right\} $
\item Wenn die Menge $z_{neu}$ ein Endzustand aus $E$ enthält und $z_{neu}$
noch nicht in $E'$ enthalten ist ($\left(\exists_{z_{neu}}^{a}:a\in E\right)\wedge z_{neu}\notin E'$),
dann füge $z_{neu}$ der Menge $E'$ hinzu.
\item Wenn es in $\delta$ noch keine Regel der Gestalt $\delta\left(z_{x},t\right)=z_{neu}$
gibt, ergänze diese.
\end{itemize}
\end{itemize}
\end{itemize}
\end{itemize}
Der Laufzeitkomplexität ist dieses Algorithmus ist $O\left(c^{n}\right)$.


\subsubsection{Von einer Grammatik zum NFA \textsf{\textmd{\small 35}}}

Für jede reguläre Grammatik $G=\left(V,\Sigma,P,S\right)$ (Typ 3)
gibt es einen NFA $M=\left(Z,\Sigma,\delta,S',E\right)$ mit $L\left(G\right)=M\left(G\right)$.
Diese lässt sich wie folgt konstruieren:

\begin{itemize}
\item $Z=V\cup\left\{ X\right\} ,\quad X\notin V$\\
Die Zustandsmenge besteht aus der Menge der Variablen, zuzüglich einer
neuen Variable (hier $X$)
\item $S'=\left\{ S\right\} $\\
Der Startzustand ist die Menge, die nur die Startvariable enthält
\item $E=\left\{ \begin{array}{cc}
\left\{ S,X\right\} , & \left(S\rightarrow\varepsilon\right)\in P\\
\left\{ X\right\} , & \left(S\rightarrow\varepsilon\right)\notin P\end{array}\right.$\\
Die Menge der Endzustände enthält $X$ und wenn es eine Produktion
der Form $\left(S\rightarrow\varepsilon\right)\in P$ gibt zusätzlich
auch noch $S$
\item $B\in\delta\left(A,a\right),\quad\left(A\rightarrow aB\right)\in P$\\
Erstelle für alle Produktionen der Form $\left(A\rightarrow aB\right)\in P$
eine Regel für $\delta$ mit $B\in\delta\left(A,a\right)$
\item $X\in\delta\left(A,a\right),\quad\left(A\rightarrow a\right)\in P$\\
Erstelle für alle Produktionen der Form $\left(A\rightarrow a\right)\in P$
eine Regel für $\delta$ mit $X\in\delta\left(A,a\right)$
\end{itemize}
Der Laufzeitkomplexität ist dieses Algorithmus ist $O\left(n\right)$.


\subsection{Reguläre Ausdrücke\index{Reguläre Ausdrücke} \textsf{\textmd{\small 36}}}

Reguläre Ausdrücke sind spezielle Formen, mit denen (reguläre / Typ
3) Sprachen definiert werden können. Folgendes sind reguläre Ausdrücke
(mit jeweils den von Ihnen beschriebenen Sprachen):

\begin{itemize}
\item $\gamma=\emptyset\Rightarrow L\left(\gamma\right)=\emptyset$
\item $\gamma=\varepsilon\Rightarrow L\left(\gamma\right)=\left\{ \varepsilon\right\} $
\item $\forall_{\Sigma}^{a}:\gamma=a\Rightarrow L\left(\gamma\right)=\left\{ a\right\} $
\item $\gamma=\alpha\beta\Rightarrow L\left(\gamma\right)=L\left(\alpha\right)L\left(\beta\right)$
\item $\gamma=\left(\alpha|\beta\right)\Rightarrow L\left(\gamma\right)=L\left(\alpha\right)\cup L\left(\beta\right)$
\item $\gamma=\left(\alpha\right)^{*}\Rightarrow L\left(\gamma\right)=L\left(\alpha\right)^{*}$
\end{itemize}
Jedem regulären Ausdruck lässt sich ein NFA (und dadurch auch DFA)
zuordnen, der die gleiche Sprache beschreibt.


\subsection{\label{sub:Das-Pumping-Lemma}Das Pumping Lemma\index{Pumping Lemma}
\textsf{\textmd{\small 39}}}

Das Pumping Lemma (Schleifenlemma\index{Schleifenlemma}, Lemma von
Bar-Hillel\index{Hillel}, $uvw$-Theorem\index{uvw-Theorem}) ist
ein wichtiges Hilfsmittel, um zu Zeigen, das eine Sprache nicht regulär
ist.

Sei $L$ eine reguläre Sprache. Dann gibt es eine Zahl $n$, so dass
sich alle Wörter $x\in L$ mit $\left|x\right|\geq n$ zerlegen lassen
in $x=uvw$, so dass folgende Eigenschaften erfüllt sind:

\begin{itemize}
\item $\left|v\right|\geq1$
\item $\left|uv\right|\leq n$
\item $\forall i\geq0:uv^{i}w\in L$
\end{itemize}
Es gibt auch Sprachen die das Pumping Lemma erfüllen, und nicht regulär
sind. Das bedeutet, das mit dem Pumping Lemma nur das nicht regulärsein
von Sprachen gezeigt werden kann.

\[
L\in\mathcal{L}_{3}\Rightarrow\left[\exists_{\mathbb{N}}^{n}:\left(\forall_{L}^{x}\left|x\right|\geq n:\left(\exists_{\Sigma^{*}}^{u,v,w}x=uvw\wedge\left|v\right|\geq1\wedge\left|uv\right|\leq n:\left(\forall i\geq0:\left(uv^{i}w\in L\right)\right)\right)\right)\right]\]


Umgekehrt gilt:

\[
\left[\forall_{\mathbb{N}}^{n}:\left(\exists_{L}^{x}\left|x\right|\geq n:\left(\forall_{\Sigma^{*}}^{u,v,w}x=uvw\wedge\left|v\right|\geq1\wedge\left|uv\right|\leq n:\left(\exists i\geq0:\left(uv^{i}w\notin L\right)\right)\right)\right)\right]\Rightarrow L\notin\mathcal{L}_{3}\]


\begin{itemize}
\item Eine Sprache, bei der mehrere Exponenten in irgendwelchen Beziehungen
zueinander stehen, sind (laut Pumping Lemma) nicht regulär.
\end{itemize}

\subsection{Äquivalenzrelation\index{Äquivalenzrelation} und Minimalautomat\index{Minimalautomat}
\textsf{\textmd{\small 42}}}


\subsubsection{Definition Äquivalenzrelation \textsf{\textmd{\small 42}}}

Es gilt $xR_{L}y$ genau dann, wenn für alle Wörter $z\in\Sigma^{*}$
gilt: $xz\in L\Leftrightarrow yz\in L$:

\[
\left(xR_{L}y\right)\Leftrightarrow\left(\forall_{\Sigma^{*}}^{z}:xz\in L\Leftrightarrow yz\in L\right)\]


Mit Hilfe von $R_{L}$ wird die Sprache $L$ in disjunkte Äquivalenzklassen\index{Äquivalentzklassen}
unterteilt. Wenn der Index von $R_{L}$ ($\mathrm{Index}\left(R_{L}\right)$
ist die Anzahl solcher Äquivalenzklassen, siehe \vref{sub:=C4quivalenzklassen-&-Index})
endlich ist, ist $L$ eine reguläre Sprache:\[
\left(\mathrm{Index}\left(R_{L}\right)<\infty\right)\Leftrightarrow L\in\mathcal{L}_{3}\]



\subsubsection{Algorithmus Minimalautomat \textsf{\textmd{\small 46}}}

Gegeben sei ein DFA $M=\left(Z,\Sigma,\delta,z_{0},E\right)$, der
nach folgenden Algorithmus in eine Zustandsminimalen\index{Zustandsminimalen}
DFA $M'=\left(Z',\Sigma,\delta',z_{0},E'\right)$ überführt wird.

\begin{itemize}
\item entferne alle Zustände aus $Z$ die vom Startzustand aus nicht erreicht
werden können.
\item Stelle eine Kreuztabelle aller Zustandspaare $\left\{ z,z'\right\} $
mit $z\neq z'$ von $M$ auf (entspricht einer quadratischen Matrize,
von der nur das ober/unter Dreieck ohne die Hauptdiagonale genommen
wurde)
\item Markiere alle Paare $\left\{ z,z'\right\} $ mit $z\in E$ und $z'\notin E$
(oder umgekehrt).
\item Wiederhole folgendes, bis sich keine Änderung in der Tabelle mehr
ergibt

\begin{itemize}
\item Für jedes noch unmarkierte Paar $\left\{ z,z'\right\} $ und jedes
$a\in\Sigma$ (es reicht, das dies für ein Terminal gilt) teste, ob
$\left\{ \delta\left(z,a\right),\delta\left(z',a\right)\right\} $
bereits markiert ist. Wenn ja: markiere auch $\left\{ z,z'\right\} $
\end{itemize}
\item Alle jetzt noch unmarkierten Paare können jeweils zu einem Zustand
verschmolzen werden. Das heißt, das man wenn z.B. das Paar $\left(z,z'\right)$
nicht markiert ist, wird für beide zusammen ein neuer Zustand geschaffen.
\end{itemize}
Dieser Algorithmus hat (bei geeigneter Implementierung (siehe Hopcroft\index{Hopcroft}/Ullmann\index{Ullmann}))
die Laufzeitkomplexität $O\left(n^{2}\right)$


\subsection{Abschlusseigenschaften\index{Abschlusseigenschaften} \textsf{\textmd{\small 48}}}

Die regulären Sprachen sind abgeschlossen unter:

\begin{itemize}
\item Vereinigung\index{Vereinigung}\\
$L\left(G_{1}\right)\cup L\left(G_{2}\right)$
\item Schnitt\index{Schnitt}\\
Wort muss in beiden Sprachen vorkommen
\item Komplement\index{Komplement}\\
Bei Grammatik: Endzustände ersetzen gegen Variablen ohne die alten
Endzustände
\item Produkt\index{Produkt}\\
Konkatenation der Wörter aus den einzelnen Sprachen\\
$L\left(G_{1}\right)L\left(G_{2}\right)$
\item Stern\index{Stern}\\
Wiederholen der Wörter
\end{itemize}
Umkehrschluss nicht möglich: Wenn nichtreguläre Sprachen kombiniert
werden, kann das Resultat trotzdem eine reguläre Sprache sein. Das
einzige was sich Aussagen lässt ist, dass wenn eine Sprache nicht
Regulär ist, mindestens eine Ihrer Komponenten auch nicht regulär
war.


\subsection{Entscheidbarkeit\index{Entscheidbarkeit} \textsf{\textmd{\small 49}}}


\subsubsection{Wortproblem\index{Wortproblem}}

Das \emph{Wortproblem} (gegeben: $x$, gefragt: ist $x\in L\left(G\right)$
bzw. $x\in T\left(M\right)$) ist mit Hilfe eines DFA leicht möglich.
Verfolge einfach Zeichen für Zeichen die Zustandsübergänge im Automaten,
die durch die Eingabe $x$ hervorgerufen werden. Falls ein Endzustand
erreicht wird, liegt $x$ in der Sprache. Die Laufzeitkomplexität
beträgt hier $O\left(n\right)$.


\subsubsection{Leerheitsproblem\index{Leerheitsproblem}}

Das \emph{Leerheitsproblem} stellt bei gegebenem $G$ (bzw. $M$)
die Frage, ob $L\left(G\right)=\emptyset$ (bzw. $T\left(M\right)=\emptyset$).
Sei $M$ ein gegebener Automat für die Sprache. $T\left(M\right)$
ist genau dann leer, wenn es keinen Pfad vom (einem) Startzustand
zu einem Endzustand gibt.


\subsubsection{Endlichkeitsproblem\index{Endlichkeitsproblem}}

Das \emph{Endlichkeitsproblem} stellt bei gegebenem $G$ (bzw. $M$)
die Frage, ob $\left|L\left(G\right)\right|<\infty$ (bzw. $T\left(M\right)<\infty$),
also ob die definierte Sprache endlich oder unendlich ist. 

Hier gibt es zwei Verfahren:

\begin{itemize}
\item Sei $n$ die Pumping Lemma (siehe \vref{sub:Das-Pumping-Lemma}) Zahl
zu $L$. Es gilt:\[
\left|L\right|=\infty\Leftrightarrow\exists_{L}^{x}:\left|x\right|\geq n\wedge\left|x\right|<2n\]


\begin{itemize}
\item Diese Argument verläuft so, dass alle Wörter der Länge $\geq n$ und
$<2n$ auf Mitgliedschaft in $L$ geprüft werden müssen.
\item Die Laufzeitkomplexität beträgt $O\left(c^{n}\right)$
\end{itemize}
\item Es ist $\left|T\left(M\right)\right|=\infty$ genau dann, wenn es
in dem von Startzustand erreichbaren Teilgraphen einen Zyklus gibt,
und wenn von diesem Zyklus aus ein Endzustand erreichbar ist. \[
\exists_{\mathrm{Startzustand}}^{z_{0}}:\exists_{\mathrm{Zustand}}^{z_{1}}:\exists_{\mathrm{Endzustand}}^{z_{2}}:\quad z_{0}\Rightarrow^{*}z_{1}\Rightarrow^{+}z_{1}\Rightarrow^{*}z_{2}\]


\begin{itemize}
\item wesentlich effizienter als erste Methode
\end{itemize}
\end{itemize}

\subsubsection{Schnittproblem\index{Schnittproblem}}

Das \emph{Schnittproblem} stellt bei gegebenen $G_{1},G_{2}$ (bzw.
$M_{1},M_{2}$) die Frage, ob $L\left(G_{1}\right)\cap L\left(G_{2}\right)=\emptyset$
(bzw. $T\left(M_{1}\right)\cap T\left(M_{2}\right)=\emptyset$). Hierfür
muss man eine Sprache (Grammatik) konstruieren, die aus $G_{1}$ und
$G_{2}$ hervorgeht, und die beide Grammatiken sozusagen simultan
durchläuft. Hiermit ist dieses Problem auf das Leerheitsproblem zurückgeführt.


\subsubsection{Äquivalenzproblem\index{Äquivalenzproblem}}

Das \emph{Äquivalenzproblem} stellt bei gegebene $G_{1},G_{2}$ (bzw.
$M_{1},M_{2}$) die Frage, ob $L\left(G_{1}\right)=L\left(G_{2}\right)$
(bzw. $T\left(M_{1}\right)=T\left(M_{2}\right)$). Hierzu gibt es
mehrere Lösungsmöglichkeiten:

\begin{itemize}
\item Per Minimalautomat:

\begin{itemize}
\item Wenn Sprachen nicht als DFA's vorliegen, diese dahingehend transformieren.
\item Jeweils den Minimalautomaten konstruieren
\item Diese auf Isomorphie (Umbenennung der Variablen) untersuchen, wenn
ja, dann sind die Sprachen gleich.
\end{itemize}
\item Rückführung auf Leerheitsproblem:\[
L_{1}=L_{2}\Leftrightarrow\left(L_{1}\cap\overline{L_{2}}\right)\cup\left(\overline{L_{1}}\cap L_{2}\right)=\emptyset\]

\end{itemize}
Am Effizientesten ist die Methode des Minimalautomaten, wenn die Sprache
bereits als DFA vorliegt. Allgemein ist das Problem \emph{NP-hart\index{NP-hart}},
hat also eine Laufzeitkomplexität von $O\left(c^{n}\right)$.


\section{Kontextfreie Sprachen\index{Kontextfreie Sprachen} (Typ 2) \textsf{\textmd{\small 51}}}

Werden gebraucht, um korrekt geklammerte Ausdrücke zu erstellen.


\subsection{Normalformen\index{Normalformen} \textsf{\textmd{\small 52}}}

Für die Normalformen müssen folgende Regeln gelten (durch Umformungen
erreichbar):

\begin{itemize}
\item $\varepsilon$-Regeln entfernen (siehe \vref{ite:Entfernen epsilon Regeln(Typ2)})
\item Kettenregeln $\left(A\rightarrow B\right)$ entfernen

\begin{itemize}
\item Bestimme äquivalente Variable:

\begin{itemize}
\item $A\leftrightarrow B$ gdw. $A\Rightarrow^{*}B$ und $B\Rightarrow^{*}A$
\item $\left[A\right]:=\left\{ B\in V|A\leftrightarrow B\right\} $
\item Wähle ein $B_{0}\in\left[A\right]$aus, uns ersetze alle Vorkommen
von $B\in\left[A\right]$ durch $B_{0}$
\end{itemize}
\item Sei $V=\left\{ A_{1},A_{2},\ldots,A_{n}\right\} $ die aktuelle Menge
der Variablen, und zwar so sortiert, dass aus $\left(A_{i}\rightarrow A_{j}\right)\in P$
folgt $i<j$
\item Wir gehen nun von von hinten nach vorne vor und eliminieren für $k=n-1,\ldots,1$
alle Regeln der Form $\left(A_{k}\rightarrow A_{k'}\right),k'>k$.
Seien die Regeln, mit $A_{k'}$auf der linken Seite, gegeben durch
$A_{k'}\rightarrow x_{1}|x_{2}|\ldots|x_{k}$. Wir fügen dann die
Regeln $A_{k}\rightarrow x_{1}|x_{2}|\ldots|x_{k}$ hinzu.
\end{itemize}
\end{itemize}

\subsubsection{Chomsky Normalform\index{Chomsky Normalform} \textsf{\textmd{\small 53}}}

Zu jeder kontextfreien Grammatik $G$ mit $\varepsilon\notin L\left(G\right)$
existiert eine \emph{Chomsky Normalform} (CNF\index{CNF}). Die Chomsky
Normalform liegt vor, wenn alle Regeln eine der folgenden Formen haben:

\begin{itemize}
\item $A\rightarrow AB$
\item $A\rightarrow a$
\end{itemize}
Ist $w\in L\left(G\right)$, so gilt:\[
S\Rightarrow_{G}^{2\left|w\right|-1}w\]


Ein Algorithmus für die Umformung findet sich im Buch (vorher Kettenregeln,
und $\varepsilon$-Regeln entfernen!)


\subsubsection{Greifenbach Normalform\index{Greifenbach Normalform} \textsf{\textmd{\small 54}}}

Zu jeder kontextfreien Grammatik $G$ mit $\varepsilon\notin L\left(G\right)$
existiert eine \emph{Greifenbach Normalform}. Diese liegt vor, wenn
alle Regeln eine der folgenden Formen haben:

\begin{itemize}
\item $A\rightarrow aB_{1}B_{2}\ldots B_{k}\quad\left(k\geq0\right)$
\end{itemize}
Die Greifenbach Grammatik ist eine Erweiterung der regulären Grammatik,
dort wäre nur $k=0$ und $k=1$ zugelassen.

Ein Algorithmus für die Umformung findet sich im Buch.


\subsection{Das Pumping Lemma\index{Pumping Lemma} (uvwxy-Theorem\index{uvwxy-Theorem})
\textsf{\textmd{\small 56}}}

Sei $L$ eine reguläre Sprache. Dann gibt es eine Zahl $n\in\mathbb{N}$,
sodass sich alle Wörter $z\in L$ mit $\left|z\right|\geq n$ zerlegen
lassen als $x=uvwxy$ mit folgenden Eigenschaften:

\begin{enumerate}
\item $\left|vx\right|\geq1$
\item $\left|vwx\right|\leq n$
\item $\forall i\geq0:uv^{i}wx^{i}y\in L$
\end{enumerate}
\[
L\in\mathcal{L}_{2}\Rightarrow\left[\exists_{\mathbb{N}}^{n}:\left(\forall_{L}^{z}\left|z\right|\geq n:\left(\exists_{\Sigma^{*}}^{u,v,w,x,y}z=uvwxy\wedge\left|vx\right|\ge1\wedge\left|vwx\right|\leq n:\left(\forall i\geq0:\left(uv^{i}wx^{i}y\in L\right)\right)\right)\right)\right]\]


Das Pumping Lemma (Schleifenlemma\index{Schleifenlemma}, Lemma von
Bar-Hillel\index{Hillel}, $uvwxy$-Theorem\index{uvwxy-Theorem})
ist ein wichtiges Hilfsmittel, um zu Zeigen, das eine Sprache nicht
regulär ist.

Die Kontraposition lautet wie folgt:\[
\left[\forall_{\mathbb{N}}^{n}:\left(\exists_{L}^{z}\left|z\right|\geq n:\left(\forall_{\Sigma^{*}}^{u,v,w,x,y}z=uvwxy\wedge\left|vx\right|\geq1\wedge\left|vwx\right|\leq n:\left(\exists i\geq0:\left(uv^{i}wx^{i}y\notin L\right)\right)\right)\right)\right]\Rightarrow L\notin\mathcal{L}_{2}\]



\subsubsection{Satz für einelementige Alphabete \textsf{\textmd{\small 62}}}

Jede kontextfreie Sprache über einem einelementigen Alphabet ist bereits
regulär.


\subsubsection{Sprachen mit Wiederholungen}

\begin{itemize}
\item Eine Sprache, bei der keine Exponenten in irgendwelchen Beziehungen
zueinander stehen, sind (laut Pumping Lemma) regulär.
\item Eine Sprache, bei der genau zwei Exponenten in irgendwelchen Beziehungen
zueinander stehen, sind (laut Pumping Lemma) Kontext frei.
\item Eine Sprache, bei der drei oder mehr Exponenten in irgendwelchen Beziehungen
zueinander stehen, sind (laut Pumping Lemma) Kontext sensitiv.
\end{itemize}

\subsection{Abschlusseigenschaften\index{Abschlusseigenschaften} \textsf{\textmd{\small 62}}}

Die kontextfreien Sprachen sind abgeschlossen unter:

\begin{itemize}
\item Vereinigung\index{Vereinigung}\\
$L\left(G_{1}\right)\cup L\left(G_{2}\right)$
\item Produkt\index{Produkt}\\
Konkatenation der Wörter aus den einzelnen Sprachen\\
$L\left(G_{1}\right)L\left(G_{2}\right)$
\item Stern\index{Stern}\\
Wiederholen der Wörter
\end{itemize}
Umkehrschluss nicht möglich: Wenn nicht kontextfreie Sprachen kombiniert
werden, kann das Resultat trotzdem eine kontextfreie Sprache sein.
Das einzige was sich Aussagen lässt ist, dass wenn eine Sprache nicht
kontextfreie ist, mindestens eine Ihrer Komponenten auch nicht kontextfrei
war.

\begin{itemize}
\item Der Durchschnitt einer (deterministischen) kontextfreien Sprache mit
einer regulären Sprache ist wieder (deterministisch) kontextfrei
\end{itemize}

\subsection{Der CYK-Algorithmus\index{CYK-Algorithmus} \textsf{\textmd{\small 64}}}

Der \emph{CYK-Algorithmus} (Cocke, Younger, Kasami) ist eine Möglichkeit
das Wortproblem\index{Wortproblem} für kontextfreie Sprachen zu lösen.
Dafür muss die Grammatik in der Chomsky Normalform vorliegen (gegeben
falls umformen).

\begin{enumerate}
\item Erstelle eine Tabelle, deren Zeilenanzahl $z$ gleich der Länge des
Wortes $w$ ist, für das dass Wortproblem gelöst werden soll. Die
Spaltenanzahl $s$ ist um eins höher.
\item Trage in die erste Zeile die einzelnen Terminale von $w$ ein.
\item Trage in die Zweite Spalte alle Variablen ein, aus denen man die Variablen
oberhalb von ihnen ableiten kann.
\item Fülle die restlichen Zellen nun zeilenweise aus. Beachte, das man
in der $j$ ten Zeile immer nur die ersten $\left|w\right|-j+1$ Zellen
ausfüllen braucht (kann).

\begin{enumerate}
\item in die Aktuelle Zelle $x_{j,i}$ kommen alle Variablen $V$ hinein,
aus denen man $AB$ ableiten kann ($V\rightarrow AB$), wobei $A$
ein Element der Menge aller Zelleninhalte oberhalb $\left(\uparrow\right)$
von $x_{j,i}$ und $B$ ein Element der Menge aller Zelleninhalte
diagonal rechts oberhalb $\left(\nearrow\right)$ von $x_{j,i}$ ist.
\end{enumerate}
\item Wenn das Startsymbol $S$ ein Element der ersten Zelle der letzten
Zeile ist, dann ist $w\in L\left(G\right)$ ansonsten $w\notin L\left(G\right)$.
\end{enumerate}

\subsection{Kellerautomaten\index{Kellerautomaten} \textsf{\textmd{\small 67}}}


\subsubsection{Definition \textsf{\textmd{\small 67}}}

Ein (nichtdeterministischer) \emph{Kellerautomat}, kurz PDA\index{PDA}
(pushdown automation), wird auf ein Eingabewort\index{Eingabewort}
ist eine Erweiterung von DFA / NFA um das einen Keller als Speicher.
Ein PDA $M$ wird spezifiziert durch ein $6$-Tupel\[
M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\#\right)\]


\begin{itemize}
\item $Z$ endliche Menge der (internen) \emph{Zustände}\index{Zustände}
\item $\Sigma$ endliches \emph{Eingabealphabet}\index{Eingabealphabet}
\item $\Gamma$ endliches \emph{Kelleralphabet\index{Kelleralphabet}} 
\item $z_{0}\in Z$ \emph{Startzustand\index{Startzustand}}
\item $\delta:Z\times\left(\Sigma\cap\left\{ \varepsilon\right\} \right)\times\Gamma\rightarrow\mathcal{P}_{e}\left(Z\times\Gamma^{*}\right)$
Überführungsfunktion\index{Ueberfuehrungsfunktion}

\begin{itemize}
\item z.B. $\left(z',B_{1}\ldots B_{k}\right)\in\delta\left(z,a,A\right)$
\item $\left(z',B_{1}\ldots B_{k}\right)\in\delta\left(z,\epsilon,A\right)$
spontaner Zustandswechsel ohne lesen eines neuen Terminals
\end{itemize}
\item $\#\in\Gamma$ das unterste \emph{Kellersymbol\index{Kellersymbol}}
\end{itemize}
Eine \emph{Konfiguration\index{Konfiguration}} $k$ eines Kellerautomaten
ist durch ein Tripel $k\in Z\times\Sigma^{*}\times\Gamma^{*}$ gegeben.

\begin{itemize}
\item Startkonfiguration\index{Startkonfiguration} zur Eingabe $x\in\Sigma^{*}$:
$\left(z_{0},x,\#\right)$
\end{itemize}
Die \emph{Rechenschrittrelation\index{Rechenschrittrelation}} $\vdash$ist
wie folgt definiert: 

\[
\left(z,a_{1}\ldots a_{n},A_{1}\ldots A_{m}\right)\vdash\left\{ \begin{array}{cc}
\left(z',a_{2}\ldots a_{n},B_{1}\ldots B_{k}A_{2}\ldots A_{m}\right) & \left(z',B_{1}\ldots B_{k}\right)\in\delta\left(z,a_{1},A_{1}\right)\\
\left(z',a_{1}a_{2}\ldots a_{n},B_{1}\ldots B_{k}A_{2}\ldots A_{m}\right) & \left(z',B_{1}\ldots B_{k}\right)\in\delta\left(z,\varepsilon,A_{1}\right)\end{array}\right.\]


\begin{itemize}
\item es wird immer in Abhängigkeit vom obersten Symbol auf dem Stack, dem
akt. internen Zustand, und \emph{eventuell} (wenn es eine Regel mit
einem $\varepsilon$ an zweiter Stelle gibt, dann nicht) dem Eingabeterminal
ein neuer interner Zustand und ein Satz an Symbolen bestimmt, die
auf den Stack gelegt werden, nachdem das oberste Symbol auf dem Stack
entfernt wurde. 
\end{itemize}
\[
k\vdash^{*}k'\Leftrightarrow\left(\exists m\geq0:\exists k_{0},k_{1},\ldots,k_{m}:k=k_{0}\wedge k'=k_{m}\wedge\forall_{\left[0,m-1\right]}^{i}:k_{i}\vdash k_{i+1}\right)\]


Die von $M$ (durch leeren Keller) \emph{akzeptierte Sprache} ist:

\[
N\left(M\right)=\left\{ x\in\Sigma^{*}|\exists_{Z}^{z}:\left(z_{0},x,\#\right)\vdash^{*}\left(z,\varepsilon,\varepsilon\right)\right\} \]


\begin{itemize}
\item $L$ kontextfrei $\Leftrightarrow$ $L$ wird von einem nichtdeterministischen
Kellerautomaten akzeptiert
\item Zu jedem PDA $M$ gibt es einen PDA $M'$ mit nur einem Zustand, sodass
$N\left(M\right)=N\left(M'\right)$ gilt

\begin{itemize}
\item durch Transformation in Grammatik, und anschließende Rücktransformation.
\end{itemize}
\end{itemize}

\subsubsection{Von Grammatik zum Kellerautomaten \textsf{\textmd{\small 72}}}

Gegeben ist eine kontextfreie Grammatik $G=\left(V,\Sigma,P,S\right)$
(Chomskynormalisierung \emph{nicht} erforderlich, sogar eher kontraproduktiv,
da die alles viel komplizierter macht). Ausgegeben wird ein PDA $M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\#\right)$.

\begin{itemize}
\item $Z=\left\{ z\right\} $
\item $\Sigma$ wird 1:1 übernommen
\item $\Gamma=V\cup\Sigma$
\item $z_{0}=z$ 
\item $\#=S$ Startvariable wird als unterstes Kellersymbol genommen
\item Erstellen der Überführungsfunktion $\delta$

\begin{itemize}
\item Für alle Produktionen $\left(l\rightarrow r\right)\in P$

\begin{itemize}
\item Füge eine Regel der Form $\delta\left(z,\varepsilon,l\right)=\left(z,r\right)$
hinzu
\end{itemize}
\item Für alle Terminale $a\in\Sigma$

\begin{itemize}
\item Füge eine Regel der Form $\delta\left(z,a,a\right)=\left(z,\varepsilon\right)$
hinzu
\end{itemize}
\end{itemize}
\end{itemize}

\subsubsection{Von Kellerautomaten zur Grammatik \textsf{\textmd{\small 73}}}

Gegeben ist ein PDA $M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\#\right)$.
Ausgegeben wird eine kontextfreie Grammatik $G=\left(V,\Sigma,P,S\right)$.

\begin{itemize}
\item $\Sigma$ wird 1:1 übernommen
\item $S$ wird mit $S$ besetzt
\item $V=\left\{ S\right\} \cup\left(Z\times\Gamma\times Z\right)$
\item Erstelle Produktionsregeln $P$

\begin{itemize}
\item Für alle Zustände $z\in Z$

\begin{itemize}
\item Füge eine Regel der Form $S\rightarrow\left(z_{0},\#,z\right)$ hinzu
\end{itemize}
\item Für alle $\left(z',\varepsilon\right)\in\delta\left(z,a,A\right)$

\begin{itemize}
\item Füge eine Regel der Form $\left(z,A,z'\right)\rightarrow a$ hinzu
\end{itemize}
\item Für alle $\left(z_{1},B\right)\in\delta\left(z,a,A\right)$ und alle
$z'\in Z$

\begin{itemize}
\item Füge eine Regel der Form $\left(z,A,z'\right)\rightarrow a\left(z_{1},B,z'\right)$
hinzu
\end{itemize}
\item Für alle $\left(z_{1},BC\right)\in\delta\left(z,a,A\right)$ und alle
$z',z_{2}\in Z$

\begin{itemize}
\item Füge eine Regel der Form $\left(z,A,z'\right)\rightarrow a\left(z_{1},B,z_{2}\right)\left(z_{2},C,z'\right)$
hinzu
\end{itemize}
\end{itemize}
\end{itemize}
Ist $G$ in Greibach Normalform, so kann ein PDA $M$ mit $L\left(G\right)=N\left(M\right)$
konstruiert werden, der keine $\varepsilon$-Übergänge hat.


\subsection{Deterministisch kontextfreie Sprachen \textsf{\textmd{\small 76}}}

Ein Kellerautomat $M$ heißt \emph{deterministisch\index{deterministisch}},
falls für alle $z\in Z$, $a\in\Sigma$ und $A\in\Gamma$ gilt:\[
\left|\delta\left(z,a,A\right)\right|+\left|\delta\left(z,\varepsilon,A\right)\right|\leq1\]


Ferner hat ein deterministischer Kellerautomat (Deterministic Push
Down Automation = DPDA\index{DPDA}) eine ausgezeichnete Menge von
\emph{Endzuständen} $E\subseteq Z$.

\[
T\left(M\right)=\left\{ x\in\Sigma^{*}|\exists z\in E:\left(z_{0},x,\#\right)\vdash^{*}\left(z,\varepsilon,\alpha\right)\right\} \]
 ist die von einem DPDA akzeptierte Sprache.

Eine Sprache $L\subseteq\Sigma^{*}$ heißt \emph{deterministisch kontextfrei\index{kontextfrei!deterministisch}\index{deterministisch kontextfrei}},
wenn es einen DPDA $M$ gibt mit $L=T\left(M\right)$.

\begin{itemize}
\item $\mathcal{L}_{2}\subset$ deterministisch kontextfreie Sprachen $\subset\mathcal{L}_{3}$
\item Stimmen mit den $LR\left(k\right)$-Sprachen überein (siehe Compilerbau)\index{LR(k)}
\item Die deterministisch kontextfreien Sprachen sind

\begin{itemize}
\item unter Komplementbildung abgeschlossen
\item \emph{nicht} unter Durchschnitt abgeschlossen
\item \emph{nicht} unter Komplementbildung abgeschlossen
\end{itemize}
\item Der Durchschnitt einer (deterministischen) kontextfreien Sprache mit
einer regulären Sprache ist wieder (deterministisch) kontextfrei
\end{itemize}

\subsection{Entscheidbarkeit\index{Entscheidbarkeit} \textsf{\textmd{\small 78}}}

\begin{description}
\item [Wortproblem\index{Wortproblem}]entscheidbar (CYK-Algorithmus)
\item [Leerheitsproblem\index{Leerheitsproblem}]entscheidbar

\begin{itemize}
\item Idee: markiere Variable $A$ mit $\left\{ x\in\Sigma^{*}|A\Rightarrow^{*}x\right\} \neq\emptyset$
\end{itemize}
\item [Endlichkeitsproblem\index{Endlichkeitsproblem}]entscheidbar

\begin{itemize}
\item $\left|L\right|=\infty\Leftrightarrow\exists x\in L:n\leq\left|x\right|<2n$
\end{itemize}
\item [Gleichheit]Wenn $L_{1}$ det. kontextfrei, und $L_{2}$ regulär.
Ist $L_{1}=L_{2}$ entscheidbar? Ja, siehe Buch.
\item [Äquivalenzproblem\index{Aequivalentzproblem}]für DPDA's entscheidbar
\end{description}

\section{Kontextsensitive Sprachen (Typ 1) und Typ 0 Sprachen \textsf{\textmd{\small 79}}}


\subsection{Kuroda Normalform\index{Kuroda Normalform} \textsf{\textmd{\small 79}}}

Eine Typ 1 Grammatik ist in \emph{Kuroda Normalform}, falls alle Regeln
eine der 4 Formen haben:

\begin{itemize}
\item $A\rightarrow a$
\item $A\rightarrow B$
\item $A\rightarrow BC$
\item $AB\rightarrow CD$
\end{itemize}
Hierbei stehen $A,B,C,D$ für Variablen und $a$ für ein Terminalsymbol.

\begin{itemize}
\item Für jede Typ 1 Grammatik $G$ mit $\varepsilon\neq L\left(G\right)$
gibt es eine Grammatik $G'$ in Kuroda Normalform mit $L\left(G\right)=L\left(G'\right)$

\begin{itemize}
\item Durch aufbrechen der Regeln, ähnlich Chomsky-Normalisierung
\end{itemize}
\end{itemize}

\subsection{Turingmaschine\index{Turingmaschine} \textsf{\textmd{\small 81}}}


\subsubsection{Definition \textsf{\textmd{\small 81}}}

Eine \emph{Touringmaschine} (Kurz: TM\index{TM}) ist gegeben durch
ein 7-Tupel\[
M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\square,E\right)\]


\begin{itemize}
\item $Z$ die endliche \emph{Zustandsmenge\index{Zustandsmenge}}
\item $\Sigma$ das \emph{Eingabealphabet\index{Eingabealphabet}}
\item $\Gamma\supset\Sigma$ das \emph{Arbeitsalphabet\index{Arbeitsalphabet}}
\item $\delta:Z\times\Gamma\rightarrow Z\times\Gamma\times\left\{ L,N,R\right\} $
im deterministischen Fall\\
(bzw. $\delta:Z\times\Gamma\rightarrow\mathcal{P}\left(Z\times\Gamma\times\left\{ L,N,R\right\} \right)$
im nichtdeterministischen Fall)\\
die \emph{Überführungsfunktion\index{Ueberfuehrungsfunktion}}
\item $z_{0}\in Z$ der \emph{Startzustand}\index{Startzustand}
\item $\square\in\left(\Gamma\backslash\Sigma\right)$ das \emph{Blank\index{Blank}}
(\emph{Leerzeichen\index{Leerzeichen}})
\item $E\subseteq Z$ die Menge der \emph{Endzustände\index{Endzustaende}}
\end{itemize}
Die Überführungsfunktion bedeutet informal: \\
${\scriptstyle \delta\left(\mathrm{alter\: Zustand},\mathrm{Symbol\, vor\, Lesekopf}\right)=\left(\mathrm{neuer\: Zustand},\mathrm{neues\, Symbol\, auf\, Band},\mathrm{Kopfbewegung\, LinksRechtNeutral}\right)}$

Eine \emph{Konfiguration\index{Konfiguration}} der TM $M$ ist ein
Wort $k\in\Gamma^{*}Z\Gamma^{+}$. $k$ deckt den von $\square$ verschiedenen
Teil des Bandes ab. Dabei sind die einzelnen Teile des Wortes: Band
Links vom Lesekopf; Akt. Zustand; Band unter und Rechts vom Lesekopf.

Die \emph{Startkonfiguration}\index{Startkonfiguration} für Eingabe
$x\in\Sigma^{*}$ ist $z_{0}x$.

Die \emph{Berechnungsrelation\index{Berechnungsrelation}} $\vdash$
ersetzt den Zustand durch den neuen Zustand, ersetzt das Symbol auf
dem Band durch das neue Symbol, und führt die Kopfbewegung aus, indem
bei L (R) ein Zeichen von Links nach Rechts neben dem Zustand (bzw.
andersherum) bewegt wird. Falls sich der Kopf am Bandrand befindet,
können an den Rändern zusätzliche $\square$ eingefügt werden.

Die von einem TM $M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\square,E\right)$
\emph{akzeptierte Sprache} ist definiert als\[
T\left(M\right)=\left\{ x\in\Sigma^{*}|z_{0}x\vdash^{*}\alpha z\beta\left(\alpha,\beta\in\Gamma^{*},z\in E\right)\right\} \]


\begin{itemize}
\item Die durch allgemeine TMen akzeptierten Sprachen sind genau die Typ
0 Sprachen
\end{itemize}

\subsubsection{Linear Beschränkte Turingmaschinen \textsf{\textmd{\small 84}}}

Eine nichtdeterministische TM $M$ heißt \emph{linear beschränkt\index{linear beschraenkt}},
wenn für alle $a_{1}a_{2}\ldots a_{n-1}a_{n}\in\Sigma^{+}$ und alle
Konfigurationen $\alpha z\beta$ mit $z_{0}a_{1}a_{2}\ldots a_{n-1}\hat{a_{n}}\vdash^{*}\alpha z\beta$
folgendes gilt: $\left|\alpha\beta\right|=n$.

Hierbei ist $\Sigma'=\Sigma\cup\left\{ \hat{a}|a\in\Sigma\right\} $
(Alphabet um modifizierte Symbole ergänzt)

$T\left(M\right)=\left\{ a_{1}a_{2}\ldots a_{n-1}a_{n}\in\Sigma^{*}|z_{0}a_{1}\ldots a_{n-1}\hat{a}_{n}\vdash^{*}\alpha z\beta\left(\alpha,\beta\in\Gamma^{*},z\in E\right)\right\} $

Informal bedeutet dies, das der TM nur ein Band der Länge $n$ zurverfügung
steht, und alle Berechnungen auf diesem Durchgeführt werden. Dazu
muss Das letzte Zeichen auf dem Band markiert werden, damit die Maschine
das Ende erkennt. Das erste Zeichen ist wird als erstes beim Start
gekennzeichnet, da die Maschine hier beginnt.

\begin{itemize}
\item Die von linear beschränkten, nichtdeterministischen TMen (LBA\index{LBA}s)
akzeptierten Sprachen sind genau die kontextsensitiven Sprachen.
\end{itemize}

\subsection{Umwandlung TM in Grammatik und umgekehrt \textsf{\textmd{\small 84}}}

Siehe hierzu im Skript.


\subsection{Abschlusseigenschaften \textsf{\textmd{\small 86}}}

Die Klasse der Kontextsensitiven Sprachen ist unter Komplementbildung
abgeschlossen.

Überblick über Sprachen und dazugehörige Werkzeuge \textsf{\small 88}{\small \par}


\section{Überblick über Sprachen und dazugehörige Werkzeuge \textsf{\textmd{\small 88}}}


\subsection{Beschreibungsmittel\index{Beschreibungsmittel} \textsf{\textmd{\small 89}}}

\begin{tabular}{|c||c|}
\hline 
Typ 3&
reguläre Grammatik, DFA, NFA, reguläre Ausdrücke\tabularnewline
\hline 
det. kontextfrei&
$LR\left(k\right)$- Grammatik\tabularnewline
\hline 
Typ 2&
kontextfreie Grammatik, Kellerautomat (PDA)\tabularnewline
\hline 
Typ 1&
kontextsensitive Grammatik, linear beschränkter Automat (LBA)\tabularnewline
\hline 
Typ 0&
Typ 0 - Grammatik, Turingmaschine (TM)\tabularnewline
\hline
\end{tabular}


\subsection{(Nicht)Determinismus\index{Determinismus}\index{Nichtdeterminismus}
\textsf{\textmd{\small 89}}}

\begin{tabular}{|c|c|c|}
\hline 
Nichtdet. Automat&
Determ. Automat&
äquivalent?\tabularnewline
\hline
\hline 
NFA&
DFA&
ja\tabularnewline
\hline 
PDA&
DPDA&
nein\tabularnewline
\hline 
LBA&
DLBA&
?\tabularnewline
\hline 
TM&
DTM&
ja\tabularnewline
\hline
\end{tabular}


\subsection{Abschlusseigenschaften\index{Abschlusseigenschaften} \textsf{\textmd{\small 89}}}

\begin{tabular}{|c||c|c|c|c|c|}
\hline 
&
Schnitt\index{Schnitt}&
Vereinigung\index{Vereinigung}&
Komplement\index{Komplement}&
Produkt\index{Produkt}&
Stern\index{Stern}\tabularnewline
\hline
\hline 
Typ 3&
ja&
ja&
ja&
ja&
ja\tabularnewline
\hline 
Det. kf.&
nein&
nein&
ja&
nein&
nein\tabularnewline
\hline 
Typ 2&
nein&
ja&
nein&
ja&
ja\tabularnewline
\hline 
Typ 1&
ja&
ja&
ja&
ja&
ja\tabularnewline
\hline 
Typ 0&
ja&
ja&
nein&
ja&
ja\tabularnewline
\hline
\end{tabular}


\subsection{Entscheidbarkeit\index{Entscheidbarkeit} \textsf{\textmd{\small 90}}}

\begin{tabular}{|c||c|c|c|c|}
\hline 
&
Wortproblem\index{Wortproblem}&
Leerheitsproblem\index{Leerheitsproblem}&
Äquivalenzproblem\index{Aequivalenzproblem}&
Schnittproblem\index{Schnittproblem}\tabularnewline
\hline
\hline 
Typ 3&
ja mit $O\left(n\right)$&
ja&
ja&
ja\tabularnewline
\hline 
Det. kf.&
ja mit $O\left(n\right)$&
ja&
ja&
nein\tabularnewline
\hline 
Typ 2&
ja mit $O\left(n^{3}\right)$&
ja&
nein&
nein\tabularnewline
\hline 
Typ 1&
ja mit $O\left(c^{n}\right)$&
nein&
nein&
nein\tabularnewline
\hline 
Typ 0&
nein&
nein&
nein&
nein\tabularnewline
\hline
\end{tabular}

\printindex{}
\end{document}
