%% 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{} \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)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}