#LyX 1.3 created this file. For more info see http://www.lyx.org/ \lyxformat 221 \textclass article \begin_preamble \usepackage{hyperref} \hypersetup { pdftex=true, hyperindex=true, colorlinks=true, bookmarks=true, bookmarksnumbered=false, pdfpagemode=None, bookmarksopen=false, pdfstartview=FitH, pdftitle=Vorlesungsmodul Automaten und formale Sprachen, pdfauthor=Matthias Ansorg, pdfcreator=pdfTeX (Web2C 7.3.1) 3.14159-0.13d } \renewcommand\familydefault{\sfdefault} \end_preamble \language ngerman \inputencoding auto \fontscheme default \graphics default \paperfontsize default \spacing single \papersize a4paper \paperpackage a4wide \use_geometry 0 \use_amsmath 0 \use_natbib 0 \use_numerical_citations 0 \paperorientation portrait \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Title \lang german Vorlesungsmodul Automaten und formale Sprachen \newline - VorlMod AtmFrmSpr - \layout Author \lang german Matthias Ansorg \layout Date \lang german 16. September 2005 bis \begin_inset ERT status Collapsed \layout Standard \backslash today \end_inset \layout Abstract \lang german Studentische Mitschrift zur Vorlesung Automaten und formale Sprachen (Modulnumme r IS006 nach PO 2002) bei Prof. Dr. Ernst Kausen (Sommersemester 2005) im Studiengang Informatik an der Fachhochsch ule Gießen-Friedberg. Anrechnung nach PO 1991 als \begin_inset Quotes ald \end_inset Theoretische Informatik (Automaten und formale Sprachen) \begin_inset Quotes ard \end_inset (Wahlpflichtmodul im Schwerpunkt Systemtechnik) oder \begin_inset Quotes ald \end_inset Mathematische Verfahren für Informatik (Automaten und formale Sprachen) \begin_inset Quotes ard \end_inset (Wahlpflichtmodul im Schwerpunkt Technisch-Wissenschaftliche Anwendungen. Anrechnung nach PO 2002 als Schwerpunktmodul für einen beliebigen Schwerpunkt. Es scheint dass Prof. Kausen diese Veranstaltung zum ersten Mal angeboten hat, denn es gibt noch keine alten Klausuren. Es gibt also wohl auch noch keine studentischen Mitschriften, aber vermutlich bietet \begin_inset LatexCommand \cite{Sipser} \end_inset genügend Hilfen. Die Gliederung dieser Mitschrift ist identisch zur Gliederung dieses Buches; der Stoff der Veranstaltung überdeckt sich dabei mit der Einführung und Teil\SpecialChar ~ 1 dieses Buches. \begin_deeper \layout Itemize \series bold \lang german Bezugsquelle: \series default Die vorliegende studentische Mitschrift steht im Internet zum Download bereit. Quelle: \begin_inset LatexCommand \url[Persönliche Homepage Matthias Ansorg]{http://matthias.ansorgs.de/} \end_inset \layout Itemize \series bold \lang german Lizenz: \series default Diese studentische Mitschrift ist public domain, darf also ohne Einschränkungen oder Quellenangabe für jeden beliebigen Zweck benutzt werden, kommerziell und nichtkommerziell; jedoch enthält sie keinerlei Garantien für Richtigkeit oder Eignung oder sonst irgendetwas, weder explizit noch implizit. Das Risiko der Nutzung dieser studentischen Mitschrift liegt allein beim Nutzer selbst. Einschränkend sind außerdem die Urheberrechte der angegebenen Quellen zu beachten. \layout Itemize \series bold \lang german Korrekturen und Feedback: \series default Fehler zur Verbesserung in zukünftigen Versionen, sonstige Verbesserungsvorschl äge und Wünsche bitte dem Autor per e-mail mitteilen: Matthias Ansorg < \begin_inset LatexCommand \url{mailto:matthias@ansorgs.de} \end_inset \layout Itemize \series bold \lang german Format: \series default Die vorliegende studentische Mitschrift wurde mit dem Programm LyX (graphisches Frontend zu \begin_inset ERT status Collapsed \layout Standard \backslash LaTeX \end_inset ) unter Linux geschrieben und mit pdf \begin_inset ERT status Collapsed \layout Standard \backslash LaTeX \end_inset als pdf-Datei erstellt. Grafiken wurden mit dem Programm xfig unter Linux erstellt und als pdf-Dateien exportiert. \layout Itemize \series bold \lang german Dozent: \series default Prof. Dr. Ernst Kausen. \layout Itemize \series bold \lang german Verwendete Quellen: \series default {}. \layout Itemize \series bold \lang german Klausur: \begin_deeper \layout Itemize \lang german Dauer 90 Minuten. \layout Itemize \lang german Es sind keine Prüfungsvorleistungen notwendig; an der Klausur darf auch teilnehmen, wer die Vorlesung nicht besucht hat. \layout Itemize \lang german Die Klausur hat zu Anfang 2-3 sehr leichte Testaufgaben, die man zu mindestens 80% richtig lösen muss damit man besteht. Das soll unnötigen Zeitaufwand für die weitere Korrektur verhindern, der sonst entsteht weil sich etliche zur Klausur angemeldet haben die die Vorlesung nicht besucht haben. Mögliche Testaufgabe: Konstruktion eines DEA zu einer informal gegebenen Sprache \begin_inset Formula $L$ \end_inset \layout Itemize \lang german Hilfsmittel bei Prof. Kausen: erlaubt ist nur ein DIN A4 Blatt, beidseitig handschriftlich beschriebe n. Dies soll eine Formelsammlung für Definitionen und Konstruktionen sein. Deshalb kommen natürlich keine Aufgaben vor, in denen nur Definitionen abgefragt werden. \layout Itemize \lang german Hilfsmittel bei Prof. Metz: keine Unterlagen zugelassen. \layout Itemize \lang german Man sollte sich das Skript der Veranstaltung bei Prof. Dr. Kausen kopieren, um in der Klausur dieselbe Notation wie in der Vorlesung verwenden zu können; andernfalls erhält man möglicherweise nicht die volle Punktzahl. Die in der Vorlesung verwendete Notation sollte man mit in die Formelsammlung aufnehmen. \layout Itemize \lang german Die Konstruktionsaufgaben in der Klausur werden von recht einfachen Beispielen (2-3 Zustände) ausgehen, weil größere Beispiele zu viel Zeit brauchen würden. \layout Itemize \lang german Wie bei allen Klausuren meldet man sich zur Klausur \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset ber das Online-System an. Im Notfall kann aber auch jemand mitschreiben, der sich nicht angemeldet hat. \layout Itemize \lang german Prof. Kausen hat angegeben, dass von den Übungsblättern \begin_inset LatexCommand \cite{Kausen-Uebgn} \end_inset r die Klausur zum Sommersemester 2005 die Blätter 1-5 und 7-9 besonders relevant sind. Von Blatt 5 sei besonders Aufgabe 1 wichtig; Aufgabe 2 wurde vom Typ her nicht direkt in der Veranstaltung behandelt. \end_deeper \end_deeper \layout Standard \lang german \begin_inset LatexCommand \tableofcontents{} \end_inset \layout Section \lang german Einfhrung \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Automaten, Berechenbarkeit und Komplexität \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Mathematische Notation und Terminologie \layout Paragraph \lang german Definitionen: Alphabet, Zeichen, Wort, Leerwort \layout Itemize \lang german Ein Alphabet \begin_inset Formula $\Sigma$ \end_inset ist eine endliche, nicht-leere Menge. \layout Itemize \lang german Ein \begin_inset Formula $a\in\Sigma$ \end_inset heißt Zeichen. \layout Itemize \lang german \begin_inset Formula $w=a_{1}a_{2}a_{3}\ldots a_{n}$ \end_inset ist Wort über \begin_inset Formula $\Sigma$ \end_inset \begin_inset Formula $\Leftrightarrow$ \end_inset \begin_inset Formula $a_{i}\in\Sigma$ \end_inset \layout Itemize \lang german \begin_inset Formula $\left|w\right|=n$ \end_inset heißt Länge des Wortes \begin_inset Formula $w$ \end_inset \layout Itemize \lang german \begin_inset Formula $\varepsilon$ \end_inset heißt Leerwort ( \begin_inset Formula $\left|\varepsilon\right|=0$ \end_inset \layout Itemize \lang german \begin_inset Formula $\Sigma^{*}=\left\{ w\mid\textrm{$w$ ist Wort über $\Sigma$}\right\} $ \end_inset \layout Itemize \lang german Jede Teilmenge \begin_inset Formula $L\subset\Sigma^{*}$ \end_inset heißt formale Sprache über \begin_inset Formula $\Sigma$ \end_inset \layout Itemize \lang german Die von einem Automaten erkannte Sprache ist \begin_inset Formula $T\left(A\right)=\left\{ w\in\Sigma^{*}\mid\textrm{$w$ wird akzeptiert}\right\} $ \end_inset \layout Paragraph \lang german Kleene'sche Hülle \layout Standard \lang german Die Kleene'sche Hülle \begin_inset Formula $L^{*}$ \end_inset einer Sprache \begin_inset Formula $L$ \end_inset ist definiert durch \begin_inset Foot collapsed true \layout Standard \lang german \begin_inset LatexCommand \cite[S. 4 (+10)]{KindlerManthey} \end_inset hat an dieser Stelle mehrere Fehler \end_inset \begin_inset Formula \begin{eqnarray*} L^{*} & = & \bigcup_{n=0}^{\infty}L^{i}\\ & = & L^{0}\cup L^{1}\cup L^{2}\cup L^{3}\cup\ldots=\left\{ \varepsilon\right\} \cup L\cup LL\cup LLL\cup\ldots\end{eqnarray*} \end_inset Weiter ist definiert: \begin_inset Formula \begin{eqnarray*} L^{+} & = & \bigcup_{n=1}^{\infty}L^{i}\\ & = & L^{1}\cup L^{2}\cup L^{3}\cup\ldots=L\cup LL\cup LLL\cup\ldots\\ & = & L^{*}\setminus\left\{ \varepsilon\right\} \end{eqnarray*} \end_inset Man beachte, dass es hierbei um eine Sprache \begin_inset Formula $L$ \end_inset geht, nicht um ein Alphabet \begin_inset Formula $\Sigma$ \end_inset Bei Alphabeten gilt, etwas analog: \layout Itemize \lang german \begin_inset Formula $\Sigma^{*}$ \end_inset ist die Menge aller Wörter über dem Alphabet \begin_inset Formula $\Sigma$ \end_inset \layout Itemize \lang german \begin_inset Formula $\Sigma^{+}=\Sigma^{*}\setminus\left\{ \varepsilon\right\} $ \end_inset ist die Menge aller Wörter über dem Alphabet \begin_inset Formula $\Sigma$ \end_inset , die aus endlicher Aneinanderreihung (Konkatenation) von Symbolen aus \begin_inset Formula $\Sigma$ \end_inset gebildet werden können. \layout Standard \lang german So ist eine Sprache \begin_inset Formula $L$ \end_inset zwar das \begin_inset Quotes ald \end_inset semantisch höhere Konstrukt \begin_inset Quotes ard \end_inset , aber nicht die mächtigere Menge: im Allgemeinen ist \begin_inset Formula $L^{*}\subset\Sigma^{*}$ \end_inset wegen der Definition \begin_inset Formula $L\subset\Sigma^{*}$ \end_inset \layout Paragraph \lang german Abzählbarkeit \layout Standard \lang german Es sei \begin_inset Formula $\left|\mathbb{N}\right|=\omega$ \end_inset Warum ist dann aber \begin_inset Formula $\left|\left\{ g:\mathbb{N}\rightarrow\left\{ 0,1\right\} \right\} \right|>\omega$ \end_inset wie in \begin_inset LatexCommand \cite[S. 6 (+10)]{KindlerManthey} \end_inset angegeben? Es ist ja \begin_inset Formula $\left|\left\{ g:\mathbb{N}\rightarrow\left\{ 0,1\right\} \right\} \right|=2^{\left|\mathbb{N}\right|}$ \end_inset für jede natürliche Zahl in der Definitionsmenge \begin_inset Formula $\mathbb{N}$ \end_inset verdoppelt sich die Zahl der möglichen Funktionen, eine Gruppe hat hier den Funktionswert \begin_inset Formula $0$ \end_inset , eine \begin_inset Formula $1$ \end_inset \layout Paragraph \lang german Chomsky-Hierarchie \layout Standard \lang german Die Beziehungen zwischen den einzelnen Typen von Grammatiken in der Chomsky-Hier archie sind echte Inklusionen. In der Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset wurde die Teilmengenbeziehung gezeigt, aber nicht immer die echte Teilmengenbez iehung. Denn ersteres lässt sich einfach zeigen, indem man zeigt dass jede Typ \begin_inset Formula $n$ \end_inset Grammatik auch eine Typ \begin_inset Formula $n-1$ \end_inset Grammatik ist. Letzteres ist aber schwierig zu zeigen, entsprechende Beispiele sind nicht trivial zu finden. \layout Subsection \lang german Definitionen, Theoreme und Beweise \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Beweistypen \layout Standard \lang german \SpecialChar ~ \layout Part \lang german Automaten und formale Sprachen \layout Section \lang german Reguläre Sprachen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Endliche Automaten \layout Paragraph \lang german Definition: Endlicher Automat \layout Standard \lang german Ein Quintupel \begin_inset Formula \[ A=\left(S,\Sigma,\delta,s_{0},F\right)\] \end_inset heißt endlicher Automat \begin_inset Foot collapsed true \layout Standard \lang german \begin_inset Formula $EA=NEA\cup DEA$ \end_inset \end_inset wenn gilt: \layout Itemize \lang german Die Übergangsfunktion \begin_inset Formula $\delta$ \end_inset ist \begin_inset Formula $\delta:\; S\times\left(\Sigma\cup\left\{ \varepsilon\right\} \right)\rightarrow p\left(S\right)$ \end_inset Dabei ist \begin_inset Formula $p\left(S\right)=\left\{ M\mid M\subset S\right\} $ \end_inset die Potenzmenge von \begin_inset Formula $S$ \end_inset \layout Standard \lang german Wenn man einschränkt auf \begin_inset Formula $\delta:\; S\times\Sigma\rightarrow S$ \end_inset ist der Automat ein deterministischer endlicher Automat. \begin_inset Formula $\delta$ \end_inset kann bei NEAs und DEAs durch folgende rekursive Definition auf Eingabeworte erweitert werden - sie werden von links nach rechts \begin_inset Quotes ald \end_inset abgearbeitet \begin_inset Quotes ard \end_inset Es sei \begin_inset Formula $s\in S$ \end_inset \begin_inset Formula $a\in\Sigma$ \end_inset \begin_inset Formula $w\in\Sigma^{*}$ \end_inset \begin_inset Formula \begin{eqnarray*} \delta\left(s,\varepsilon\right) & = & s\\ \delta\left(s,aw\right) & = & \delta\left(\underbrace{\delta\left(s,a\right)}_{s'},w\right)\end{eqnarray*} \end_inset \layout Paragraph \lang german Pfade durch einen endlichen Automaten \layout Standard \lang german Notation für Pfade durch einen endlichen Automaten (f \begin_inset Formula $w\in\Sigma^{*}$ \end_inset \begin_inset Formula $s_{i}\in S$ \end_inset \begin_inset Formula \begin{eqnarray*} s_{1}\stackrel{w}{\longrightarrow}s_{2} & \;:\Leftrightarrow\; & \delta\left(s_{1},w\right)=s_{2}\\ s_{1}\longrightarrow s_{2} & \;:\Leftrightarrow\; & \exists w\in\Sigma^{*}:\: s_{1}\stackrel{w}{\longrightarrow}s_{2}\end{eqnarray*} \end_inset \layout Paragraph \lang german Deterministischer endlicher Automat \layout Standard \lang german Die Übergangsrelation \begin_inset Formula $\delta$ \end_inset ist allgemein \begin_inset Formula $\delta\subseteq S\times\Sigma^{*}\times S$ \end_inset Bei deterministischen Automaten kann man \begin_inset Formula $\delta$ \end_inset statt als Relation auch als Abbildung (Funktion) formalisieren: \begin_inset Formula $\delta:S\times\Sigma\rightarrow S$ \end_inset Man nennt \begin_inset Formula $\delta$ \end_inset dann auch Übergangsfunktion. Ist der Automat vollständig, so ist es eine totale Abbildung ( \begin_inset Formula $\mathbb{D}=S\times\Sigma$ \end_inset ), ansonsten eine partielle ( \begin_inset Formula $\mathbb{D}\subset S\times\Sigma$ \end_inset Diese alternativen Formalisierungen sind nicht verwunderlich, da jede Funktion eine spezielle Relation ist: eine Relation \begin_inset Formula $R$ \end_inset für die gilt \begin_inset Formula $\left(p,r\right)\in R,\:\left(q,s\right)\in R,\: r\neq s\Rightarrow p\neq q$ \end_inset ist eine Funktion. Auch die Schreibweise \begin_inset Formula $p\rightarrow q$ \end_inset \begin_inset Formula $\left(p,q\right)\in\rightarrow$ \end_inset bei einer Relation \begin_inset Formula $\rightarrow\subseteq A\times A$ \end_inset zeigt schon die Verwandtschaft zwischen Funktionen und Relationen. \layout Standard \lang german Ein DEA ist ein endlicher Automat, der buchstabierend ist, genau einen Startzust and besitzt und bei dem \begin_inset Formula $\delta$ \end_inset eine Funktion ist. Ein DEA muss also nicht vollständig sein. \layout Paragraph \lang german Nichtdeterministischer endlicher Automat \layout Standard \lang german Ein nichtdeterministischer endlicher Automat (NEA) wird formalisiert als \begin_inset Formula $5$ \end_inset -Tupel \begin_inset Formula $\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset Statt der Menge \begin_inset Formula $F$ \end_inset der Finalzustände kann man auch fordern, dass ein NEA genau einen Finalzustand \begin_inset Formula $f$ \end_inset haben muss. Jeder NEA lässt sich entsprechend transformieren, indem man \begin_inset Formula $\varepsilon$ \end_inset Übergänge von allen bisherigen Finalzuständen zum neu eingeführten Finalzustand \begin_inset Formula $f$ \end_inset einführt. \begin_inset Formula $\varepsilon$ \end_inset Übergänge erlauben Spontanübergänge. \layout Standard \lang german Um zu prüfen ob ein NEA ein Wort akzeptiert, muss man alle vom Startzustand zur gegebenen Eingabe möglichen Pfade gleichzeitig verfolgen und dabei insbesondere auch Spontanübergänge berücksichtigen. Geschickt ist es dabei, diese möglichen Pfade durch den Automaten als verzweigt en Graphen zu notieren. Erreicht man auf einem der Pfade einen Endzustand, ist es nicht mehr notwendig für die restlichen Pfade zu notieren ob auf ihnen ein Endzustand erreicht werden kann. \layout Paragraph \lang german Operationen auf Sprachen \layout Standard \lang german Eine Operation hat die \begin_inset Quotes ald \end_inset Abschlusseigenschaft \begin_inset Quotes ard \end_inset , wenn ihr Ergebnis Element derselben mathematischen Struktur ist. Welche Operationen auf von endlichen Automaten erkannten Sprachen haben die Abschlusseigenschaft, d.h. werden wieder von endlichen Automaten erkannt? Nach \begin_inset LatexCommand \cite[S. 22-23 (+10)]{KindlerManthey} \end_inset sind das die folgenden, sog. \begin_inset Quotes ald \end_inset regul \begin_inset Quotes ard \end_inset Operationen: \layout Description \lang german Schnittmenge \begin_inset Formula \[ L_{1}\cap L_{2}\] \end_inset \layout Description \lang german Vereinigungsmenge \begin_inset Formula \[ L_{1}+L_{2}=L_{1}\cup L_{2}\] \end_inset \layout Description \lang german Komplementbildung \begin_inset Formula \[ \overline{L}=\Sigma^{*}\setminus L\] \end_inset \layout Description \lang german Konkatenation \begin_inset Formula \[ L_{1}L_{2}=L_{1}\circ L_{2}=\left\{ vw\mid v\in L_{1},w\in L_{2}\right\} \] \end_inset \begin_inset Formula $L=L_{1}=L_{2}$ \end_inset entsteht der Spezialfall \begin_inset Formula $L_{1}L_{2}=L^{2}$ \end_inset bzw. bei mehrfacher Anwendung allgemeiner \begin_inset Formula $L^{n}$ \end_inset \layout Description \lang german Kleene'sche\SpecialChar ~ Hülle \begin_inset Formula \begin{eqnarray*} L^{*} & = & \bigcup_{i\in\mathbb{N}_{0}}L^{i}\\ & = & L^{0}\cup L^{1}\cup L^{2}\cup L^{3}\cup\ldots=\left\{ \varepsilon\right\} \cup L\cup LL\cup LLL\cup\ldots\end{eqnarray*} \end_inset \layout Standard \lang german Daneben gibt es weitere Operationen auf Sprachen ( \begin_inset LatexCommand \cite[S. 24 (+10)]{KindlerManthey} \end_inset \begin_inset LatexCommand \cite[S. 35ff (+10)]{KindlerManthey} \end_inset ), die jedoch in dieser Veranstaltung nicht behandelt wurden: \layout Itemize \lang german Homomorphismen \layout Itemize \lang german inverse Homomorphismen \layout Itemize \lang german Substitution \layout Itemize \lang german Quotient \layout Itemize \lang german Spiegelung \layout Paragraph \lang german Algorithmus zur Konstruktion eines NEA-quivalenten DEA \begin_inset Foot collapsed true \layout Standard \lang german Dieser Algorithmus ist äquivalent zu dem in der Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset im SS 2005 bei Prof. Dr. Ernst Kausen. Er verwendet jedoch etwas andere Schritte und Schreibweisen (in Anlehnung an \begin_inset LatexCommand \cite[S.18 (+10)]{KindlerManthey} \end_inset ) wo dies zu mehr Klarheit führt. \end_inset \layout Enumerate \lang german Das Zustandsübergangsdiagramm von \begin_inset Formula $A$ \end_inset ist gegeben. \layout Enumerate \lang german Wandle den NEA in einen NEA mit genau einem Startzustand. \layout Enumerate \lang german Mache den NEA alphabetisch. \layout Enumerate \lang german Mache den NEA buchstabierend ( \begin_inset Formula $\varepsilon$ \end_inset -Elimination). \begin_inset Foot collapsed true \layout Standard \lang german Dieser Schritt kann durch Änderungen in der Definition von \begin_inset Formula $A'$ \end_inset äquivalent ersetzt werden (was den Algorithmus jedoch verkompliziert). Dann ist: \begin_inset Formula \begin{eqnarray*} s_{0}' & := & \left\{ s_{0}\right\} \cup\left\{ \delta\left(s_{0},\varepsilon^{k}\right)\mid k\geq1\right\} \\ F' & := & \left\{ R\in S'\mid R\cap\left(F\cup\left\{ \delta\left(s_{f},\varepsilon^{k}\right)\mid s_{f}\in F,\: k\geq1\right\} \right)\neq0\right\} \\ \delta'\left(R,a\right) & := & \left\{ \delta\left(s,\varepsilon^{k}a\varepsilon^{k}\right)\mid s\in R,\: k\geq1\right\} \end{eqnarray*} \end_inset \end_inset \layout Enumerate \lang german Die einzelnen Komponenten von \begin_inset Formula $A=\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset ermitteln und aufschreiben. Dabei \begin_inset Formula $\delta$ \end_inset tabellarisch notieren: Funktionswerte \begin_inset Formula $\delta\left(q,a\right)$ \end_inset befinden sich am Kreuzungspunkt einer Zeile (aktueller Zustand) und einer Spalte (Eingabezeichen). \layout Enumerate \lang german Die einzelnen Komponenten von \begin_inset Formula $A'=\left(S',\Sigma',\delta',s_{0}',F'\right)$ \end_inset ermitteln und aufschreiben: \begin_deeper \layout Itemize \lang german \begin_inset Formula $S':=\mathcal{P}\left(S\right)=\left\{ M\mid M\subset S\right\} $ \end_inset Beachte \begin_inset Formula $\emptyset\in S'$ \end_inset \layout Itemize \lang german \begin_inset Formula $\Sigma':=\Sigma$ \end_inset \layout Itemize \lang german \begin_inset Formula $s_{0}':=\left\{ s_{0}\right\} $ \end_inset \layout Itemize \lang german \begin_inset Formula $F':=\left\{ R\in S'\mid R\cap F\neq\emptyset\right\} $ \end_inset \layout Itemize \lang german \begin_inset Formula $\delta':\; S'\times\Sigma\rightarrow S',\quad\delta'\left(R,a\right):=\left\{ \delta\left(s,a\right)\mid s\in R\right\} $ \end_inset \begin_inset Foot collapsed true \layout Standard \lang german Achtung: hier wurden \begin_inset Formula $\delta$ \end_inset und \begin_inset Formula $\delta'$ \end_inset als Funktionen formalisiert und nicht wie sonst manchmal als Relationen. \end_inset In Worten: man bilde einen Folgezustand \begin_inset Formula $R'=\delta'\left(R,a\right)$ \end_inset in \begin_inset Formula $A'$ \end_inset als Menge der Folgezustände \begin_inset Formula $\delta\left(s,a\right)$ \end_inset aller \begin_inset Formula $s\in R$ \end_inset in \begin_inset Formula $A$ \end_inset \begin_deeper \layout Itemize \lang german \begin_inset Formula $\delta'$ \end_inset notiere man tabellarisch wie schon \begin_inset Formula $\delta$ \end_inset und führe dabei zur Übersichtlichkeit neue Namen für die \begin_inset Formula $R\in S'$ \end_inset ein. Zum Beispiel: \begin_inset Formula $\left\{ s_{0},s_{1},s_{3}\right\} =s_{013}'$ \end_inset \layout Itemize \lang german Die Folgezustände einelementiger \begin_inset Formula $R\in S'$ \end_inset lassen sich direkt aus der tabellarischen Notation von \begin_inset Formula $\delta$ \end_inset ablesen. \layout Itemize \lang german Die restlichen Folgezustände ergeben sich durch Vereinigungsmengen mehrere Folgezustände einelementiger \begin_inset Formula $R\in S'$ \end_inset \layout Itemize \lang german Wenn man in der Tabelle für \begin_inset Formula $\delta'$ \end_inset zuerst nur die Zustände einelementiger \begin_inset Formula $R\in S'$ \end_inset als Ausgangszustände (linke Spalte) notiert und dort nur noch solche ergänzt, in die diese Ausgangszustände übergehen, ergibt sich schon sofort der Minimalau tomat. \end_deeper \layout Itemize \lang german Damit ist \begin_inset Formula $\delta'\left(R,a\right)$ \end_inset das \begin_inset Formula $R'\in S'$ \end_inset , das aus all den \begin_inset Formula $s\in S$ \end_inset besteht die in \begin_inset Formula $A$ \end_inset von einem \begin_inset Formula $r\in R$ \end_inset aus durch Eingabe von \begin_inset Formula $a$ \end_inset erreichbar sind. \end_deeper \layout Enumerate \lang german Das Zustandsübergangsdiagramm von \begin_inset Formula $A'$ \end_inset zeichnen. \layout Enumerate \lang german Vollständiger DEA oder Minimalautomat? Wenn bei der Konstruktion von \begin_inset Formula $\delta'$ \end_inset der Automat nicht minimiert wurde, ist der DEA nun ein vollständiger DEA. Aber auch jetzt noch kann der Minimalautomat erstellt werden. Dazu alle Zustände eliminieren, die vom Startzustand \begin_inset Formula $s_{0}'$ \end_inset nicht erreicht werden können. \layout Paragraph \lang german Reduzierter endlicher Automat \layout Standard \lang german Sei ein deterministischer endlicher Automat \begin_inset Formula $A=\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset Sei \begin_inset Formula $~$ \end_inset eine quivalenzrelation \begin_inset Formula $~$ \end_inset \begin_inset Formula $s,s'\in S$ \end_inset mit \begin_inset Formula $s~s':\Leftrightarrow\forall w\in\Sigma^{*}:\:\delta\left(s,w\right)\in F\Leftrightarrow\delta\left(s',w\right)\in F$ \end_inset \begin_inset Formula $A$ \end_inset heißt reduzierter endlicher Automat \begin_inset Formula $:\Leftrightarrow$ \end_inset \begin_inset Formula $\forall s,s'\in S:\: s~s'\Rightarrow s=s'$ \end_inset In Worten: man kann von einem beliebigen Zustand jeweils nur einen Endzustand erreichen, unabhängig vom Eingabewort. \layout Paragraph \lang german äquivalenter reduzierter endlicher Automat \layout Standard \lang german Sei ein Automat \begin_inset Formula $A=\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset und eine Funktion \begin_inset Formula $B\left(s\right)=\left\{ s'\in S\mid s~s'\right\} $ \end_inset \begin_inset Foot collapsed true \layout Standard \lang german Es ist \begin_inset Formula $B\left(s\right)=\left[s\right]_{~}$ \end_inset , d.h. \begin_inset Formula $B\left(s\right)$ \end_inset ermittelt zu einem \begin_inset Formula $s$ \end_inset seine Äquivalenzklasse unter \begin_inset Formula $~$ \end_inset \end_inset Dann ist der reduzierte endliche Automat \begin_inset Formula $A'$ \end_inset mit \begin_inset Formula $T\left(A\right)=T\left(A'\right)$ \end_inset \begin_inset Formula \begin{eqnarray*} A' & = & \left(S',\Sigma,\delta',s_{0}',F'\right)\\ S' & = & \left\{ B\left(s\right)\mid s\in S\right\} \\ s_{0}' & = & B\left(s_{0}\right)\\ F' & = & \left\{ B\left(s\right)\mid s\in F\right\} \\ \delta'\left(B\left(s\right),a\right) & = & B\left(\delta\left(s,a\right)\right)\end{eqnarray*} \end_inset Erklärung zur Definition für \begin_inset Formula $\delta'$ \end_inset Üblicherweise würde man definieren \begin_inset Formula $\delta'\left(B\left(s\right),a\right)=\left\{ \delta\left(t,a\right)\mid t\in B\left(s\right)\right\} $ \end_inset Nun gilt aber \begin_inset Formula $s~s'\Leftrightarrow\delta\left(s,a\right)~\delta\left(s',a\right)$ \end_inset \begin_inset Foot collapsed true \layout Standard \lang german Beweisbar ist durch Induktion über die Definition der Äquivalenzrelation \begin_inset Formula $~$ \end_inset \end_inset : sind zwei Zustände äquivalent, so sind auch ihre Folgezustände äquivalent. Weil alle \begin_inset Formula $t\in B\left(s\right)$ \end_inset per Definition äquivalent sind, sind also auch alle Folgezustände \begin_inset Formula $\delta\left(t,a\right)\mid t\in B\left(s\right)$ \end_inset äquivalent und sind zu ermitteln als Äquivalenzklasse zu einem Folgezustand \begin_inset Formula $\delta\left(s,a\right)$ \end_inset So erhält man obige Definition: \begin_inset Formula \[ \delta'\left(B\left(s\right),a\right)=\left\{ \delta\left(t,a\right)\mid t\in B\left(s\right)\right\} =B\left(\delta\left(s,a\right)\right)\] \end_inset \layout Paragraph \lang german Konstruktion des äquivalenten reduzierten endlichen Automaten: state merging method \layout Standard \lang german Idee: \begin_inset Formula $S'$ \end_inset ist die Partition von \begin_inset Formula $S$ \end_inset unter der Äquivalenzrelation \begin_inset Formula $~$ \end_inset Ermittle also immer feinere Partitionen \begin_inset Formula $\Pi_{0}$ \end_inset \begin_inset Formula $\Pi_{1}$ \end_inset \begin_inset Formula $\Pi_{2}$ \end_inset , \SpecialChar \ldots{} bis das Verfahren nicht mehr zu einer feineren Partition führt: \begin_inset Formula $\Pi_{k}=\Pi_{k+1}=S'$ \end_inset Das Verfahren ist: \layout Enumerate \lang german Basispartition \begin_inset Formula $\Pi_{0}=\left\{ F,S\setminus F\right\} =\left\{ S_{01},S_{02}\right\} $ \end_inset Sie \begin_inset Formula $S_{i}\in\Pi_{0}$ \end_inset heißen Blöcke. \layout Enumerate \lang german Blockteilung: untersuche für jeden Block \begin_inset Formula $B$ \end_inset und jedes Eingabesymbol \begin_inset Formula $a\in\Sigma$ \end_inset , ob die \begin_inset Formula $\delta\left(s,a\right)$ \end_inset im selben Zielblock landen \begin_inset Foot collapsed true \layout Standard \lang german Dies ist gefordert durch \begin_inset Formula $s~s'\Leftrightarrow\delta\left(s,a\right)~\delta\left(s',a\right)$ \end_inset für den Fall dass Block \begin_inset Formula $B$ \end_inset tatsächlich nur äquivalente Zustände enthält \end_inset Falls nicht, muss \begin_inset Formula $B$ \end_inset entsprechend aufgeteilt werden und es ergibt sich die feinere Partition \begin_inset Formula $\Pi_{1}=\left\{ S_{11},S_{12},\ldots,S_{1n_{1}}\right\} $ \end_inset \layout Enumerate \lang german Wiederhole Schritt 2 bis \begin_inset Formula $\Pi_{k}=\Pi_{k+1}=:S'$ \end_inset \layout Subsection \lang german Nichtdeterminiertheit \layout Standard \lang german Die \begin_inset Quotes ald \end_inset Determiniertheit \begin_inset Quotes ard \end_inset des DEA zeigt sich darin, dass zu einem Tupel \begin_inset Formula $a\in S\times\Sigma$ \end_inset genau ein Folgezustand \begin_inset Formula $S$ \end_inset existiert - der Folgezustand ist damit eindeutig bestimmt, \begin_inset Quotes ald \end_inset determiniert \begin_inset Quotes ard \end_inset Und \begin_inset Formula $\delta$ \end_inset ist dann eine echte Funktion. Die \begin_inset Quotes ald \end_inset Nichtdeterminiertheit \begin_inset Quotes ard \end_inset des NEA dagegen besteht darin dass er für einen Zustand bei derselben Eingabe mehrere mögliche Folgezustände erlaubt. Der Folgezustand ist damit nicht durch aktuellen Zustand und Eingabe eindeutig festgelegt, d.h. er ist nicht \begin_inset Quotes ald \end_inset determiniert \begin_inset Quotes ard \end_inset Auch der aktuelle Zustand ist nicht determiniert: der Automat befindet sich im Endzustand des letzten Übergangs oder einem der Zustände, die damit durch \begin_inset Formula $\varepsilon$ \end_inset Übergänge verbunden sind. Der Automat befindet sich in durch \begin_inset Formula $\varepsilon$ \end_inset Übergänge verbundenen Zuständen \begin_inset Quotes ald \end_inset gleichzeitig \begin_inset Quotes ard \end_inset , zumindest logisch gesehen. Erst nach der nächsten Eingabe kann man eingrenzen, in welchen Zuständen der Automat sich zuletzt vor der Eingabe befunden hat. Das erinnert irgendwie an Unschärfe und Nichtdeterminiertheit in der Quantenphy sik. \layout Standard \lang german Nichtdeterminiertheit bei Automaten kann man sich etwas genauer so vorstellen: gibt man dem Automaten ein Wort stückweise als Eingabe, so durchläuft er alle Pfade und deren Folgepfade, die aufgrund der Eingabe denkbar sind, gleichzeitig. Er akzeptiert ein Wort, wenn er auf mindestens einem dieser Pfade einen Endzustand erreicht. Dass die Eingabe \begin_inset Quotes ald \end_inset stückweise \begin_inset Quotes ard \end_inset erfolgt bedeutet, dass man dem Automaten in jedem Schritt alternative Eingaben zur Verfügung stellt: ein Zeichen, zwei Zeichen, drei Zeichen usw. bis zum aktuellen Rest des Wortes. Denn der Automat akzepztiert möglicherweise auch Zeichenketten als Eingaben. \layout Standard \lang german So ist zwar das Ergebnis des Automaten determiniert ( \begin_inset Quotes ald \end_inset akzeptiert \begin_inset Quotes ard \end_inset oder \begin_inset Quotes ald \end_inset nicht akzeptiert \begin_inset Quotes ard \end_inset ) und auch reproduzierbar. Aber der Weg zu diesem Ergebnis ist nicht determiniert, es werden alle möglichen Wege gleichzeitig verfolgt. \layout Subsection \lang german Reguläre Ausdrücke \layout Paragraph \lang german Äquivalenz mit rechtslinearen Grammatiken \layout Standard \lang german Reguläre Sprachen können äquivalent durch endliche Automaten, reguläre Ausdrü oder reguläre Grammatiken charakterisiert werden. Eine Grammatik \begin_inset Formula $G=\left(V,\Sigma,P,S\right)$ \end_inset heißt rechtslinear, wenn jede Produktion eine der folgenden Formen hat (mit \begin_inset Formula $A,B\in V$ \end_inset \begin_inset Formula $w\in\Sigma^{*}$ \end_inset \layout Standard \lang german \begin_inset Formula \begin{eqnarray*} A & \rightarrow & wB\\ A & \rightarrow & w\end{eqnarray*} \end_inset Will man mit rechtslinearen Grammatiken auch das Leerwort \begin_inset Formula $\varepsilon$ \end_inset erzeugen können, sind ein paar Erweiterungen nötig. Rechtslineare und (analog definierte) linkslineare Grammatiken fasst man zur Klasse der regulären Grammatiken zusammen (das sind Chomsky Typ\SpecialChar ~ 3-Grammatike n Rechtslineare und linkslineare Grammatiken charakterisieren beide die regulären Sprachen, da diese Sprachklasse unter Spiegelung abgeschlossen ist. \layout Paragraph \lang german Axiome zum Rechnen mit formaler Sprache \layout Standard \lang german Seien \begin_inset Formula $L,R,S,T\subset\Sigma^{*}$ \end_inset \layout Standard \lang german \begin_inset Formula \begin{eqnarray*} L+L & = & L\\ L+\emptyset & = & L\\ R+S & = & S+R\\ \left(R+S\right)+T & = & R+\left(S+T\right)=R+S+T\\ \left(RS\right)T & = & R\left(ST\right)\\ R\left\{ \varepsilon\right\} & = & \left\{ \varepsilon\right\} R=R\\ R\emptyset & = & \emptyset R=\emptyset\\ R\left(S+T\right) & = & \left(RS\right)+\left(RT\right)=RS+RT\\ L^{*}L^{*} & = & L^{*}\\ \left(L^{*}\right)^{*} & = & L^{*}\end{eqnarray*} \end_inset \layout Paragraph \lang german Axiome zum Rechnen mit regulären Ausdrücken \layout Standard \lang german Diese Axiome sind äquivalent zu den Axiomen zum Rechnen mit formaler Sprache. In \begin_inset LatexCommand \cite[S.29 (+10)]{KindlerManthey} \end_inset finden sich folgende 14 Axiome zum Rechnen mit regulären Ausdrücken, hier mit Anmerkungen zum Verständnis: \layout Standard \lang german \begin_inset Formula \begin{equation} \varepsilon=\emptyset^{*}\label{eq:RegExpAxiom_0-0}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r=r\label{eq:RegExpAxiom_0-1}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r+\emptyset=r\label{eq:RegExpAxiom_0-2}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r+r=r\label{eq:RegExpAxiom_0-3}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} \left(r+s\right)+t=r+\left(s+t\right)\label{eq:RegExpAxiom_1}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} \left(rs\right)t=r\left(st\right)\label{eq:RegExpAxiom_2}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r+s=s+r\label{eq:RegExpAxiom_3}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r\left(s+t\right)=rs+rt\label{eq:RegExpAxiom_4}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} \left(r+s\right)t=rt+st\label{eq:RegExpAxiom_5}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r\varepsilon=r\label{eq:RegExpAxiom_6}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r\emptyset=\emptyset\label{eq:RegExpAxiom_7}\end{equation} \end_inset Verständnis: \begin_inset Formula $\emptyset$ \end_inset ist ein regulärer Ausdruck, der keine Eingaben akzeptiert, auch nicht \begin_inset Formula $\varepsilon$ \end_inset (den \begin_inset Quotes ald \end_inset leeren String \begin_inset Quotes ard \end_inset Die Konkatenation \begin_inset Formula $r\emptyset$ \end_inset muss diese Anforderung \begin_inset Quotes ald \end_inset nichts akzeptieren \begin_inset Quotes ard \end_inset erfüllen, und damit ist der Teil \begin_inset Formula $r$ \end_inset llig unerheblich für das, was \begin_inset Formula $r\emptyset$ \end_inset akzeptiert. Diese Tatsache wird durch \begin_inset Formula $r\emptyset=\emptyset$ \end_inset ausgedrückt. \layout Standard \lang german \begin_inset Formula \begin{equation} r^{*}=rr^{*}+\varepsilon\label{eq:RegExpAxiom_8}\end{equation} \end_inset \layout Standard \lang german \begin_inset Formula \begin{equation} r^{*}=\left(r+\varepsilon\right)^{*}\label{eq:RegExpAxiom_9}\end{equation} \end_inset Zwei weitere Axiome sind praktisch, aber zur Vollständigkeit entbehrlich: \begin_inset Formula \[ r^{*}r^{*}=r^{*}\] \end_inset \begin_inset Formula \[ \left(r^{*}\right)^{*}=r^{*}\] \end_inset \layout Paragraph \lang german Rechenregel \begin_inset Quotes ald \end_inset Gleichungsauflösung \begin_inset Quotes ard \end_inset für reguläre Ausdrücke \layout Standard \lang german \begin_inset LatexCommand \cite[S.30 (+10)]{KindlerManthey} \end_inset wird sie so formuliert: \begin_inset Quotes ald \end_inset Wenn die Gleichung \begin_inset Formula $r=sr+t$ \end_inset gilt und \begin_inset Formula $s$ \end_inset die Leerworteigenschaft \emph on nicht \emph default erfüllt, dann gilt auch die Gleichung \begin_inset Formula $r=s^{*}t$ \end_inset \begin_inset Quotes ard \end_inset Unter der Nebenbedingung, dass \begin_inset Formula $s$ \end_inset die Leerworteigenschaft nicht erfüllt, wird also \begin_inset Formula $r=s^{*}t$ \end_inset als einzige Lösung der Gleichung \begin_inset Formula $r=sr+t$ \end_inset angesehen. Die Probe zeigt, dass es tatsächlich eine Lösung ist: setze \begin_inset Formula $r=s^{*}t$ \end_inset ein in \begin_inset Formula $r=sr+t$ \end_inset \begin_inset Formula \[ s^{*}t\stackrel{!}{=}s\left(s^{*}t\right)+t\] \end_inset Mit Gleichung \begin_inset LatexCommand \ref{eq:RegExpAxiom_8} \end_inset gilt: \begin_inset Formula \[ s^{*}t=\left(ss^{*}+\varepsilon\right)t\] \end_inset Mit Gleichung \begin_inset LatexCommand \ref{eq:RegExpAxiom_5} \end_inset gilt weiter: \begin_inset Formula \[ s^{*}t=\left(ss^{*}+\varepsilon\right)t=\left(ss^{*}\right)t+\varepsilon t\] \end_inset Und mit Gleichungen \begin_inset LatexCommand \ref{eq:RegExpAxiom_2} \end_inset und \begin_inset LatexCommand \ref{eq:RegExpAxiom_6} \end_inset gilt schlielich wie zu zeigen war: \begin_inset Formula \[ s^{*}t=\left(ss^{*}+\varepsilon\right)t=s\left(s^{*}t\right)+t\] \end_inset \layout Paragraph \lang german Äquivalenzen ausrechnen durch das Rechnen mit regulären Ausdrücken \layout Standard \lang german Mit den Rechenregeln für reguläre Ausdrücke ist es möglich zu zeigen dass zwei reguläre Ausdrücke äquivalent sind, jedoch liefern sie kein effektives Konstruktionsverfahren dazu. Mit den Rechenregeln kann also auch nicht gezeigt werden dass zwei reguläre Ausdrücke nicht quivalent sind \begin_inset LatexCommand \cite[S.31 (+10)]{KindlerManthey} \end_inset Will man durch die Rechenregeln die Äquivalenz zweier regulärer Ausdrücke \begin_inset Formula $r_{1}$ \end_inset und \begin_inset Formula $r_{2}$ \end_inset beweisen, muss man insgesamt einen Term der Form \begin_inset Formula $r_{1}=\ldots=r_{2}$ \end_inset aufstellen, es bietet sich also folgendes Beweisverfahren an (in dem jedoch immer noch eine Beweisidee nötig ist): \layout Enumerate \lang german Schreibe \begin_inset Formula $r_{1}=$ \end_inset auf. \layout Enumerate \lang german Forme \begin_inset Formula $r_{1}$ \end_inset schrittweise durch die Axiome zu einem längeren regulären Ausdruck \begin_inset Formula $r_{1}'$ \end_inset um. \layout Enumerate \lang german Fasse \begin_inset Formula $r_{1}'$ \end_inset schrittweise durch die Axiome zum kürzeren regulären Ausdruck \begin_inset Formula $r_{2}$ \end_inset zusammen. \layout Paragraph \lang german Erzeugte reguläre Sprache zu einem regulären Ausdruck ermitteln \layout Standard \lang german Das Prinzip ist, die Operationen im regulären Ausdruck von außen nach innen in die gleichlautenden Operationen auf regulären Sprachen umzuformen. An Beispielen: \begin_inset Formula \[ L\left(a\left(b+c\right)\right)=L\left(a\right)L\left(b+c\right)=L\left(a\right)\left(L\left(b\right)+L\left(c\right)\right)=\left\{ a\right\} \left(\left\{ b\right\} \cup\left\{ c\right\} \right)=\left\{ a\right\} \times\left\{ b,c\right\} =\left\{ ab,ac\right\} \] \end_inset \begin_inset Formula \[ L\left(a^{*}\right)=L\left(a\right)^{*}=\left\{ a\right\} ^{*}=\bigcup_{n=0}^{\infty}\left\{ a^{n}\right\} =\left\{ \varepsilon,a,aa,aaa,aaaa,\ldots\right\} =\left\{ a^{n}\mid n\geq0\right\} \] \end_inset \layout Paragraph \lang german Endlichen Automaten zu einem regulären Ausdruck konvertieren \layout Standard \lang german Das Verfahren folgt der rekursiven Definition der regulären Ausdrücke und beweist den Satz \begin_inset Quotes ald \end_inset \begin_inset Formula $L$ \end_inset regul \begin_inset Formula $\Rightarrow$ \end_inset \begin_inset Formula $\exists$ \end_inset endlicher Automat \begin_inset Formula $A$ \end_inset mit \begin_inset Formula $L=T\left(A\right)$ \end_inset \begin_inset Quotes ard \end_inset Sei nun: \layout Itemize \lang german \begin_inset Formula $a\in\Sigma$ \end_inset \layout Itemize \lang german \begin_inset Formula $A=\left(S_{1},\Sigma,\delta_{1},s_{a},F_{1}\right)$ \end_inset \begin_inset Formula $B=\left(S_{2},\Sigma,\delta_{2},s_{b},F_{2}\right)$ \end_inset \layout Itemize \lang german \begin_inset Formula $\alpha,\beta$ \end_inset sind reguläre Ausdrücke mit \begin_inset Formula $L\left(\alpha\right)=T\left(A\right)$ \end_inset und \begin_inset Formula $L\left(\beta\right)=T\left(B\right)$ \end_inset \layout Standard \lang german Dann gilt: \layout Enumerate \lang german Der endliche Automat zu \begin_inset Formula $L\left(a\right)=\left\{ a\right\} $ \end_inset ist \begin_inset Formula $C=\left(S,\Sigma,\delta,s_{0},F\right)=\left(\left\{ s_{0},s_{f}\right\} ,\left\{ a\right\} ,\delta:\:\delta\left(s_{0},a\right)=s_{f},s_{0},\left\{ s_{f}\right\} \right)$ \end_inset \layout Enumerate \lang german Der endliche Automat zu \begin_inset Formula $L\left(\varepsilon\right)=\left\{ \varepsilon\right\} $ \end_inset ist \begin_inset Formula $C=\left(S,\Sigma,\delta,s_{0},F\right)=\left(\left\{ s_{0}\right\} ,\emptyset,\delta,s_{0},\left\{ s_{0}\right\} \right)$ \end_inset \layout Enumerate \lang german Der endliche Automat zu \begin_inset Formula $L\left(\emptyset\right)=\emptyset$ \end_inset ist \begin_inset Formula $C=\left(S,\Sigma,\delta,s_{0},F\right)=\left(\left\{ s_{0}\right\} ,\emptyset,\delta,s_{0},\emptyset\right)$ \end_inset \layout Enumerate \lang german Der endliche Automat zu \begin_inset Formula $L\left(\alpha+\beta\right)$ \end_inset ist \begin_inset Formula $C=\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset mit \begin_inset Formula \begin{eqnarray*} S & = & S_{1}\cup S_{2}\cup s_{0}\\ F & = & F_{1}\cup F_{2}\\ \delta\left(s,a\right) & = & \left\{ \begin{array}{cc} \delta_{1}\left(s,a\right) & \textrm{f r }s\in S_{1}\\ \delta_{2}\left(s,a\right) & \textrm{f r }s\in S_{2}\\ \left\{ s_{a},s_{b}\right\} & \textrm{f r }s=s_{0},a=\varepsilon\\ \emptyset & \textrm{f r }s=s_{0},a\neq\varepsilon\end{array}\right.\end{eqnarray*} \end_inset \layout Enumerate \lang german Der endliche Automat zu \begin_inset Formula $L\left(\alpha\beta\right)$ \end_inset ist \begin_inset Formula $C=\left(S,\Sigma,s_{a},\delta,F_{2}\right)$ \end_inset mit \begin_inset Formula \begin{eqnarray*} S & = & s_{1}\cup s_{2}\\ \delta\left(s,a\right) & = & \left\{ \begin{array}{cc} \delta_{2}\left(s,a\right) & \textrm{f r }s\in S_{2}\\ \delta_{1}\left(s,a\right) & \textrm{f r }s\in S_{1},s\notin F_{1}\\ \delta_{1}\left(s,a\right)\cup & \textrm{f r }s=s_{0},a=\varepsilon\\ \emptyset & \textrm{f r }s=s_{0},a\neq\varepsilon\end{array}\right.\end{eqnarray*} \end_inset \layout Subsection \lang german Nichtreguläre Sprachen \layout Paragraph \lang german Endlicher Index von \begin_inset Formula $R_{L}$ \end_inset \layout Standard \lang german Der Satz von Myhill und Nerode besagt: Eine Sprache ist genau dann regulär wenn der Index der Relation \begin_inset Formula $R_{L}$ \end_inset endlich ist. Vgl. \begin_inset LatexCommand \cite[S.31 (+10)]{KindlerManthey} \end_inset und \begin_inset LatexCommand \cite[S.33 (+10)]{KindlerManthey} \end_inset In der Veranstaltung bei Prof. Kausen wurde dieser Stoff nicht behandelt. \layout Paragraph \lang german Pumping-Lemma \layout Standard \lang german Das Pumping-Lemma \begin_inset Foot collapsed true \layout Standard \lang german wörtlich bersetzt \begin_inset Quotes ald \end_inset Aufblassatz \begin_inset Quotes ard \end_inset , deutsche Bezeichnung \begin_inset Quotes ald \end_inset \begin_inset Formula $uvw$ \end_inset -Theorem \begin_inset Quotes ard \end_inset \end_inset wird verwendet zum Nachweis dass eine Sprache nicht mehr regulär ist, also zum Test der Regularität \layout Paragraph \lang german Nichtregularität der Sprache der Palindrome \layout Standard \lang german Ein Palindrom ist ein Wort, das vorwärts und rückwärts gelesen gleich lautet \begin_inset LatexCommand \url{http://de.wikipedia.org/wiki/Palindrom} \end_inset In \begin_inset LatexCommand \cite[S.33 (+10)]{KindlerManthey} \end_inset wird bewiesen dass die Sprache \begin_inset Formula $L$ \end_inset der Palindrome über \begin_inset Formula $\Sigma=\left\{ a,b\right\} $ \end_inset nicht regulär ist. Die Idee dabei: \layout Enumerate \lang german Pumping-Lemma fordert, dass für jedes \begin_inset Formula $x\in L$ \end_inset einer regulären Sprache mit \begin_inset Formula $\left|x\right|\geq n$ \end_inset eine Zerlegung \begin_inset Formula $x=uvw$ \end_inset (mit \begin_inset Formula $\left|uv\right|\leq n$ \end_inset \begin_inset Formula $\left|v\right|\geq1$ \end_inset ) existiert so dass \begin_inset Formula $uv^{i}w\in L$ \end_inset für jedes \begin_inset Formula $i\in\mathbb{N}$ \end_inset \layout Enumerate \lang german wähle also geschickt ein konkretes \begin_inset Formula $x\in L$ \end_inset Und wähle eine konkrete Zerlegung \begin_inset Formula $x=uvw$ \end_inset so dass \begin_inset Formula $\left|uv\right|\leq n$ \end_inset \begin_inset Formula $\left|v\right|\geq1$ \end_inset Da \begin_inset Formula $n$ \end_inset (ab dem Pumping-Lemma gilt) i.A. unbekannt ist, wähle ein \begin_inset Formula $x\in L$ \end_inset mit \begin_inset Formula $n$ \end_inset -parametrisierbarer Länge und eine Zerlegung \begin_inset Formula $x=uvw$ \end_inset mit \begin_inset Formula $n$ \end_inset -parametrisierten Längen der Bestandteile so dass \begin_inset Formula $\left|uv\right|\leq n$ \end_inset \begin_inset Formula $\left|v\right|\geq1$ \end_inset erfüllt ist. \layout Enumerate \lang german Wähle ein \begin_inset Formula $i\in\mathbb{N}$ \end_inset so dass \begin_inset Formula $uv^{i}w\notin L$ \end_inset Damit ist die Nichtregularität von \begin_inset Formula $L$ \end_inset nachgewiesen. Oft bietet sich wohl \begin_inset Formula $i=0$ \end_inset an. \layout Section \lang german Kontextfreie Sprachen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Kontextfreie Grammatiken \layout Standard \lang german Die Definition für deterministisch kontextfreie Sprachen lautet: \begin_inset Quotes ald \end_inset Eine kontextfreie Sprache \begin_inset Formula $L$ \end_inset heit deterministisch, wenn es einen deterministischen Kellerautomaten \begin_inset Formula $A$ \end_inset gibt, der die Sprache \begin_inset Formula $L$ \end_inset über Endzustände akzeptiert (d.h. \begin_inset Formula $L=L\left(A\right)$ \end_inset \begin_inset Quotes ard \end_inset \begin_inset LatexCommand \cite[S.90 (+10)]{KindlerManthey} \end_inset Dabei gilt: Es muss ber Akzeptierung ber Endzustände definiert werden, denn eine Definition über Akzeptierung mit leerem Keller wäre echt schwächer - denn die dadurch akzeptierten Sprachen sind präfixfrei \begin_inset LatexCommand \cite[S.90 (+10)]{KindlerManthey} \end_inset Dabei bedeutet \begin_inset Quotes ald \end_inset präfixfrei \begin_inset Quotes ard \end_inset \begin_inset Quotes ald \end_inset Eine Sprache \begin_inset Formula $L$ \end_inset heißt präfixfrei, wenn für kein Paar \begin_inset Formula $u\sqsubseteq v$ \end_inset mit \begin_inset Formula $u\neq v$ \end_inset sowohl \begin_inset Formula $u\in L$ \end_inset als auch \begin_inset Formula $v\in L$ \end_inset gilt. \begin_inset Quotes ard \end_inset \begin_inset LatexCommand \cite[S.98 (+10)]{KindlerManthey} \end_inset \layout Subsection \lang german Kellerautomaten \layout Standard \lang german Englisch \begin_inset Quotes ald \end_inset Pushdown-Automaten \begin_inset Quotes ard \end_inset , deshalb in \begin_inset LatexCommand \cite{Sipser} \end_inset auch abgekürzt mit \begin_inset Quotes ald \end_inset PDA \begin_inset Quotes ard \end_inset . Kellerautomaten sind die Akzeptoren für kontextfreie Sprachen. Kellerautomaten haben ein unbeschränktes Register mit dem man sich das Abarbeiten eines Zustandes merken kann; die Unbeschränktheit des unbeschränkten Register durchbricht dabei die endliche Beschränktheit bei endlichen Automaten. Ein Zustandsübergang eines Kellerautomaten enthält die Änderung des Kellerkopfe s. \layout Standard \lang german Zu jeder kontextfreien Sprache kann ein nichtdeterministischer Kellerautomat konstruiert werden. Jedoch gibt es nicht zu jeder kontextfreien Sprache einen determinierten Kellerautomaten; ein Beispiel für eine solche kontextfreie Sprache ist aber schwierig zu finden. \layout Subsection \lang german Nicht-kontextfreie Sprachen \layout Standard \lang german \SpecialChar ~ \layout Part \lang german Berechenbarkeit \layout Section \lang german Church-Turing These \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Turingmaschinen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Varianten von Turingmaschinen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Definition des Algorithmus \layout Standard \lang german \SpecialChar ~ \layout Section \lang german Entscheidbarkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Entscheidbare Sprachen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Das Halteproblem \layout Standard \lang german \SpecialChar ~ \layout Section \lang german Reduzierbarkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Unentscheidbare Probleme aus der Theorie der formalen Sprachen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Ein einfaches unentscheidbares Problem \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Abbildende Reduzierbarkeit (Mapping Reducibility) \layout Standard \lang german \SpecialChar ~ \layout Section \lang german Fortgeschrittene Aspekte der Berechenbarkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Das Rekursionstheorem \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Entscheidbarkeit logischer Theorien \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Turing-Reduzierbarkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Eine Definition für Information \layout Standard \lang german \SpecialChar ~ \layout Part \lang german Komplexität \layout Section \lang german Zeitkomplexität \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Komplexitätsmessung \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Die Klasse P \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Die Klasse NP \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german NP-Vollständigkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Beispiele für NP-vollständige Probleme \layout Standard \lang german \SpecialChar ~ \layout Section \lang german Ortskomplexität \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Savitch'sches Theorem \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Die Klasse PSPACE \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german PSPACE-Vollständigkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Die Klassen L und NL \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german NL-Vollständigkeit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german NL ist CONL \layout Standard \lang german \SpecialChar ~ \layout Section \lang german Widerspenstigkeit (Intractability) \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Hierarchietheoreme \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Relativierung \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Schaltungskomplexit \layout Standard \lang german \SpecialChar ~ \layout Section \lang german Fortgeschrittene Aspekte der Komplexit \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Approximierende Algorithmen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Probabilistische Algorithmen \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Alternierung \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Interaktive Beweissysteme \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Parallelcomputing \layout Standard \lang german \SpecialChar ~ \layout Subsection \lang german Kryptografie \layout Standard \lang german \SpecialChar ~ \layout Part \lang german Anhang \layout Section \start_of_appendix \lang german Aufgabensammlung \layout Standard \lang german Die folgenden Aufgaben sind zusammengenommen gleichzeitig: \layout Itemize \lang german Die gesamte Menge der Übungsaufgaben zur Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset bei Prof. Dr. Hans-Rudolf Metz. Siehe \begin_inset LatexCommand \cite{Metz-Uebgn} \end_inset . Die Reihenfolge hier ist identisch zu der in \begin_inset LatexCommand \cite{Metz-Uebgn} \end_inset . \layout Itemize \lang german Fast die gesamte Menge der Übungsaufgaben zur Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset bei Prof. Dr. Ernst Kausen. Siehe \begin_inset LatexCommand \cite{Kausen-Uebgn} \end_inset . Ausgenommen sind nur die ersten beiden Übungsblätter mit mathematischen Grundlagen, die nicht speziell klausurrelevant sind. Die Reihenfolge hier ist identisch zu der in \begin_inset LatexCommand \cite{Kausen-Uebgn} \end_inset . \layout Itemize \lang german Eine kleine Auswahl der Übungsaufgaben aus dem Buch Michael Sipser: \begin_inset Quotes ald \end_inset Introduction to the Theory of Computation \begin_inset Quotes ard \end_inset (Boston 1997). Siehe \begin_inset LatexCommand \cite{Sipser} \end_inset . Die Reihenfolge hier folgt nicht der in \begin_inset LatexCommand \cite{Sipser} \end_inset . \layout Subsection \lang german Zustandsübergangsdiagramm eines DEA \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Ein DEA sei formal gegeben durch \begin_inset Formula $\left(\left\{ q_{1},q_{2},q_{3},q_{4},q_{5}\right\} ,\left\{ \mathtt{u},\mathtt{d}\right\} ,\delta,q_{3},\left\{ q_{3}\right\} \right)$ \end_inset , wobei \begin_inset Formula $\delta$ \end_inset durch die folgende Tabelle gegeben ist. Geben Sie das Zustandsübergangsdiagramm des DEA an. \layout Standard \lang german \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{u}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{d}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{1}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{1}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{2}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{2}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{1}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{3}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{3}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{2}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{4}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{4}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{3}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{5}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{5}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{4}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $q_{5}$ \end_inset \end_inset \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.1 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.3]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german DEAs für Sprachen ber \begin_inset Formula $\Sigma=\left\{ 0,1\right\} $ \end_inset \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie Zustandsübergangsdiagramme für DEAs an, die die folgenden Sprachen erkennen. In jedem Fall ist das Alphabet \begin_inset Formula $\left\{ 0,1\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ \textnormal{beginnt mit $1$ und endet mit $0$}}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mindestens dreimal $1$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält den Substring $0101$, also $w=x0101y$ für beliebige $x$ und $y$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ hat Länge mind. $3$ und das dritte Symbol ist $0$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ beginnt mit $0$ und hat ungerade Länge, oder beginnt mit $1$ und hat gerade Länge}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält nicht den Substring $110$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ \varepsilon,0\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält gerade Anzahl $0$en oder genau zwei $1$en}\right\} $ \end_inset \layout Enumerate \lang german Die leere Menge. \layout Enumerate \lang german Alle Zeichenketten auer der leeren Zeichenkette. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.1 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.4, part a-f.k-n]{Sipser} \end_inset . \layout Paragraph \lang german Lösung \layout Subsection \lang german Sprachen unter regulren Operationen \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Es sei \begin_inset Formula $\Sigma=\left\{ 0,1\right\} $ \end_inset und \begin_inset Formula $A$ \end_inset \begin_inset Formula $B$ \end_inset seien Sprachen über dem Alphabet \begin_inset Formula $\Sigma$ \end_inset mit \layout Standard \lang german \begin_inset Formula \[ A=\left\{ w\mid\textrm{$w$ endet mit $1$}\right\} \] \end_inset \begin_inset Formula \[ B=\left\{ w\mid\textrm{$w$ beginnt mit $1$}\right\} \] \end_inset Beschreiben Sie, welche Sprachen sich mit den regulären Operationen \begin_inset Formula $A\cup B$ \end_inset \begin_inset Formula $A\circ B$ \end_inset \begin_inset Formula $A^{*}$ \end_inset und \begin_inset Formula $B^{*}$ \end_inset ergeben. Quelle: \begin_inset LatexCommand \cite[Bl.1 Aufg.3]{Kausen-Uebgn} \end_inset \layout Paragraph \lang german Lösung \layout Standard \lang german \begin_inset Formula \[ A\cup B=\left\{ w\mid w=\mathtt{1}x\,\vee\, w=x1,\: x\in\Sigma^{*}\right\} \] \end_inset \begin_inset Formula \[ A\circ B=\left\{ w\mid w=x11y,\: x,y\in\Sigma^{*}\right\} \] \end_inset \begin_inset Formula \[ A^{*}=\left\{ w\mid w=x^{n},\: n\in\mathbb{N}_{0},\: x=y1,\: y\in\Sigma^{*}\right\} \] \end_inset \begin_inset Formula \[ B^{*}=\left\{ w\mid w=x^{n},\: n\in\mathbb{N}_{0},\: x=1y,\: y\in\Sigma^{*}\right\} \] \end_inset \layout Subsection \lang german NEAs zu gegebenen Sprachen konstruieren (1) \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Konstruieren Sie NEAs mit der angegebenen Anzahl von Zuständen, die jeweils die angegebene Sprache akzeptieren. Es sei jeweils \begin_inset Formula $\Sigma=\left\{ 0,1\right\} $ \end_inset \layout Enumerate \lang german Die Sprache \begin_inset Formula $\left\{ w\mid\textrm{$w$ endet mit $00$}\right\} $ \end_inset mit drei Zuständen. \layout Enumerate \lang german Die Sprache \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält den Substring $0101$, also $w=x0101y$ für beliebige $x$ und $y$}\right\} $ \end_inset mit fünf Zustnden. \layout Enumerate \lang german Die Sprache \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält gerade Anzahl $0$en oder genau zwei $1$en}\right\} $ \end_inset mit sechs Zuständen. \layout Enumerate \lang german Die Sprache \begin_inset Formula $\left\{ 0\right\} $ \end_inset mit zwei Zuständen. \layout Enumerate \lang german Die Sprache \begin_inset Formula $\left\{ \varepsilon\right\} $ \end_inset mit einem Zustand. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.2 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.5 part a-d.f]{Sipser} \end_inset . \layout Paragraph \lang german Lösung \layout Subsection \lang german NEA in DEA umwandeln \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german In der Vorlesung wurde hergeleitet, dass es zu jedem NEA einen äquivalenten DEA gibt. Verwenden Sie die im Beweis benutzte Methode, um die folgenden beiden nichtdete rministischen endlichen Automaten in äquivalente deterministische endliche Automaten zu konvertieren. Zeichnen Sie zunächst die Zustandsdiagramme. \layout Enumerate \lang german Es sei \begin_inset Formula $N=\left\{ \left\{ 1,2\right\} ,\left\{ \mathtt{a},\mathtt{b}\right\} ,\delta,1,\left\{ 1\right\} \right\} $ \end_inset , wobei \begin_inset Formula $\delta$ \end_inset durch die folgende Tabelle gegeben ist. \newline \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{a}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{b}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\varepsilon$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 1,2\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 2\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 1\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \end_inset \layout Enumerate \lang german Es sei \begin_inset Formula $N=\left\{ \left\{ 1,2,3\right\} ,\left\{ \mathtt{a},\mathtt{b}\right\} ,\delta,1,\left\{ 2\right\} \right\} $ \end_inset , und \begin_inset Formula $\delta$ \end_inset ist durch die folgende Tabelle gegeben. \newline \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{a}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{b}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\varepsilon$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 3\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 2\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 1\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $3$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 2\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\left\{ 2,3\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\emptyset$ \end_inset \end_inset \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.2 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.12]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german NEA zur Konkatenation regulärer Sprachen \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german In der Vorlesung wurde gezeigt, da die Klasse der regulären Sprachen unter der Operation der Konkatenation abgeschlossen ist. Verwenden Sie die für die Herleitung benutzte Konstruktion, um das Zustandsdiag ramm eines nichtdeterministischen endlichen Automaten anzugeben, der die Konkatenation der Sprachen \layout Itemize \lang german \begin_inset Formula $\left\{ w\mid\textrm{die Länge von $w$ ist höchstens $5$}\right\} $ \end_inset und \layout Itemize \lang german \begin_inset Formula $\left\{ w\mid\textrm{jede ungerade Position von $w$ ist eine $1$}\right\} $ \end_inset \layout Standard \lang german erkennt. Es sei \begin_inset Formula $\Sigma=\left\{ 0,1\right\} $ \end_inset Quelle: \begin_inset LatexCommand \cite[Bl.3 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.7 part a]{Sipser} \end_inset . \layout Paragraph \lang german Lösung \layout Standard \lang german Die Konstruktion besteht darin, die Endzustände des Automaten \begin_inset Formula $A_{1}$ \end_inset durch \begin_inset Formula $\varepsilon$ \end_inset -Übergänge mit den Startzuständen des Automaten \begin_inset Formula $A_{2}$ \end_inset zu verbinden. Die Anfangszustände des kombinierten Automaten sind die Anfangszustände von \begin_inset Formula $A_{1}$ \end_inset , seine Endzustände sind die Endzustände von \begin_inset Formula $A_{2}$ \end_inset . Als Formel nach \begin_inset LatexCommand \cite[S.23 (+10)]{KindlerManthey} \end_inset \begin_inset Formula \begin{eqnarray*} A & = & \left(Q,\Sigma,\delta,I,F\right)\\ & = & \left(Q_{1}\cup Q_{2},\Sigma,\delta_{1}\cup\left(F_{1}\times\left\{ \varepsilon\right\} \times I_{2}\right)\cup\delta_{2},I_{1},F_{2}\right)\end{eqnarray*} \end_inset \layout Subsection \lang german NEAs zu gegebenen Sprachen konstruieren (2) \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Konstruieren Sie NEAs mit der angegebenen Anzahl von Zuständen, die die jeweils angegebene Sprache erkennen. \layout Enumerate \lang german Die Sprache \begin_inset Formula $0^{*}1^{*}0^{*}0$ \end_inset mit drei Zuständen. \layout Enumerate \lang german Die Sprache \begin_inset Formula $0^{*}$ \end_inset mit einem Zustand. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.3 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.5 part e.g]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Standard \lang german Sipser unterscheidet in \begin_inset LatexCommand \cite{Sipser} \end_inset fast nicht zwischen regulären Ausdrcken und regulären Sprachen. Jedoch sind reguläre Ausdrücke ein syntaktisches Konzept, und reguläre Sprachen sind das durch reguläre Ausdrcke repräsentierbare semantische Konzept. Reguläre Sprachen sind auch durch weitere syntaktische Konzepte repräsentierbar , z.B. durch endliche Automaten. Exakter wrde die Aufgabenstellung zum ersten Teil also z.B. lauten: \begin_inset Quotes ald \end_inset Konstruieren sie einen NEA mit drei Zuständen, der die vom regulären Ausdruck \begin_inset Formula $0^{*}1^{*}0^{*}0$ \end_inset erzeugte Sprache \begin_inset Formula $L\left(0^{*}1^{*}0^{*}0\right)$ \end_inset erkennt. \begin_inset Quotes ard \end_inset \layout Standard \lang german Zur Lösung hilft es hier nicht weiter, NEAs für die Teilausdrcke zu kombinieren (wie in \begin_inset LatexCommand \cite[S.23 (+10)]{KindlerManthey} \end_inset ), da dann wesentlich mehr als drei Zustände benötigt werden. \layout Subsection \lang german Reguläre Ausdrcke zu gegebenen Sprachen konstruieren \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie reguläre Ausdrcke an, die die folgenden Sprachen erzeugen: \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ \textnormal{beginnt mit $1$ und endet mit $0$}}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mindestens dreimal $1$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält den Substring $0101$, also $w=x0101y$ für beliebige $x$ und $y$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ hat Länge mind. $3$ und das dritte Symbol ist $0$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ beginnt mit $0$ und hat ungerade Länge, oder beginnt mit $1$ und hat gerade Länge}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält nicht den Substring $110$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{die Länge von $w$ ist höchstens $5$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ ist ein beliebiger String au er $11$ und $111$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{jede ungerade Position von $w$ ist eine $1$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mindestens zwei $0$en und höchstens eine $1$}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ \varepsilon,0\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält gerade Anzahl $0$en oder genau zwei $1$en}\right\} $ \end_inset \layout Enumerate \lang german Die leere Menge. \layout Enumerate \lang german Alle Zeichenketten außer der leeren Zeichenkette. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.3 Aufg.3]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.13]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Standard \lang german Es wird stets zuerst die Beschreibung der Sprache und dann der reguläre Ausdruck genannt. \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ \textnormal{beginnt mit $1$ und endet mit $0$}}\right\} $ \end_inset \begin_inset Formula \[ 1\left(0+1\right)^{*}0\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mindestens dreimal $1$}\right\} $ \end_inset \begin_inset Formula \[ \left(0+1\right)^{*}1\left(0+1\right)^{*}1\left(0+1\right)^{*}1\left(0+1\right)^{*}\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält den Substring $0101$, also $w=x0101y$ für beliebige $x$ und $y$}\right\} $ \end_inset \begin_inset Formula \[ \left(0+1\right)^{*}0101\left(0+1\right)^{*}\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ hat Länge mind. $3$ und das dritte Symbol ist $0$}\right\} $ \end_inset \begin_inset Formula \[ \left(0+1\right)\left(0+1\right)0\left(0+1\right)^{*}\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ beginnt mit $0$ und hat ungerade Länge, oder beginnt mit $1$ und hat gerade Länge}\right\} $ \end_inset \begin_inset Formula \[ 0\left(\left(0+1\right)\left(0+1\right)\right)^{*}+1\left(0+1\right)\left(\left(0+1\right)\left(0+1\right)\right)^{*}\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält nicht den Substring $110$}\right\} $ \end_inset \begin_inset Formula \begin{eqnarray*} & & \varepsilon\\ & + & \left(0+1\right)\\ & + & \left(0+1\right)\left(0+1\right)\\ & + & 0^{*}\left(10+0^{*}\right)^{*}111^{*}\end{eqnarray*} \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{die Länge von $w$ ist höchstens $5$}\right\} $ \end_inset \begin_inset Formula \[ \left(0+1+\varepsilon\right)\left(0+1+\varepsilon\right)\left(0+1+\varepsilon\right)\left(0+1+\varepsilon\right)\left(0+1+\varepsilon\right)\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ ist ein beliebiger String außer $11$ und $111$}\right\} $ \end_inset \begin_inset Formula \begin{eqnarray*} & & \varepsilon\\ & + & 0\left(0+1\right)^{*}\\ & + & 10\left(0+1\right)^{*}\\ & + & 110\left(0+1\right)^{*}\\ & + & 111\left(0+1\right)\left(0+1\right)^{*}\end{eqnarray*} \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{jede ungerade Position von $w$ ist eine $1$}\right\} $ \end_inset \begin_inset Formula \[ \left(1\left(0+1\right)\right)^{*}\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mindestens zwei $0$en und höchstens eine $1$}\right\} $ \end_inset \begin_inset Formula \begin{eqnarray*} & & 000^{*}\left(1+\varepsilon\right)0^{*}\\ & + & 0\left(1+\varepsilon\right)00^{*}\\ & + & \left(1+\varepsilon\right)000^{*}\end{eqnarray*} \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ \varepsilon,0\right\} $ \end_inset \begin_inset Formula \[ \varepsilon+0\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält gerade Anzahl $0$en oder genau zwei $1$en}\right\} $ \end_inset \begin_inset Formula \[ \left(1^{*}01^{*}01^{*}\right)^{*}+0^{*}10^{*}10^{*}\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german Die\SpecialChar ~ leere\SpecialChar ~ Menge. \begin_inset Formula \[ \emptyset\] \end_inset \layout List \labelwidthstring 00.00.0000 \lang german Alle\SpecialChar ~ Zeichenketten\SpecialChar ~ außer\SpecialChar ~ der\SpecialChar ~ leeren\SpecialChar ~ Zeichenkette. \begin_inset Formula \[ \left(0+1\right)\left(0+1\right)^{*}\] \end_inset \layout Subsection \lang german Beispiele und Gegenbeispiele für Wörter einer Sprache \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie für jede der folgenden Sprachen zwei Wörter an, die zu dieser Sprache gehören, und zwei Wörter, die nicht zu dieser Sprache gehören. (Also insgesamt 4 Wörter pro Sprache.) Nehmen Sie das Alphabet \begin_inset Formula $\Sigma=\left\{ a,b\right\} $ \end_inset für alle diese Sprachen an. \layout Enumerate \lang german \begin_inset Formula $a^{*}b^{*}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $a\left(ba\right)^{*}b$ \end_inset \layout Enumerate \lang german \begin_inset Formula $a^{*}\cup b^{*}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left(aaa\right)^{*}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\Sigma^{*}a\Sigma^{*}b\Sigma^{*}a\Sigma^{*}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $aba\cup bab$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left(\varepsilon\cup a\right)b$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left(a\cup ba\cup bb\right)\Sigma^{*}$ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.4 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.15]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Reguläre Ausdrücke in NEAs konvertieren \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Verwenden Sie das in der Vorlesung beschriebene Verfahren, um die folgenden regulären Ausdrücke in nichtdeterministische endliche Automaten zu konvertieren. \layout Enumerate \lang german \begin_inset Formula $\left(0\cup1\right)^{*}000\left(0\cup1\right)^{*}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\emptyset^{*}$ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.5 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.14 part a.c]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german DEAs in reguläre Ausdrücke konvertieren \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Verwenden Sie das in der Vorlesung beschriebene Verfahren, um die folgenden endlichen Automaten in reguläre Ausdrücke zu konvertieren. Zeichnen Sie zunächst die Zustandsdiagramme der Automaten. \layout Enumerate \lang german Es sei \begin_inset Formula $M=\left\{ \left\{ 1,2\right\} ,\left\{ \mathtt{a},\mathtt{b}\right\} ,\delta,1,\left\{ 2\right\} \right\} $ \end_inset , wobei \begin_inset Formula $\delta$ \end_inset durch die folgende Tabelle gegeben ist. \newline \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{a}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{b}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \end_inset \layout Enumerate \lang german Es sei \begin_inset Formula $M=\left\{ \left\{ 1,2,3\right\} ,\left\{ \mathtt{a},\mathtt{b}\right\} ,\delta,1,\left\{ 1,3\right\} \right\} $ \end_inset , und \begin_inset Formula $\delta$ \end_inset ist durch die folgende Tabelle gegeben. \newline \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{a}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $\mathtt{b}$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $3$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $3$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $1$ \end_inset \end_inset \begin_inset Text \layout Standard \lang german \begin_inset Formula $2$ \end_inset \end_inset \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.5 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.16]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Pumping Lemma für reguläre Sprachen \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Benutzen Sie das Pumping Lemma (d.i., den \begin_inset Formula $uvw$ \end_inset -Satz) um nachzuweisen dass die folgenden Sprachen nicht regulär sind. \layout Enumerate \lang german \begin_inset Formula $A_{1}=\left\{ \mathtt{0}^{n}\mathtt{1}^{n}\mathtt{2}^{n}\mid n\geq0\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $A_{2}=\left\{ www\mid w\in\left\{ \mathtt{a},\mathtt{b}\right\} ^{*}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $A_{3}=\left\{ \mathtt{a}^{2^{n}}\mid n\geq0\right\} $ \end_inset Dabei bedeutet \begin_inset Formula $\mathtt{a}^{2^{n}}$ \end_inset eine Zeichenkette von \begin_inset Formula $2^{n}$ \end_inset \begin_inset Formula $\mathtt{a}$ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.6 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 1.17]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Parsebäume und Ableitungen für eine kontextfreie Grammatik \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Es sei \begin_inset Formula $G=\left(V,\Sigma,R,E\right)$ \end_inset eine kontextfreie Grammatik mit \begin_inset Formula $V=\left\{ E,T,F\right\} $ \end_inset , \begin_inset Formula $\Sigma=\left\{ \mathtt{a},\mathtt{+},\mathtt{\times},\mathtt{(},\mathtt{)}\right\} $ \end_inset und den folgenden Regeln: \begin_inset Formula \begin{eqnarray*} E & \rightarrow & E\mathtt{+}T\mid T\\ T & \rightarrow & T\mathtt{\times}F\mid F\\ F & \rightarrow & \mathtt{(}E\mathtt{)}\mid\mathtt{a}\end{eqnarray*} \end_inset Geben Sie Parsebäume und Ableitungen für jeden der folgenden Strings an. \layout Enumerate \lang german \begin_inset Formula $\mathtt{a}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\mathtt{a+a}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\mathtt{a+a+a}$ \end_inset \layout Enumerate \lang german \begin_inset Formula $\mathtt{((a))}$ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.7 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.1]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Fragen zu einer kontextfreien Grammatik \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Beantworten Sie die folgenden Fragen in Bezug auf die folgende kontextfreie Grammatik \begin_inset Formula $G$ \end_inset \begin_inset Formula \begin{eqnarray*} R & \rightarrow & XRX\mid S\\ S & \rightarrow & \mathtt{a}T\mathtt{b}\mid\mathtt{b}T\mathtt{a}\\ T & \rightarrow & XTX\mid X\mid\varepsilon\\ X & \rightarrow & \mathtt{a}\mid\mathtt{b}\end{eqnarray*} \end_inset \layout Enumerate \lang german Was sind die Nichtterminalsymnbole und Terminalsymbole von \begin_inset Formula $G$ \end_inset ? Welches ist das Startsymbol? \layout Enumerate \lang german Geben Sie drei Beispiele für Strings die in \begin_inset Formula $L\left(G\right)$ \end_inset enthalten sind. \layout Enumerate \lang german Geben Sie drei Beispiele für Strings die \emph on nicht \emph default in \begin_inset Formula $L\left(G\right)$ \end_inset enthalten sind. \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $T\Rightarrow\mathtt{aba}$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $T\stackrel{*}{\Rightarrow}\mathtt{aba}$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $T\Rightarrow T$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $T\stackrel{*}{\Rightarrow}T$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $XXX\Rightarrow\mathtt{aba}$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $X\stackrel{*}{\Rightarrow}\mathtt{aba}$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $T\stackrel{*}{\Rightarrow}XX$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $T\stackrel{*}{\Rightarrow}XXX$ \end_inset \layout Enumerate \lang german Wahr oder falsch: \begin_inset Formula $S\stackrel{*}{\Rightarrow}\varepsilon$ \end_inset \layout Enumerate \lang german Beschreiben Sie \begin_inset Formula $L\left(G\right)$ \end_inset in natürlicher Sprache. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.7 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.3]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Kontextfreie Grammatiken zu gegebenen Sprachen konstruieren (1) \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie kontextfreie Grammatiken an, die die folgenden Sprachen erzeugen. Das Alphabet sei jeweils \begin_inset Formula $\Sigma=\left\{ \mathtt{0},\mathtt{1}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mindestens drei $\mathtt{1}$en}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ beginnt und endet mit demselben Symbol}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ hat ungerade Länge}\right\} $ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.7 Aufg.3]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.4 part a-c]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Umwandlung in Chomsky-Normalform \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Die kontextfreie Grammatik \begin_inset Formula \begin{eqnarray*} A & \rightarrow & BAB\mid B\mid\varepsilon\\ B & \rightarrow & \mathtt{00}\mid\varepsilon\end{eqnarray*} \end_inset soll mit der in der Vorlesung besprochenen Methode in eine äquivalente kontextfr eie Grammatik in Chomsky-Normalform umgewandelt werden. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.8 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.14]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Zustandsdiagramme für Kellerautomaten zu gegebenen Sprachen (2) \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie Zustandsdiagramme von Kellerautomaten für die folgenden Sprachen an. \layout Enumerate \lang german Das Komplement der Sprache \begin_inset Formula $\left\{ \mathtt{a}^{n}\mathtt{b}^{n}\mid n\geq0\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mathtt{\#}x\mid\textrm{$w^{\mathcal{R}}$ist ein Substring von $x$, wobei $w,x\in\left\{ \mathtt{0},\mathtt{1}\right\} ^{*}$}\right\} $ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.8 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.7]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Kontextfreie Grammatiken zu gegebenen Sprachen konstruieren (2) \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie kontextfreie Grammatiken an, die die folgenden Sprachen erzeugen. Das Alphabet sei jeweils \begin_inset Formula $\Sigma=\left\{ \mathtt{0},\mathtt{1}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ hat ungerade Länge und $\mathtt{0}$ als mittleres Symbol}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enth lt mehr $\mathtt{1}$en als $\mathtt{0}$en}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w=w^{\mathcal{R}}$, d.i., $w$ ist ein Palindrom}\right\} $ \end_inset \layout Enumerate \lang german Die leere Menge. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.8 Aufg.3]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.4 part d-g]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Zustandsdiagramme für Kellerautomaten zu gegebenen Sprachen (2) \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie Zustandsdiagramme von Kellerautomaten für die folgenden Sprachen an. \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ hat ungerade Länge und $\mathtt{0}$ als mittleres Symbol}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält mehr $\mathtt{1}$en als $\mathtt{0}$en}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w=w^{\mathcal{R}}$, d.i., $w$ ist ein Palindrom}\right\} $ \end_inset \layout Enumerate \lang german Die leere Menge. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.8 Aufg.4]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.5]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Kontextfreie Grammatik in Kellerautomaten konvertieren \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Konvertieren Sie mit der in der Vorlesung vorgestellten Methode die kontextfreie Grammatik \begin_inset Formula $G=\left(V,\Sigma,R,E\right)$ \end_inset mit \begin_inset Formula $V=\left\{ E,T,F\right\} $ \end_inset \begin_inset Formula $\Sigma=\left\{ \mathtt{a},\mathtt{+},\mathtt{\times},\mathtt{(},\mathtt{)}\right\} $ \end_inset und den Regeln \begin_inset Formula \begin{eqnarray*} E & \rightarrow & E\mathtt{+}T\mid T\\ T & \rightarrow & T\mathtt{\times}F\mid F\\ F & \rightarrow & \mathtt{(}E\mathtt{)}\mid\mathtt{a}\end{eqnarray*} \end_inset in einen äquivalenten Kellerautomaten (Pushdown-Automaten). \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.9 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.11]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Abschlusseigenschaften kontextfreier Sprachen \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Es soll gezeigt werden, dass der Durchschnitt zweier kontextfreier Sprachen nicht immer kontextfrei ist, und dass auch das Komplement einer kontextfreien Sprache nicht kontextfrei sein muss. \layout Enumerate \lang german Verwenden Sie die Sprache \begin_inset Formula $A=\left\{ \mathtt{a}^{m}\mathtt{b}^{n}\mathtt{c}^{n}\mid m,n\geq0\right\} $ \end_inset und die Sprache \begin_inset Formula $B=\left\{ \mathtt{a}^{n}\mathtt{b}^{n}\mathtt{c}^{m}\mid m,n\geq0\right\} $ \end_inset zusammen mit dem in der Vorlesung besprochenen ersten Beispiel zum Pumping-Lemm a kontextfreie Sprachen, um zu zeigen, dass die Klasse der kontextfreien Sprachen nicht abgeschlossen unter dem Durchschnitt ist. \layout Enumerate \lang german Zeigen Sie mit dem Ergebniss des ersten Teils der Aufgabe und mit einer Regel von De Morgan (siehe Formelsammlung), dass die Klasse der kontextfreien Sprachen nicht abgeschlossen unter dem Komplement ist. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.10 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.2]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Nachweis dass Sprachen nicht kontextfrei sind über Pumping-Lemma \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Verwenden Sie das Pumping-Lemma um zu zeigen dass die folgenden Sprachen nicht kontextfrei sind. \layout Enumerate \lang german \begin_inset Formula $\left\{ \mathtt{0}^{n}\mathtt{\#}\mathtt{0}^{2n}\mathtt{\#}\mathtt{0}^{3n}\mid n\geq0\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mathtt{\#}x\mid\textrm{$w$ ist ein Substring von $x$, wobei $w,x\in\left\{ \mathtt{a},\mathtt{b}\right\} ^{*}$}\right\} $ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.10 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.18 part b-c]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Zahl der Ableitungsschritte für kontextfreie Grammatiken in Chomsky-Normalform \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Zeigen Sie: Wenn \begin_inset Formula $G$ \end_inset eine kontextfreie Grammatik in Chomsky-Normalform ist, dann sind für jeden String \begin_inset Formula $w\in L\left(G\right)$ \end_inset mit Länge \begin_inset Formula $n\geq1$ \end_inset genau \begin_inset Formula $2n-1$ \end_inset Schritte notwendig für jede Ableitung von \begin_inset Formula $w$ \end_inset . \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.10 Aufg.3]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 2.19]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Turing-Entscheidbarkeit \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german In der Vorlesung wurde gezeigt, da eine nichtdeterministische Turing-Maschine durch eine deterministische Turing-Maschine simuliert werden kann, dass also eine Sprache genau dann Turing-erkennbar ist, wenn sie von einer nichtdete rministischen Turing-Maschine erkannt wird. Ändern Sie den Beweis ab, um zu zeigen, da eine Sprache genau dann entscheidbar ist, wenn eine nichtdeterministische Turing-Maschine sie entscheidet. (Sie können den folgenden Satz über Bäume benutzen: Wenn jeder Knoten in einem Baum endlich viele Kinder und jeder Zweig des Baumes endlich viele Knoten hat, dann hat der Baum endlich viele Knoten.) \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.11 Aufg.1]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 3.3]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Turing-Maschinen zu gegebenen Sprachen beschreiben \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Geben Sie informelle Beschreibungen von Turing-Maschinen an (entsprechend den Beschreibungen in der Vorlesung; Zustandsdiagramme sollen nicht gezeichnet werden), die die folgenden Sprachen über dem Alphabet \begin_inset Formula $\left\{ \mathtt{0},\mathtt{1}\right\} $ \end_inset entscheiden. \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält gleich viele $\mathtt{0}$en und $\mathtt{1}$en}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält doppelt so viele $\mathtt{0}$en wie $\mathtt{1}$en}\right\} $ \end_inset \layout Enumerate \lang german \begin_inset Formula $\left\{ w\mid\textrm{$w$ enthält nicht doppelt so viele $\mathtt{0}$en wie $\mathtt{1}$en}\right\} $ \end_inset \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.11 Aufg.2]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 3.8]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Subsection \lang german Mächtigkeit von Kellerautomaten mit \begin_inset Formula $k$ \end_inset Kellern \layout Paragraph \lang german Aufgabenstellung \layout Standard \lang german Sei ein \begin_inset Formula $k$ \end_inset -Kellerautomat ein Kellerautomat mit \begin_inset Formula $k$ \end_inset Kellern. Somit ist ein \begin_inset Formula $0$ \end_inset -Kellerautomat ein nichtdeterministischer endlicher Automat und ein \begin_inset Formula $1$ \end_inset -Kellerautomat ist ein konventioneller Kellerautomat. \begin_inset Formula $1$ \end_inset -Kellerautomaten sind bekanntlich mächtiger als \begin_inset Formula $0$ \end_inset -Kellerautomaten, d.h. sie erkennen eine mächtigere Klasse von Sprachen. \layout Enumerate \lang german Zeigen Sie dass \begin_inset Formula $2$ \end_inset -Kelleautomaten mchtiger als \begin_inset Formula $1$ \end_inset -Kellerautomaten sind. \layout Enumerate \lang german Zeigen Sie dass \begin_inset Formula $3$ \end_inset -Kellerautomaten nicht mächtiger als \begin_inset Formula $2$ \end_inset -Kellerautomaten sind. \layout Standard \lang german Hinweis: Simulieren sie das Band einer Turing-Maschine durch zwei Kellern. \layout Standard \lang german Quelle: \begin_inset LatexCommand \cite[Bl.11 Aufg.3]{Kausen-Uebgn} \end_inset bzw. \begin_inset LatexCommand \cite[exercise 3.9]{Sipser} \end_inset \layout Paragraph \lang german Lösung \layout Section \lang german Klausurrelevanter Stoff \layout Standard \lang german Die folgende erschöpfende Zusammenstellung des klausurrelevanten Stoffes hat Prof. Dr. Ernst Kausen in der Klausurvorbesprechung 2005-09-20 gemacht, also für die Prfung zum Sommersemester 2005. Darin nicht genannter Stoff (z.B. der Stoff der in Vorträgen vermittelt wurde) ist nicht klausurrelevant. Die Veranstaltung zeichnete sich besonders dadurch aus dass die verschiedenen Konstruktionsverfahren an ausführlichen Beispielen behandelt wurden. Die Turing-Maschine wurde aus Zeitgründen nicht mehr behandelt. \layout Subsection \lang german Formale Sprache \layout Itemize \lang german Alphabet \layout Itemize \lang german \begin_inset Formula $\Sigma^{*}$ \end_inset \layout Itemize \lang german formale Sprache \begin_inset Formula $L\subset\Sigma^{*}$ \end_inset \layout Itemize \lang german Operationen auf formalen Sprachen: \begin_inset Formula $L_{1}+L_{2}$ \end_inset \begin_inset Formula $L_{1}L_{2}$ \end_inset \begin_inset Formula $L^{n}$ \end_inset \begin_inset Formula $L^{*}$ \end_inset \layout Subsection \lang german Endliche Automaten \layout Itemize \lang german Ein DEA \begin_inset Formula $\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset wobei \begin_inset Formula $\delta$ \end_inset eine Abbildung (Funktion) ist: \begin_inset Formula $\delta:S\times\Sigma\rightarrow S$ \end_inset \begin_deeper \layout Itemize \lang german Zustandsdiagramm eines DEA zeichnen können \layout Itemize \lang german Bedeutung von \begin_inset Formula $\delta\left(s,w\right)$ \end_inset bzw. \begin_inset Formula $s\stackrel{w}{\rightarrow}s'$ \end_inset kennen \layout Itemize \lang german Konzept der akzeptierten Sprache \begin_inset Formula $T\left(A\right)$ \end_inset \layout Itemize \lang german Konstruktion eines DEA zu einer Sprache \begin_inset Formula $L$ \end_inset , die durch informale Beschreibung gegeben ist. In der Vorlesung wurden dazu um 10 Beispiele durchgenommen. \end_deeper \layout Itemize \lang german NEA \begin_inset Formula $\left(S,\Sigma,\delta,s_{0},F\right)$ \end_inset wobei \begin_inset Formula $\delta$ \end_inset im Unterschied zum DEA eine Abbildung \begin_inset Formula $\delta:S\times\Sigma_{\varepsilon}\rightarrow p\left(S\right)$ \end_inset ist \begin_inset Foot collapsed true \layout Standard \lang german \begin_inset Formula $\Sigma_{\varepsilon}=\Sigma\cup\left\{ \varepsilon\right\} $ \end_inset , was Spontanbergnge erlaubt; \begin_inset Formula $p\left(S\right)$ \end_inset ist die Potenzmenge von \begin_inset Formula $S$ \end_inset , also die Menge aller mglichen Teilmengen von \begin_inset Formula $S$ \end_inset \end_inset \begin_deeper \layout Itemize \lang german Konzepte wie beim DEA \layout Itemize \lang german Vorteil: erlaubt flexibleren Umgang mit Automaten als bei DEAs, geringere Zustandsmengen. \layout Itemize \lang german Nachteil: das \begin_inset Quotes ald \end_inset Wortproblem \begin_inset Quotes ard \end_inset ist wesentlich schwieriger zu lsen als mit einem DEA. Denn man muss alle Verzweigungen untersuchen, es gibt keinen determinierten Pfad durch den Automaten wie beim DEA. \layout Itemize \lang german Äquivalenz von NEA und DEA. Bewiesen wird das durch ein konstruktives Verfahren, das man können muss: die Konstruktion eines DEA zu einem gegebenen NEA. Diese Aufgabe wird in der Klausur von einem einfachen Beispiel ausgehen, weil dieses Verfahren einige Zeit braucht. \end_deeper \layout Subsection \lang german Reguläre Ausdrücke \layout Itemize \lang german rekursive Definition regulärer Ausdrücke \layout Itemize \lang german die regulären Operationen \begin_inset Formula $+$ \end_inset \begin_inset Formula $\cdot$ \end_inset \begin_inset Formula $*$ \end_inset \layout Itemize \lang german Michael Sipser macht in \begin_inset LatexCommand \cite{Sipser} \end_inset kaum Unterschiede zwischen regulären Sprachen und regulären Ausdrcken. In dieser Veranstaltung wurde aber genau ein regulärer Ausdruck \begin_inset Formula $\alpha$ \end_inset unterschieden von \begin_inset Formula $L\left(\alpha\right)$ \end_inset , d.i. die von \begin_inset Formula $\alpha$ \end_inset erzeugte reguläre Sprache. \layout Itemize \lang german regulären Ausdruck konstruieren können, der eine (informal beschriebene) Sprache \begin_inset Formula $L$ \end_inset erzeugt \layout Itemize \lang german Äquivalenzkonzept: reguläre Sprache \begin_inset Formula $\cong$ \end_inset \begin_inset Foot collapsed true \layout Standard \lang german \begin_inset Quotes ald \end_inset ist quivalent \begin_inset Quotes ard \end_inset \end_inset zur Menge der Sprachen die von endlichen Automaten erkannt werden. Also gibt es zu jedem regulren Ausdruck einen endlichen Automaten, der diese Sprache akzeptiert und andersherum: \begin_deeper \layout Itemize \lang german Konstruktion \begin_inset Quotes ald \end_inset regulärer Ausdruck \begin_inset Formula $\rightarrow$ \end_inset NEA \begin_inset Quotes ard \end_inset für die Klausur können) \layout Itemize \lang german Konstruktion \begin_inset Quotes ald \end_inset NEA \begin_inset Formula $\rightarrow$ \end_inset regulärer Ausdruck \begin_inset Quotes ard \end_inset (kommt nicht in der Klausur vor) \end_deeper \layout Itemize \lang german Pumping Lemma ( \begin_inset Formula $uvw$ \end_inset -Theorem) für reguläre Ausdrücke. Der Beweis des Pumping Lemma wird in der Klausur nicht gefordert. Auch eine Anwendung des Pumping Lemma zum Test der Regularität einer Sprache wird in der Klausur nicht gefordert sein, weil dies zu theoretisch sein. \layout Subsection \lang german Grammatiken \layout Itemize \lang german Hier geht der Stoff weit über Michael Sipsers Buch \begin_inset LatexCommand \cite{Sipser} \end_inset hinaus. Sipser behandelt nur kontextfreie Grammatiken, in der Vorlesung wurde aber das allgemeine Chomsky-Konzept einer Grammatik eingeführt: \begin_inset Formula $G=\left(N,T,R,S\right)$ \end_inset Das Regelsystem ist \begin_inset Formula $R\subset\Sigma_{e}^{*}\times\Sigma^{*}$ \end_inset \begin_inset Formula $\Sigma=N\cup T$ \end_inset und \begin_inset Formula $\Sigma_{e}^{*}=\Sigma^{*}\setminus\left\{ \varepsilon\right\} =\Sigma^{+}$ \end_inset \layout Itemize \lang german direkte Ableitbarkeit: \begin_inset Formula $w\,\overrightarrow{G}\, w'$ \end_inset Bedeutung: \begin_inset Formula $x\alpha y\,\overrightarrow{G}\, x\beta y\Leftrightarrow\left(\alpha,\beta\right)\in R$ \end_inset \layout Itemize \lang german Ableitbarkeit: \begin_inset Formula $w\stackrel{*}{\,\overrightarrow{G}\,}w'$ \end_inset \layout Itemize \lang german Die Sprache \begin_inset Formula $L=L\left(G\right)$ \end_inset zu einer gegebenen Grammatik \begin_inset Formula $G$ \end_inset erkennen können; das ist, informal beschreiben können, welche Art Wörter man aus einer Grammatik ableiten kann. \layout Itemize \lang german Chomsky-Hierarchie verstehen (es geht jeweils um echte Inklusionen) \begin_deeper \layout Itemize \lang german Typ 0: die allgemeine Chomsky-Grammatik \begin_inset Formula $G=\left(N,T,R,S\right)$ \end_inset \layout Itemize \lang german Typ 1: kontextsensitive Grammatiken \layout Itemize \lang german Typ 2: kontextfreie Grammatiken \layout Itemize \lang german Typ 3: rechtslineare Grammatiken (auch genannt: reguläre Grammatiken) \end_deeper \layout Itemize \lang german Wichtige Äquivalenz, eigentlich der Kernsatz der Vorlesung: \begin_inset Formula \[ \mathrm{rechtslineare\: Grammatiken}\cong\mathrm{reguläre\: Sprachen}\cong\mathrm{endliche\: Automaten}\] \end_inset \layout Itemize \lang german Diese Äquivalenz (zwischen rechtslinearen Grammatiken und regulren Sprachen) wird durch zwei Konstruktionsverfahren bewiesen, die man beide anwenden können muss \begin_inset Foot collapsed true \layout Standard \lang german In der Vorlesung wurden dazu einige Beispiele behandelt, die man sich ansehen sollte. \end_inset \begin_deeper \layout Itemize \lang german vom DEA zu einer rechtslinearen Grammatik \layout Itemize \lang german von einer rechtslinearen Grammatik zu einem NEA \end_deeper \layout Subsection \lang german Kontextfreie Sprachen \layout Itemize \lang german Konstruktion beherrschen: kontextfreie Grammatik zu einer informal gegebenen Sprache \begin_inset Formula $L$ \end_inset konstruieren. \layout Itemize \lang german Die Chomsky-Normalform der kontextfreien Grammatik (CNF) wurde behandelt, man muss also wissen was das ist. Ihre Konstruktion kommt in der Klausur jedoch nicht dran weil sie in der Vorlesung nicht in voller Tiefe behandelt wurde und weil sie zu lange dauert (mindestens 30 Minuten). \layout Itemize \lang german Kellerautomaten (mit Kelleralphabet, Kellerstartzustand, komplizierteres Akzeptieren) \begin_deeper \layout Itemize \lang german determinierte Kellerautomaten \layout Itemize \lang german nichtdeterminierte Kellerautomaten \layout Itemize \lang german verstehen: wie funktioniert eine Ableitung in einem Kellerautomaten \layout Itemize \lang german Konzept der vom Kellerautomaten erkannten Sprache \begin_inset Formula $T\left(A\right)$ \end_inset Die Konfiguration zu einem Wort \begin_inset Formula $w$ \end_inset ist \begin_inset Formula $\left(s,w,k\right)$ \end_inset ; man kann von einer Konfiguration zu einer anderen durch einen geeigneten Zustandsübergang kommen. \begin_inset Quotes ald \end_inset Akzeptieren \begin_inset Quotes ard \end_inset bedeutet bei einem Kellerautomaten entweder \begin_inset Quotes ald \end_inset Automat in einem Endzustand \begin_inset Quotes ard \end_inset oder \begin_inset Quotes ald \end_inset leerer Keller \begin_inset Quotes ard \end_inset \layout Itemize \lang german Konstruieren können: nichtdeterminierten Kellerautomaten zu einer informal gegebenen kontextfreien Sprache \begin_inset Formula $L$ \end_inset . Die Umkehrung (Sprache an einem nichtdeterminierten Kellerautomaten erkennen) wurde in der Vorlesung teilweise behandelt, ist aber nicht klausurrelevant. \end_deeper \layout Section \lang german Schnellreferenz zur Klausur \layout Bibliography \bibitem {Kausen-Homepage} \lang german Prof. Dr. Ernst Kausen: Persönliche Homepage. Mit Material zur Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset inkl. einer Inhaltsangabe zur Veranstaltung. Quelle: \begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg8429/} \end_inset \layout Bibliography \bibitem {Kausen-Uebgn} \lang german Prof. Dr. Ernst Kausen: Übungen zur Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset , Sommersemester 2005. Die Übungen zu Abbildungen und Relationen stammen aus einer Mathematikvorlesung von Prof. Kausen aus dem WS 2003/2004 und sind deshalb nicht speziell klausurrelevant. Die restlichen Übungsblätter sind die Übungsblätter identisch mit \begin_inset LatexCommand \cite{Metz-Uebgn} \end_inset . Quelle: \begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg8429/uebungen.html} \end_inset \layout Bibliography \bibitem {Metz-Uebgn} \lang german Prof. Dr. Hans-Rudolf Metz: Übungen zur Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset , Sommersemester 2004. Die Übungen stammen fast alle aus \begin_inset LatexCommand \cite{Sipser} \end_inset . Quelle: \begin_inset LatexCommand \url{http://hera.mni.fh-giessen.de/~hg8070/afs04/afs04.html} \end_inset \layout Bibliography \bibitem {MNI-Wiki-01} \lang german MNI-Wiki: Kausen; Wiki der Fachschaft MNI der FH Gießen-Friedberg. Bisher keine Informationen zur Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset (Stand 2005-09-17). Quelle: \begin_inset LatexCommand \url{http://www.fh-giessen.de/fachschaft/mni/mediawiki/index.php/Kausen} \end_inset \layout Bibliography \bibitem {Hess} \lang german Lena-Luisa Heß: Mitschrift der Vorlesung Automaten und formale Sprachen; 2003-06-30. Studentischer Mitschrieb zu dieser Veranstaltung bei Prof. Dr. Lutz Eichner, FH Gießen-Friedberg. Quelle: \begin_inset LatexCommand \url{http://members.tripod.com/lena_hess/data/skripte/AutomatenUndFormaleSprachen.pdf} \end_inset \layout Bibliography \bibitem {Eichner} \lang german Prof. Dr. Lutz Eichner: Klausuren in Automaten und formale Sprachen. Mit diesen Klausuren zu üben ist auch für die Veranstaltung bei Prof. Kausen sinnvoll: ähnliche Aufgabentypen und klare Aufgabenstellungen. \layout Bibliography \bibitem {Gurari} \lang german Eitan M. Gurari: An Introduction to the Theory of Computation; Ohio State University; Computer Science Press, 1989, ISBN 0-7167-8182-4. Frei online verfügbar. Quelle: \begin_inset LatexCommand \url{http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html} \end_inset \layout Bibliography \bibitem {KindlerManthey} \lang german Ekkart Kindler, Steffen Manthey: Automaten, Formale Sprachen und Berechenbarkeit I; Skript zur Vorlesung im WS 2001/02 an der TU München; Version: 1.30 vom 30. April 2002. 167 Seiten. Quelle: \begin_inset LatexCommand \url{http://wwwcs.uni-paderborn.de/cs/kindler/Lehre/Skripte/Automaten.pdf} \end_inset oder \begin_inset LatexCommand \url{http://wind.in.tum.de/lehre/fospr/WS0102/Skript/SkriptIII.pdf} \end_inset . Ergänzend gibt es auch das handschriftliche Skript in gescannter Form und weitere Unterlagen auf \begin_inset LatexCommand \url{http://wind.in.tum.de/lehre/fospr/WS0102/unterlagen.html} \end_inset . \layout Bibliography \bibitem {Pfitzmann} \lang german Birgit Pfitzmann: Informatik 3 - Ergänzungen zum Skript=Sipser-Buch; Version 11.2.2001. 60 Seiten Ergänzungen zu \begin_inset LatexCommand \cite{Sipser} \end_inset . Quelle: \begin_inset LatexCommand \url{http://www-krypt.cs.uni-sb.de/download/scripts/vorlesung_info3.pdf} \end_inset \layout Bibliography \bibitem {Wilf} \lang german Herbert S. Wilf: Algorithms and Complexity; 1994. 139 Seiten. Zum freien Download verfügbar. Quelle: \begin_inset LatexCommand \url{http://www.cis.upenn.edu/~wilf/AlgComp.html} \end_inset \layout Bibliography \bibitem {Levin} \lang german Leonid A. Levin: Fundamentals of Computing. Quelle: \begin_inset LatexCommand \url{http://www.cs.bu.edu/fac/lnd/toc/} \end_inset \layout Bibliography \bibitem {CT313} \lang german CT 313: Theory of Computation 2001. Quelle: \begin_inset LatexCommand \url{http://www.u-friend.com/lectures/CT313/} \end_inset \layout Bibliography \bibitem {Rodger} \lang german Susan H. Rodger: CPS 140, Spring 1998, Lecture Notes. Quelle: \begin_inset LatexCommand \url{http://www.cs.duke.edu/~rodger/courses/cps140/lecture.html} \end_inset \layout Bibliography \bibitem {Bischof} \lang german Hans-Peter Bischof: Foundations of Computer Science -- CSC 221 -- Spring 1998; 1998. Quelle: \begin_inset LatexCommand \url{http://www.cs.rit.edu/~hpb/Lectures/98_221/all.html} \end_inset \layout Bibliography \bibitem {Sipser} \lang german Michael Sipser: Introduction to the Theory of Computation; Boston 1997. Das Inhaltsverzeichnis befindet sich auf \begin_inset LatexCommand \url{http://www-math.mit.edu/~sipser/itoc-1and2.html} \end_inset . Einige Lösungen zu Übungsaufgaben befinden sich unter \begin_inset LatexCommand \url{http://www.cas.mcmaster.ca/~soltys/cas705-f04/} \end_inset und \begin_inset LatexCommand \url{http://www.cas.mcmaster.ca/~soltys/cas705-f03/} \end_inset . \layout Bibliography \bibitem {OCW-01} \lang german MIT OpenCourseWare: 18.404J / 6.840J Theory of Computation, Fall 2002. Dieser Veranstaltung liegt \begin_inset LatexCommand \cite{Sipser} \end_inset zugrunde. Hier werden online Hausaufgaben-Problemstellungen und eine Klausur angeboten. Dieses Material wurde auch von Prof. Metz für seine Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset genutzt. Quelle: \begin_inset LatexCommand \url{http://ocw.mit.edu/OcwWeb/Mathematics/18-404JTheory-of-ComputationFall2002/CourseHome/index.htm} \end_inset . \layout Bibliography \bibitem {OCW-02} \lang german MIT OpenCourseWare: 6.045J / 18.400J Automata, Computability, and Complexity, Spring 2002. Enthält Aufgabenstellungen und eine Klausursammlung. Dieses Material wurde auch von Prof. Metz für seine Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset genutzt. Quelle: \begin_inset LatexCommand \url{http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-045JAutomata--Computability--and-ComplexitySpring2002/CourseHome/index.htm} \end_inset \layout Bibliography \bibitem {Asteroth} \lang german Alexander Asteroth, Christel Baier: Theoretische Informatik: eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen. Pearson Studium. Auch als eBook verfügbar ( \begin_inset LatexCommand \url{http://www.ciando.com/shop/book/index.cfm/fuseaction/show_book/bok_id/1084/cat_id/68/cat_nav/65} \end_inset oder \begin_inset LatexCommand \url{http://www.bol.de/shop/home/artikeldetails/ID4153439/} \end_inset ), etwa 30 EUR. Vorteil: sofort zum Download verfügbar. Prof. Dr. Metz hat dieses Buch in den Literaturangaben zu seiner Veranstaltung \begin_inset Quotes ald \end_inset Automaten und formale Sprachen \begin_inset Quotes ard \end_inset . \the_end