\documentclass{schuleit}
\usepackage[utf8]{inputenc}
\usepackage{schulinf}
\usepackage{fancybox}

\providecommand\ProgSp{Java\xspace}
%\providecommand\ProgSp{Python\xspace}

% Dieses Dokument ist in der Zusammenarbeit von Informatikreferendaren und
% ehemaligen Informatikreferendaren der Studienseminare (heute ZfsL) Arnsberg,
% Hamm und Solingen entstanden.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% http://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% http://ddi.uni-wuppertal.de/material/materialsammlung/
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter  http://www.ctan.org/pkg/schule
% zur Verfügung.

\usepackage[pdfauthor={Referendare Informatikfachseminare Arnsberg und Hamm}]{hyperref}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\svnid{$Id: leitprogramm_automaten.tex 1570 2016-09-24 11:04:22Z pieper $}

\usepackage{natbib}
\bibpunct{[}{]}{}{a}{}{,~}
\bibliographystyle{dinat}

\usepackage{colortbl, hhline}
\usetikzlibrary{automata}

\usepackage{extarrows}
\usepackage{adjustbox}
\usepackage{todonotes}

% \jahrgang{Q2}

% \renewcommand\sectionmark[1]{\markboth{#1}{}}
% \chead{\leftmark}
% \ohead{Datenbanken}
\renewcommand{\ttdefault}{pcr}

\lstset{% 
	breaklines=true, % Zeilenumbrüche
	language=SQL, % Sprache
	basicstyle=\ttfamily,
	breakindent=1pt,
	breakatwhitespace=true,
	breakautoindent=false,
	tabsize=2,
	morekeywords={double,text,show,tables,use,is,truncate,rename,to,after,change},
	% numbers=left, numberstyle=\tiny,  numbersep=5pt,
	prebreak={} % Zeichen am Zeilenende (Umbruch)
}

\definecolor{Gray}{gray}{0.9}

% \makeatletter% siehe FAQ (aber wirklich nachsehen!)
% \newcommand*{\headingpar}{\par\nobreak\@afterheading}
% \makeatother% siehe FAQ

% \newcommand{\AufgabenHinweis}[1]{}

\newcommand{\monatWort}[1]{%
\ifcase #1
 Monat 0 \or Januar \or Februar \or März  \or April \or Mai \or Juni \or Juli%
 \or August \or September \or Oktober \or November \or Dezember\fi}

\begin{document}
	\begin{titlepage}
		\begin{center}
			\begin{Large}
				Leitprogramm
			\end{Large}
		\end{center}

		\begin{center}
			\begin{huge}
				\textbf{Automaten, Sprachen, Grammatiken und reguläre Ausdrücke}
			\end{huge}
		\end{center}

		\begin{center}
			Stand \svnday. \monatWort{\svnmonth} \svnyear 
		\end{center}

		\tableofcontents

	\end{titlepage}

\chapter{Vorwort}
Eine alltägliche Bedeutung der Begriffe Automaten und Sprachen ist jeder Schülerin und jedem Schüler einer gymnasialen Oberstufe klar. %Zumindest würde man dieses denken. 
Im Bereich der theoretischen Informatik haben diese beiden Wörter eine andere Bedeutung und beschreiben jeweils ein abstraktes Konstrukt. So geht es besonders im Bereich der Automaten nicht primär darum, wie ein Ticketautomat oder ein Geldautomat programmiert wird. Vielmehr dienen Automaten im Zusammenhang mit der Automatentheorie als Grundlage für Beschreibungen und theoriegeleitete Aussagen über Klassen von Automaten, ihre prinzipiellen Möglichkeiten und grundsätzliche Grenzen, die auch formal nachgewiesen werden können.
%viele Beweise innerhalb der Informatik. 

In diesem Leitprogramm geht es zunächst um sogenannte endliche Automaten mit Ein- und Ausgabe. Daran anschließend geht es um solche Automaten, die eine Sprache akzeptieren, wie sie von 
%Grammatiken oder 
% Grammatiken ist der allgemeinere Begriff 
regulären Ausdrücken aufgestellt werden. Hierbei werden zwei weitere Arten unterschieden, bei denen sich zeigen lässt, dass die gleichwertig sind. Von den 
%Grammatiken über 
regulären Ausdrücken mit möglichen Anwendungen wird ein besonderer Blick auf den Begriff der Sprache geworfen. Zum Abschluss gibt es einen Ausblick zu den Kellerautomaten und der Turingmaschine, die beide keine endlichen Automaten sind.

\chapter[Transduktoren]{Automaten mit Ein- und Ausgabe (Transduktoren)}
In der Automatentheorie werden zwei Arten von Automaten unterschieden. Automaten, die neben der Eingabe auch eine Ausgabe haben, werden als Transduktoren bezeichnet. Sie kommen real existierenden Automaten nah. Daher soll zu Beginn auch ein solcher realer Automat betrachtet werden: Der Schrankenautomat an der Ausfahrt des Parkplatzes des Münsterraner Zoos.

\begin{figure}[ht]
	\centering
	\includegraphics[width=0.4\textwidth]{parkautomat}
	\caption{Schrankenautomat des Münsterraner Zoos}
\end{figure}

Dieser Automat steuert die Schranke, indem er sie nach passender Bezahlung öffnet und nach der Durchfahrt eines Autos wieder schließt. Danach muss erneut die passende Bezahlung geleistet werden, damit der Automat die Schranke wieder öffnet.

Die Beschreibung (Automatenmodellierung) eines theoretischen Automaten setzt sich aus mehreren Angaben zusammen. Bei einigen dieser Angaben werden mehrere Elementen angegeben. Wie in der Mathematik bezeichnet man eine solche Sammlung von Elementen als Menge. Ein Automat ist nur dann vollständig angegeben, wenn alle Angaben zu ihm aufgelistet werden. Zwei dieser Angaben sind die Eingabemenge \(\Sigma\) und die Ausgabemenge~\(A\). Dabei zählt man alle möglichen einzelnen Eingaben und Ausgaben des Automaten auf.

\begin{Aufgaben}
	\item Zählen Sie alle möglichen einzelnen Eingaben auf, die an den Schrankenautomaten gestellt werden können.
	\AufgabenHinweis{Jede Eingabe löst im Automaten eine Aktion aus. Also schreiben Sie alle diese Möglichkeiten auf, wie z.\,B. den Einwurf einer 1~Euro~Münze.}
	\TextFeld{2cm}

	\item Zählen Sie auch alle Ausgaben des Automaten auf. Als Ausgabe wird dabei auch das bezeichnet, was eine Benutzerin oder ein Benutzer sehen kann.
	\AufgabenHinweis{Denken Sie dabei neben der Anzeige auch an die Schranke selber und die Geldrückgabe.}
	\TextFeld{2cm}
\end{Aufgaben}

Welche Eingabe beim Automaten erfolgt ist, speichert dieser durch den Wechsel in einen entsprechenden (häufig anderen) Zustand. Die Namen aller Zustände, auch als Zustandsmenge \(Z\) bezeichnet, gehört dabei mit zu den Angaben eines Automaten, wie auch die Regeln, wann in welchen Zustand gewechselt werden soll. Die Benennung der Zustände eines Automaten ist nicht einheitlich geregelt. Oft werden sie durchnummeriert oder bekommen einen Buchstaben mit durchnummerierten Indizes. In diesem Dokument werden bis auf besondere Ausnahmen alle Zustände mit \(s_1\), \(s_2\) usw. bezeichnet.

Die Regeln des Automaten werden durch die Zustandsübergangsfunktion \(\varphi\) beschrieben. Diese wird üblicherweise graphisch in einem Zustandsübergangsdiagramm oder tabellarisch in einer Zustandsübergangstabelle dargestellt. Zur Erläuterung der graphischen Darstellung wird nur eine Schranke mit der Einwurfmöglichkeit einer Parkmünze betrachtet. Bei dieser öffnet sich die Schranke, sobald die Parkmünze eingeworfen wurde. Ist anschließend das Auto durchgefahren, so schließt sich die Schranke wieder. Die Zustände des Automaten werden dabei mit Kreisen dargestellt und die Übergänge mit Pfeilen. Die Eingaben und Ausgaben werden dabei an die Pfeile geschrieben. Gibt es sowohl Ein- als auch Ausgaben, so werden diese durch einen Schrägstrich getrennt. Außerdem ist es üblich, die Namen abzukürzen. In unserem Fall steht PM für \enquote{Parkmünze}, Ad für \enquote{Auto durchgefahren}, Sa für \enquote{Schranke auf} und Sz für \enquote{Schranke zu}. Der mit \enquote{start} markierte Pfeil an den Zustand \(s_1\) zeigt an, in welchem Zustand der Automat beginnt. In anderen Darstellungen kann dieses auch ein Pfeil ohne Bezeichnung sein. Dieser Startzustand \(z_0\) gehört mit zu den nötigen Angaben eines Automaten.

\begin{figure}[ht] 
	\centering
	\begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
		\node[state,initial]	(s_1) {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\path[->] 
			(s_1)  edge[bend left] node[above] {PM/Sa} (s_2)
			(s_2)  edge[bend left] node[above] {Ad/Sz} (s_1);
	\end{tikzpicture}
	\caption{Zustandsübergangsdiagramm eines Parkschrankenautomaten nur mit Park\-mün\-ze} \label{Schranke_Parkmuenze}
\end{figure}

In der tabellarischen Darstellung stehen in der obersten Zeile alle möglichen Eingaben. Die möglichen Zustände sind in der vordersten Spalte zu finden. So kann den Zellen entnommen werden, welcher neue Zustand und welche Ausgabe zu jeder Eingabe mit dem vorherigen Zustand gehören.

\begin{table}[ht]
	\centering
	\begin{tabular}{l||l|l}
		& PM & Ad \\ \hline \hline
		\(s_1\) & \(s_2\)/Sa & \\ \hline
		\(s_2\) & & \(s_1\)/Sz \\
	\end{tabular}
	\caption{Zustandsübergangstabelle eines Parkschrankenautomaten nur mit Park\-mün\-ze}
\end{table}

\begin{Aufgaben}
	\item Geben Sie die Zustandsmenge \(Z\) des Automaten für die Parkschranke an, der die von Ihnen angegebene Eingabemenge nutzt.
	\TextFeld{0.7cm}

	\item Geben Sie den zur Zustandsmenge \(Z\) zugehörigen Startzustand \(z_0\) des Parkschrankenautomaten an.
	\TextFeld{0.5cm}

	\item Erstellen Sie ein Zustandsübergangsdiagramm, dass die Zustandsübergangsfunktion \(\varphi\) angibt.
	\AufgabenHinweis{An dieser Stelle soll der vorstellte Automat so erweitert werden, dass er auch die Geldmünzen verarbeiten kann.}
	\AufgabenLoesung{Die Lösung wird im Text darunter vorgestellt.}
	\TextFeld{3.5cm}
\end{Aufgaben}

\newpage

Bei der Angabe der Mengen wird die Mengenschreibweise der Mathematik verwendet. Dabei werden alle Elemente innerhalb von geschweiften Klammern geschrieben. Die Beschreibung des gesamten Automaten \((\Sigma, A, Z, z_0, \varphi)\) sieht damit wie folgt aus:

\begin{figure}[ht]
	\(\Sigma = \{\mbox{PM, Ad, 1, 2}\} \)\\
	\(A = \{\mbox{2, 1, Sa, Sz\_3}\}\)\\
	\(Z = \{s_1, s_2, s_3, s_4\}\)\\
	\(z_0 = s_1\)\\
	\(\varphi = \)\\
	\hspace*{0.7cm}
	\begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
		\node[state,initial]	(s_1) {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state]	(s_3) [right=of s_2]  {$s_3$};
		\node[state]	(s_4) [right=of s_3]  {$s_4$};
		\path[->] 
			(s_1) edge[bend left=45] node[above] {PM/Sa} (s_4)
			(s_4) edge[bend left=50] node[below] {Ad/Sz\_3} (s_1)
			(s_1) edge node[above] {1/2} (s_2)
			(s_2) edge[bend left=25] node[above] {2/Sa} (s_4)
			(s_2) edge node[above] {1/1} (s_3)
			(s_3) edge node[above] {1/Sa} (s_4)
			(s_1) edge[bend right] node[above] {2/1} (s_3)
			(s_3) edge[bend right=40] node[above] {2/Sa} (s_4);
	\end{tikzpicture}
	\caption{Kompletter Parkscheinautomat}
\end{figure}

Wenn man sich diese Lösung ansieht, so fällt auf, dass bei der Eingabemenge und der Ausgabemenge gleiche Symbole verwendet werden. So geben die Zahlen bei der Eingabemenge die entsprechenden Geldstücke an. Bei der Ausgabe entsprechen die Zahlen der Anzeige. Dadurch bedingt werden nach dem Durchfahren des Autos zwei Sachen gleichzeitig getätigt: Die Schranke schließt sich und die Anzeige geht zurück auf 3. Dieses muss aber in einer Ausgabe \enquote{Sz\_3} zusammengefasst werden.

\section{Ticketautomat}
Um das Verständnis für solche Automaten zu stärken, wird als zweites Beispiel ein einfacher Ticketautomat betrachtet. Dieser gibt nach dem Einwurf von 2,50~Euro ein Ticket aus. Wird mehr gezahlt, so gibt er zum Ticket auch das passende Rückgeld mit aus. Er soll keine Anzeige der bisher gezahlten Summe erhalten. Gezahlt werden kann nur mit 1~Euro, 2~Euro oder 50~Cent Münzen. 

\begin{Aufgaben}
	\item Erstellen Sie die vollständige Darstellung eines Automaten, der der obigen Beschreibung entspricht.
	\AufgabenHinweis{Wenn auf eine Eingabe keine Ausgabe kommt, so kann man dieses auch mit einem waagerechten Strich deutlich machen.}
	\AufgabenLoesung{Erfolgt keine Ausgabe, so wird dieses mit einem waagerechten Strich deutlich gemacht. Die Semikolons in den Mengen wurden verwendet, da Kommata bereits in den einzelnen Elementen Verwendung finden.
		\begin{figure}[ht]
			\(\Sigma = \{\mbox{0,5; 1; 2}\} \)\\
			\(A = \{\mbox{-; T; T\_0,5; T\_1; T\_1,5;}\}\)\\
			\(Z = \{s_0, s_{0,5}, s_1, s_{1,5}, s_2\}\)\\
			\(z_0 = s_0\)\\
			\(\varphi = \)\\
			\hspace*{0.7cm}
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
				\scaleTikz{0.8}
				\node[state,initial]	(s_00) {$s_{0}$};
				\node[state]	(s_05) [right=of s_00]  {$s_{0,5}$};
				\node[state]	(s_10) [right=of s_05]  {$s_{1}$};
				\node[state]	(s_15) [right=of s_10]  {$s_{1,5}$};
				\node[state]	(s_20) [right=of s_15]  {$s_{2}$};
				\path[->] 
					(s_00) edge node[above] {0,5/-} (s_05)
					(s_05) edge node[above] {0,5/-} (s_10)
					(s_10) edge node[above] {0,5/-} (s_15)
					(s_15) edge node[above] {0,5/-} (s_20)
					
					(s_00) edge[bend left] node[above] {1/-} (s_10)
					(s_05) edge[bend left] node[above] {1/-} (s_15)
					(s_10) edge[bend left] node[above] {1/-} (s_20)
					
					(s_00) edge[bend left=35] node[above] {2/-} (s_20)

					(s_20) edge[bend left=45] node[above] {0,5/T} (s_00)
					(s_20) edge[bend left=60] node[above] {1/T\_0,5} (s_00)
					(s_20) edge[bend left=80] node[above] {2/T\_1,5} (s_00)
					
					(s_15) edge[bend left=30] node[above] {1/T} (s_00)
					(s_15) edge[bend left=45] node[above] {2/T\_1} (s_00)

					(s_10) edge[bend left=30] node[above] {2/T\_0,5} (s_00)
					
					(s_05) edge[bend left=30] node[above] {2/T} (s_00);
			\end{tikzpicture}
			\caption{Lösung für den Ticketautomat}
		\end{figure}
	}
	\TextFeld{9cm}

	\item Erläutern Sie, weshalb der Automat nicht verändert werden muss, wenn Sie die Anzeige des bisher bezahlten Betrags realisieren möchten.
	\AufgabenHinweis{Der Automat enthält bereits an die Information, welcher Betrag gezahlt wurde.}
	\AufgabenLoesung{In den Zuständen ist gespeichert, welcher Betrag bereits gezahlt wurde. Daher könnte man eine Anzeige direkt mit den Zuständen verknüpfen.}
	\TextFeld{1cm}
\end{Aufgaben}

\section{Fehler bei der Eingabe}
Beim Parkschrankenautomaten wird davon ausgegangen, dass bei bestimmten Zuständen nur spezielle Eingaben folgen. Besonders bei dem folgenden Kapitel zu den Akzeptoren werden solche Annahmen gemacht. Doch was passiert, wenn eine andere Eingabe vorgenommen wird? Das beste Beispiel dafür wäre, dass ohne Einwurf passender Münzen und bei geschlossener Schranke das Auto durch fährt. Dazu wird der Automat noch einmal betrachtet, bei dem nur eine Parkmünze zum Öffnen der Schranke erlaubt war (Abbildung~\ref{Schranke_Parkmuenze}). Bezieht man diesen Fall auf die Realität, so wird jedem schnell klar, die Schranke ist anschließend defekt. Diesen überträgt man auch auf die Automaten. Sie bekommen einen zusätzlichen \enquote{Fehlerzustand}. In diesen führen alle Eingaben, die keinen anderen Übergang von dem betrachteten Zustand aus haben. Aus diesem Zustand kommt man anschließend aber auch nicht mehr heraus. Die oben betrachtete Zustandsübergangsfunktion würde im Diagramm dann so aussehen:
\begin{figure}[ht]
	\centering
	\begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
		\node[state,initial]	(s_1) {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state]	(f) [below=of s_1]  {$s_f$};
		\path[->] 
			(s_1)  edge[bend left] node[above] {PM/Sa} (s_2)
			(s_2)  edge[bend left] node[above] {Ad/Sz} (s_1)
			(s_1)  edge node[left] {Ad/-} (f)
			(s_2)  edge node[right] {PM/-} (f)
			(f) edge[loop right] node[right] {Ad,PM/-} ();
	\end{tikzpicture}
	\caption{Parkautomat nur mit Parkmünze incl. Fehlerzustand}
\end{figure}

Durch diesen Fehlerzustand wird ein Automat, besonders in der Zeichnung, sehr aufgebläht. Auch die Übersichtlichkeit kann dadurch verloren gehen. Deshalb ist es üblich auf den Fehlerzustand in der Darstellung der Zustandsübergangsfunktion zu verzichten. 

\begin{Aufgabe}
	Betrachten Sie die Lösung des Schrankenautomaten. Welche weiteren Fälle von Eingaben wurden bei diesem nicht betrachtet. Geben Sie mit an, ob bei diesen Fällen der Übergang in den \enquote{Fehlerzustand} sinnvoll ist.
	\AufgabeLoesung{Betrachtet wurden alle Fälle nicht, bei denen erst Geld und anschließend die Parkmünze eingeworfen wurde. Auch die Fälle, in denen die Schranke geöffnet ist und Geld bzw. die Parkmünze eingeworfen wird, sind nicht eingebaut. Für diese Fälle ist es eher sinnvoll, die Zustandsübergangsfunktion zu erweitern.}
	\TextFeld{2cm}
\end{Aufgabe}

\chapter[Akzeptoren]{Akzeptierende Automaten (Akzeptoren)}
Die zweite Art von Automaten wird als Akzeptoren bezeichnet. Sie haben im Gegensatz zu Transduktoren keine Ausgabe, sondern ihre Aufgabe besteht darin, die nacheinander erfolgten Eingaben und ihre Reihenfolge daraufhin zu überprüfen, ob diese korrekt ist. Dieses lässt sich daran erkennen, wenn sich der Automat nach der vollständigen Eingabe in einem sogenannten akzeptierten Zustand befindet. Dabei können auch mehrere Zustände am Ende akzeptiert werden, so dass man von der Menge der akzeptierten Endzustände \(E\) spricht.

Als Beispiel soll hier ein Akzeptor für Klassenbezeichner betrachtet werden. Dieser soll prüfen, ob die Eingabe, die gemacht wird, die Konvention für Klassenbezeichner erfüllt. 

\begin{figure}[ht]
	\(\Sigma = \{\mbox{A, \ldots, Z, a, \ldots, z, 0, \ldots, 9}\} \)\\
	\(Z = \{s_0, s_1\}\)\\
	\(z_0 = s_0\)\\
	\(E = \{s_1\}\)\\
	\(\varphi = \)\\
	\hspace*{0.7cm}
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
		\node[state,initial]	(s_0) {$s_0$};
		\node[state,accepting]	(s_1) [right=of s_0]  {$s_1$};
		\path[->] 
			(s_0) edge node[above] {A..Z} (s_1)
			(s_1) edge[loop right] node[right] {a..z,A..Z,0..9} ();
	\end{tikzpicture}
	\caption{Akzeptor für Klassenbezeichner} \label{Akzeptor_Klassenbezeichner}
\end{figure}

Wie in der Graphik zu erkennen, werden die akzeptierten Endzustände durch einen doppelten Kreis deutlich gemacht. Außerdem werden bei den Buchstaben Abkürzungen genutzt, um nicht alle einzelnen Zeichen aufschreiben zu müssen. Bei dem Übergang von \(s_1\) zu sich selbst hätte man auch ein \(\Sigma\) an den Pfeil schreiben können, um zu verdeutlichen, dass hier alle Elemente der Eingabemenge zulässig sind. Teilweise findet man dafür in einigen Diagrammen auch ein Asterisk (*). 

\begin{Aufgaben}
	\item Beschreiben Sie die Konvention für Klassenbezeichner anhand des abgebildeten Akzeptors.
	\AufgabenLoesung{Die Eingabe muss mit einem Großbuchstaben beginnen und darf anschließend nur weitere Buchstaben und Ziffern, aber keine Sonderzeichen enthalten. Die Groß- und Kleinschreibung ist bei den weiteren Zeichen nicht von Bedeutung.}
	\TextFeld{1cm}

	\item Gegeben ist das Zustandsübergangsdiagramm eines Akzeptors. 
		
		\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
			\node[state,initial]	(s_0) {$s_0$};
			\node[state]	(s_1) [right=of s_0]  {$s_1$};
			\node[state]	(s_2) [right=of s_1]  {$s_2$};
			\node[state,accepting]	(s_3) [right=of s_2]  {$s_3$};
			\node[state]	(s_4) [below=of s_1]  {$s_4$};
			\node[state,accepting]	(s_5) [right=of s_4]  {$s_5$};
			\path[->] 
				(s_0) edge node[above] {0} (s_1)
				(s_1) edge node[above] {x} (s_2)
				(s_2) edge node[above] {A..F,1..9} (s_3)
				(s_3) edge[loop below] node[below] {A..F,0..9} ()

				(s_0) edge node[left] {A..F,1..9} (s_4)
				(s_4) edge node[above] {h} (s_5)

				(s_4) edge[loop below] node[below] {A..F,0..9} ()

				(s_1) edge node {h} (s_5)
				(s_2) edge node {0} (s_5);
		\end{tikzpicture}
	
		Geben Sie die Eingabemenge und die Menge der akzeptierten Endzustände an. Erläutern Sie außerdem, welche Eingaben von dem Automaten akzeptiert werden.
	\AufgabenHinweis{Der Akzeptor überprüft zwei Schreibweisen eines besonderen Zahlensystems}
	\AufgabenLoesung{Die Eingabemenge ist \(\Sigma =\{\mbox{A, \ldots, F, 0, \ldots, 9, x, h}\} \) und die Endzustände sind \(E = \{s_3, s_5\}\). Der Automat akzeptiert die beiden Schreibweisen für hexadezimale Zahlen, die entweder mit einem 0x beginnen oder mit einem h enden. Dabei sind keine führenden Nullen zugelassen. Die Null selber aber schon.}
	\TextFeld{2cm}

	\item Erstellen Sie einen Akzeptor, der überprüft, ob eine Eingabe eine gültige Kombination aus Vor- und Nachname darstellt. Sonderzeichen müssen dabei nicht berücksichtigt werden.
	\AufgabenHinweis{Stellen Sie zuerst einfache Regeln auf, anhand derer überprüft werden kann, ob es ein gültiger Name ist. Nehmen sie dabei gültige und nicht gültige Beispiele. So sollten \enquote{Hermman Hesse}, \enquote{Ludwig van Beethoven} und \enquote{Luisa Maria Peters} akzeptiert werden. Diese Fälle aber nicht: \enquote{Gustav}, \enquote{MArtin Mars} und \enquote{von Beethoven, Ludwig}.}
	\AufgabenLoesung{
		Der Akzeptor muss nur prüfen, ob mindestens zweimal mehrere Zeichen hintereinander hängen und durch ein Leerzeichen getrennt sind. Dabei darf nur der erste Buchstabe jeweils groß sein. In der Mitte dürfen auch noch weitere Zeichen aneinander hängen, die komplett klein geschrieben sind.

		Für die bessere Lesbarkeit ist das Leerzeichen durch ein \_ im folgenden Automaten ersetzt worden.
		\begin{figure}[ht]
			\(\Sigma = \{\mbox{\_, A, \ldots, Z, a, \ldots, z}\} \)\\
			\(Z = \{s_1, s_2, s_3, s_4\}\)\\
			\(z_0 = s_0\)\\
			\(E = \{s_3\}\)\\
			\(\varphi = \)\\
			\hspace*{0.7cm}
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
% 				\scaleTikz{0.8}
				\node[state,initial]	(s_0) {$s_0$};
				\node[state]	(s_1) [right=of s_0]  {$s_1$};
				\node[state]	(s_2) [right=of s_1]  {$s_2$};
				\node[state,accepting]	(s_3) [right=of s_2]  {$s_3$};
				\node[state]	(s_4) [below=of s_2]  {$s_4$};
				\path[->] 
					(s_0) edge node[above] {A..Z} (s_1)
					(s_1) edge[loop below] node[below] {a..z} ()
					(s_1) edge node[above] {\_} (s_2)
					(s_2) edge[bend left] node[above] {A..Z} (s_3)
					(s_2) edge[bend left] node[right] {a..z} (s_4)
					(s_3) edge[bend left] node[below] {\_} (s_2)
					(s_4) edge[bend left] node[left] {\_} (s_2)
					(s_3) edge[loop below] node[below] {a..z} ();
			\end{tikzpicture}
			\caption{Lösung für den Namensakzeptor}
		\end{figure}
	}
	\TextFeld{5cm}
\end{Aufgaben}

\section{Endlicher Automat}
Wird in der Informatik von einem Automaten gesprochen, so meint man in den meisten Fällen einen endlichen Automaten. Diesen Namen haben die Automaten durch ihre endliche Anzahl an möglichen Zuständen. Es ist also möglich, für jeden endlichen Automaten anzugeben, wie viele Zustände er hat. Somit handelt es sich auch bei allen bisher diskutierten Automaten um endliche Automaten.

Die Endlichkeit der Automaten hat größere Auswirkungen, als man im ersten Moment vermuten würde. Sie beschränkt die Möglichkeiten der Automaten in einem besonderen Maße. Alle Zählaufgaben sind nur eingeschränkt möglich, denn für jeden Zählschritt, der durchgeführt werden soll, muss ein einzelner Zustand existieren. Verdeutlicht werden soll dies an einem Automaten, der das Vorkommen aller Neunen in einer Zahl abzählt:

\begin{figure}[ht]
	\centering
	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
		\node[state,initial,accepting]	(s_0) {$s_0$};
		\node[state]	(s_1) [right=of s_0]  {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state]	(s_3) [right=of s_2]  {$s_3$};
		\node[state, color = white]	(s_4) [right=of s_3]  {\color{black}\ldots};
		\path[->] 
			(s_0) edge node[above] {9} (s_1)
			(s_0) edge[loop below] node[below] {0..8} ()
			(s_1) edge node[above] {9} (s_2)
			(s_1) edge[loop below] node[below] {0..8} ()
			(s_2) edge node[above] {9} (s_3)
			(s_2) edge[loop below] node[below] {0..8} ()
			(s_3) edge node[above] {9} (s_4)
			(s_3) edge[loop below] node[below] {0..8} ();
	\end{tikzpicture}
	\caption{Beispiel für einen unendlichen Automaten}
\end{figure}

Anhand der Nummer des Zustandes kann man die Anzahl ablesen. Da es keine Beschränkung der Länge der übergebenen Zahl gibt, benötigt der Automat unendlich viele Zustände, um seine Aufgabe voll erfüllen zu können.

\begin{Aufgaben}
	\item Ein weiteres Beispiel für die Einschränkung eines endlichen Automaten ist ein Akzeptor, der überprüft, dass es zu jeder öffnen Klammer auch eine schließende gibt. Erstellen Sie das Zustandsübergangsdiagramm für einen Automaten, der bis zu einer Klammerungstiefe von drei dieses überprüfen kann.
	\AufgabenHinweis{Überlegen Sie genau, was bei einer schließenden Klammer zu beachten ist. Nehmen Sie zum Testen auch Beispiele wie (x(x)x((x)x))(x).}
	\AufgabenLoesung{
		Bei der Lösung sind die Klammern unterstrichen, um deutlich zu machen, dass es sich hierbei um Eingabesymbole handelt.
		\begin{figure}[ht]
			\centering
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
				\node[state,initial,accepting]	(s_0) {$s_0$};
				\node[state]	(s_1) [right=of s_0]  {$s_1$};
				\node[state]	(s_2) [right=of s_1]  {$s_2$};
				\node[state]	(s_3) [right=of s_2]  {$s_3$};
				\path[->] 
					(s_0) edge[bend left] node[above] {\underline{(}} (s_1)
					(s_0) edge[loop above] node[above] {\(\Sigma\) - \{\underline{(},\underline{)}\}} ()
					(s_1) edge[bend left] node[above] {\underline{)}} (s_0)
					(s_1) edge[bend left] node[above] {\underline{(}} (s_2)
					(s_1) edge[loop above] node[above] {\(\Sigma\) - \{\underline{(},\underline{)}\}} ()
					(s_2) edge[bend left] node[above] {\underline{)}} (s_1)
					(s_2) edge[bend left] node[above] {\underline{(}} (s_3)
					(s_2) edge[loop above] node[above] {\(\Sigma\) - \{\underline{(},\underline{)}\}} ()
					(s_3) edge[bend left] node[above] {\underline{)}} (s_2);
			\end{tikzpicture}
			\caption{Akzeptor für eine korrekte Klammerung bis zur Tiefe von drei.}
		\end{figure}
	}
	\TextFeld{1cm}

	\item Zeichnen Sie das Zustandsübergangsdiagramm zu einem Automaten, der eine beliebige Klammertiefe verarbeiten kann. Orientieren Sie sich dabei an der vorherigen Lösung und erklären Sie, weshalb diese Anforderung nicht mit einem endlichen Automaten realisiert werden kann.
	\AufgabenLoesung{
		Die Lösung für den Automaten sieht dem Automaten für eine fest Klammerungstiefe sehr ähnlich:
		\begin{figure}[ht]
			\centering
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
				\node[state,initial,accepting]	(s_0) {$s_0$};
				\node[state]	(s_1) [right=of s_0]  {$s_1$};
				\node[state]	(s_2) [right=of s_1]  {$s_2$};
				\node[state]	(s_3) [right=of s_2]  {$s_3$};
				\node[state, color = white]	(s_4) [right=of s_3]  {\color{black}\ldots};
				\path[->] 
					(s_0) edge[bend left] node[above] {\underline{(}} (s_1)
					(s_0) edge[loop above] node[above] {\(\Sigma\) - \{\underline{(},\underline{)}\}} ()
					(s_1) edge[bend left] node[above] {\underline{)}} (s_0)
					(s_1) edge[bend left] node[above] {\underline{(}} (s_2)
					(s_1) edge[loop above] node[above] {\(\Sigma\) - \{\underline{(},\underline{)}\}} ()
					(s_2) edge[bend left] node[above] {\underline{)}} (s_1)
					(s_2) edge[bend left] node[above] {\underline{(}} (s_3)
					(s_2) edge[loop above] node[above] {\(\Sigma\) - \{\underline{(},\underline{)}\}} ()
					(s_3) edge[bend left] node[above] {\underline{)}} (s_2)
					(s_3) edge[bend left] node[above] {\underline{(}} (s_4)
					(s_4) edge[bend left] node[above] {\underline{)}} (s_3);
			\end{tikzpicture}
			\caption{Zustandsübergangsdiagramm für einen unendlichen Automaten, der die korrekte Klammerung überprüft}
		\end{figure}
		Der wichtige Unterschied zwischen den beiden Automaten besteht in diesem, dass bei ihm nicht vorher angegeben werden kann, wie viele Zustände benötigt werden, da für jede Stufe der Klammerung ein weiterer Zustand benötigt wird. Es handelt sich deshalb um keinen endlichen Automaten.
	}
	\TextFeld{3cm}

	\item Diskutieren Sie, ob es sich bei einem Computer um einen endlichen Automaten handelt.
	\AufgabenHinweis{Stellen Sie verschiedene Aspekte bei einem Computer gegenüber. Betrachten Sie dabei auch den Compiler für eine beliebige Programmiersprache, der auf einem Computer ausgeführt werden kann. Vor der eigentlichen Übersetzung in ein maschinenlesbares Programm, wird in der Regel die Syntax des Quellcodes überprüft.}
	\AufgabenLoesung{Vom Prinzip her handelt es sich bei einem Computer um einen unendlichen Automaten. Dieses lässt sich auch daran festmachen, dass bei Programmen die korrekte Klammerung unabhängig von der Klammerungstiefe geprüft werden kann. Auch andere Zählungen sind ohne größere Probleme möglich. Beachtet man aber, dass der Zustand eines Automaten eine mögliche Belegung des Speichers darstellt, ist der Computer kein unendlicher Automat. Dieses liegt daran, dass bei jedem Computer der Speicher beschränkt ist und damit auch die Möglichkeiten, wie der Speicher genutzt wird.}
	\TextFeld{1cm}
\end{Aufgaben}

\section[DEA und NEA]{Deterministischer und nicht deterministischer endlicher Automat}
Einen Akzeptor zu entwickeln, der alle gewünschten Eigenschaften hat, ist teilweise nicht einfach. Als Beispiel soll hier die Erkennung aller Wörter dienen, die auf \enquote{ter} enden. Eine einfache Lösung dafür sieht wie folgt aus:

\begin{figure}[ht]
	\centering
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
		\node[state,initial]	(s_0) {$s_0$};
		\node[state]	(s_1) [right=of s_0]  {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state,accepting]	(s_3) [right=of s_2]  {$s_3$};
		\path[->] 
			(s_0) edge[bend left] node[above] {t} (s_1)
			(s_0) edge[loop above] node[above] {\(\Sigma\) - \{t\}} ()
			(s_1) edge[bend left] node[above] {e} (s_2)
			(s_1) edge[bend left] node[above] {\(\Sigma\) - \{e\}} (s_0)
			(s_2) edge[bend left] node[above] {r} (s_3)
			(s_2) edge[bend left=45] node[above] {\(\Sigma\) - \{r\} } (s_0)
			(s_3) edge[bend left=60] node[above] {\(\Sigma\)} (s_0);
	\end{tikzpicture}
	\caption{Zustandsübergangsdiagramm eines Akzeptors für alle Wörter, die auf \enquote{ter} enden}
\end{figure}

\begin{Aufgabe}
	Testen Sie den oben angegebenen Akzeptor an folgenden Wörtern auf seine Korrektheit:
	Peter, Peterson, Wetter und lauter. Geben Sie zu jedem Zustandsübergang den entsprechenden Buchstaben und nächsten Zustand an.
	\AufgabeLoesung{
		Wie den folgenden Lösungen zu entnehmen ist, werden nicht alle Fälle korrekt erkannt:

		Peter: \(0 \xLongrightarrow{\text{P}} 0 \xLongrightarrow{\text{e}} 0 \xLongrightarrow{\text{t}} 1 \xLongrightarrow{\text{e}} 2 \xLongrightarrow{\text{r}} 3 \)\\
		Peterson: \(0 \xLongrightarrow{\text{P}} 0 \xLongrightarrow{\text{e}} 0 \xLongrightarrow{\text{t}} 1 \xLongrightarrow{\text{e}} 2 \xLongrightarrow{\text{r}} 3  \xLongrightarrow{\text{s}} 0 \xLongrightarrow{\text{o}} 0  \xLongrightarrow{\text{n}} 0\) \\
		Wetter: \(0 \xLongrightarrow{\text{W}} 0 \xLongrightarrow{\text{e}} 0 \xLongrightarrow{\text{t}} 1  \xLongrightarrow{\text{t}} 0 \xLongrightarrow{\text{e}} 0 \xLongrightarrow{\text{r}} 0 \) \\
		lauter: \(0 \xLongrightarrow{\text{l}} 0 \xLongrightarrow{\text{a}} 0  \xLongrightarrow{\text{u}} 0 \xLongrightarrow{\text{t}} 1 \xLongrightarrow{\text{e}} 2 \xLongrightarrow{\text{r}} 3 \)
	}
	\TextFeld{4cm}
\end{Aufgabe}

Die Lösung der obigen Aufgabe zeigt, dass der angegebene Automat nicht in der Lage ist, alle Wörter korrekt zu erkennen. So sorgt beim Fall von Wetter die Kombination aus den doppelten t dafür, das aus dem Zustand \(s_1\) wieder in den Zustand \(s_0\) gewechselt wird. Dadurch werden die folgenden Buchstaben nicht wie gewünscht verarbeitet.

Zur Lösung dieses Problems bietet sich ein anderer Akzeptor an, der auch als nicht deterministischer Automat (NEA) bezeichnet wird:
\begin{figure}[ht]
	\centering
		\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
		\node[state,initial]	(s_0) {$s_0$};
		\node[state]	(s_1) [right=of s_0]  {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state,accepting]	(s_3) [right=of s_2]  {$s_3$};
		\path[->] 
			(s_0) edge node[above] {t} (s_1)
			(s_0) edge[loop above] node[above] {\(\Sigma\)} ()
			(s_1) edge node[above] {e} (s_2)
			(s_2) edge node[above] {r} (s_3);
	\end{tikzpicture}
	\caption{Zustandsübergangsdiagramm eines nicht deterministischen Automaten für alle Wörter, die auf \enquote{ter} enden}
	\label{nea_ter}
\end{figure}

Ein solcher NEA hat eine ganz besondere Eigenschaft: Er kann in mehreren Zuständen gleichzeitig sein. So wechselt er beim Wort \enquote{Wetter} mit dem ersten t gleichzeitig in den Zustand \(s_0\) und \(s_1\). Dadurch hat er die Möglichkeit beim folgenden t wieder korrekt in den Zustand \(s_1\) zu wechseln. 

\begin{Hinweis}
	Zum besseren Verständnis kann man einen NEA auch als Automat mit einem Orakel bezeichnen. Dieses sagt dem Automaten, wann es bei einer Eingabe welche Zustandsänderung machen soll. Durch das Vorausschauen in die Zukunft wählt der Automat so die richtigen Übergänge um korrekte Eingaben auch zu akzeptieren.
\end{Hinweis}

Der Begriff Determinismus kommt aus dem Lateinischen lässt sich mit \enquote{bestimmbar} übersetzen. Bei allen Aktzeptoren bis zu diesem Abschnitt lässt sich eindeutig bestimmen, in welchem Zustand sie sich nach einer Eingabe befinden. Deshalb werden diese auch als deterministische endliche Automaten oder kurz DEA bezeichnet. Genau diese Eigenschaft weist ein NEA nicht auf. Er kann sich zu jedem Zeitpunkt in verschiedenen Zuständen befinden und auch der Startzustand muss nicht eindeutig festgelegt sein. Durch diese Möglichkeiten kann man auch für komplexere Anforderungen einen Automaten mit nur wenigen Zuständen erstellen.

\begin{Aufgaben}
	\item Bei der DNA von Zellen befinden sich am ihrem Anfang und Ende jeweils spezielle Sequenzen die sich auch in der Regel mehrfach wiederholen. Sie haben eine wichtige Steuerfunktion bei der Reproduktion der DNA. Erstellen Sie einen NEA, mit dem überprüft werden kann, ob die Startsequenz AATG und die Endsequenz TCAC in einer gegebenen DNA vorhanden ist.
	\AufgabenHinweis{Das Eingabealphabet beschränkt sich bei der DNA nur auf vier verschiedene Möglichkeiten: ACGT. Zu beachten ist nur der Anfang und das Ende der Eingabe. Dabei muss der entsprechende Einstieg gefunden werden.}
	\AufgabenLoesung{}
	\TextFeld{3cm}

	\item Gegeben ist nur die Zustandsübergangstabelle eines NEA. Dabei sind die Zustände, die der Automat bei gleicher Eingabe von einem Zustand aus erreichen kann, durch ein Komma getrennt. Geben Sie an, welche Eingaben der Automat akzeptiert. Zeichnen Sie außerdem das Zustandsübergangsdiagramm auf. Startzustand ist \(s_0\) und der akzeptierte Endzustand ist \(s_5\).

	\begin{center}
% 	\begin{table}[ht]
% 		\centering
		\begin{tabular}{l||l|l|l|l}
			& A & C & G & T \\ \hline \hline
			\(s_0\) & \(s_1\) & - & - & - \\ \hline
			\(s_1\) & - & - & - & \(s_2\) \\ \hline
			\(s_2\) & \(s_1,s_3\) & \(s_3\) & \(s_3\) & \(s_3\) \\ \hline
			\(s_3\) & \(s_3\) & \(s_3,s_4\) & \(s_3\) & \(s_3\) \\ \hline
			\(s_4\) & - & - & \(s_5\) & - \\ \hline
			\(s_1\) & - & \(s_4\) & - & - \\ 
		\end{tabular}	
	\end{center}
% 		\caption{Zustandsübergangstabelle eines NEA}
% 		ets
% 	\end{table}
	\AufgabenLoesung{
		Der Automat akzeptiert Eingaben, die mit eine Wiederholung von AT beginnen und einer Wiederholung von CG enden. Dazwischen muss mindestens ein Zeichen aus A, T, C oder G stehen.
		\begin{figure}[ht]
			\centering
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
				\node[state,initial]	(s_0) {$s_0$};
				\node[state]	(s_1) [right=of s_0]  {$s_1$};
				\node[state]	(s_2) [right=of s_1]  {$s_2$};
				\node[state]	(s_3) [right=of s_2]  {$s_3$};
				\node[state]	(s_4) [right=of s_3]  {$s_4$};
				\node[state, accepting]	(s_5) [right=of s_4]  {$s_5$};
				\path[->] 
					(s_0) edge node[above] {A} (s_1)
					(s_1) edge[bend left] node[above] {T} (s_2)
					(s_2) edge[bend left] node[above] {A} (s_1)
					(s_2) edge node[above] {A,C,G,T} (s_3)
					(s_3) edge[loop above] node[above] {A,C,G,T} ()
					(s_3) edge node[above] {C} (s_4)
					(s_4) edge[bend left] node[above] {G} (s_5)
					(s_5) edge[bend left] node[above] {C} (s_4);
			\end{tikzpicture}
			\caption{Zustandsübergangsdiagramm für einen unendlichen Automaten, der die korrekte Klammerung überprüft}
		\end{figure}	
	}
	\TextFeld{4cm}

\end{Aufgaben}

\subsection{Ein Übergang ohne Eingabe: Der $\epsilon$-Übergang}
Neben der Eigenschaft, in verschiedenen Zuständen gleichzeitig zu sein, kann ein NEA auch einen Übergang in einen anderen Zustand machen, ohne dass es dazu eine Eingabe gibt. Dieser Übergang wird \(\epsilon\)-Übergang genannt. 

Dieser Übergang kann z.\,B. dann genutzt werden, wenn man einen bestehenden Automaten einfach um eine weitere Eigenschaft erweitern will. Ein Automat, der alle Eingaben akzeptiert, die eine beliebige Anzahl von \enquote{t} haben und mit einem \enquote{r} enden, kann so auch erweitert werden, dass er auch eine Wiederholung dieser Wörter akzeptiert.

\missingfigure{Übergangsdiagramm des Automaten mit $\epsilon$-Übergang}

Natürlich lassen sich solche Erweiterungen auch auf andere Weise realisieren. So kann man den \(\epsilon\)-Übergang von Startzustand zu einem anderen Zustand auch direkt durch einen zweiten Startzustand realisieren. Dieses bedeutet, dass es zu jedem NEA mit \(\epsilon\)-Übergängen auch einen NEA ohne solche Übergänge gibt, der die gleiche Aufgabe erfüllt.

\todo[inline]{Übung zum $\epsilon$-Übergang}

\subsection{Vergleich von DEA und NEA}

Beim Vergleich von einem DEA und einem NEA ist zu erkennen, dass beide die gleiche Aufgabe erfüllen: Eingaben zu akzeptieren oder abzulehnen. Daher stellt sich die Frage, ob ein NEA durch seine zusätzliche Möglichkeit, in mehreren Zuständen gleichzeitig zu sein, wirklich mehr kann als ein DEA. Sollte dieses nicht der Fall sein, so gibt es zu jedem NEA auch einen DEA, der genau die gleichen Eingaben akzeptiert.

Betrachten wir deshalb noch einmal den ersten NEA \ref{nea_ter} in diesem Leitprogramm, der alle Wörter akzeptiert, die auf ter enden. Es gibt auch einen DEA, der diese Aufgabe erfüllt:

\begin{figure}[ht]
	\centering
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm and 8cm,on grid,auto]
		\node[state,initial]	(s_0) {$s_0$};
		\node[state]	(s_1) [right=of s_0]  {$s_1$};
		\node[state]	(s_2) [below=of s_1]  {$s_2$};
		\node[state,accepting]	(s_3) [left=of s_2]  {$s_3$};
		\path[->] 
			(s_0) edge[bend left=10] node[above] {t} (s_1)
			(s_0) edge[loop above] node[above] {\(\Sigma - \{t\}\)} ()
			(s_1) edge[bend left] node[right] {e} (s_2)
			(s_1) edge[bend left=10] node[above] {\(\Sigma  - \{t,e\}\)} (s_0)
			(s_1) edge[loop above] node[above] {t} ()
			(s_2) edge node[above] {r} (s_3)
			(s_2) edge[bend left] node[left] {t} (s_1)
			(s_2) edge[] node[near end, below] {\(\Sigma  - \{t,r\}\)} (s_0)
			(s_3) edge[] node[left] {\(\Sigma  - \{t\}\)} (s_0)
			(s_3) edge[] node[near start, below] {t} (s_1);
	\end{tikzpicture}
	\caption{Zustandsübergangsdiagramm eines deterministischen Automaten für alle Wörter, die auf \enquote{ter} enden}
\end{figure}

Für diesen speziellen Fall lässt sich also ein passender DEA zum NEA finden. Gesucht wird daher zu einem beliebigen NEA ein passender DEA. Dieses ist auch nicht so schwer, wie es auf den Blick erscheint. Betrachtet man einen NEA mit \(n\) Zuständen, so kann sich dieser auch in mehreren Zuständen gleichzeitig befinden. Die Anzahl der möglichen Kombinationen von Zuständen, in den sich der NEA befinden kann, ist aber begrenzt: Es gibt nur \(2^n\) mögliche Kombinationen. Daher ist es möglich, einen DEA zu finden, der \(m \leq 2^n\) Zustände hat.

\subsection{Vom NEA zum DEA}
Um für einen NEA den entsprechenden DEA zu finden, gibt es einen einfachen Algorithmus. Dieser soll an einem einfachen NEA demonstriert werden:

\begin{figure}[ht]
 \centering
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
		\node[state,initial]	(s_1) {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state,accepting]	(s_5) [right=of s_2]  {$s_5$};
		\node[state,initial]	(s_3) [below=of s_1]  {$s_3$};
		\node[state,accepting] (s_4) [right=of s_3]  {$s_4$};
		\path[->] 
			(s_1) edge node[above] {a} (s_2)
			(s_2) edge[loop above] node[above] {a,b} ()
			(s_2) edge node[above] {b} (s_5)
			(s_3) edge node[right] {b} (s_1)
			(s_3) edge node[above] {b} (s_4)
			(s_4) edge node[right] {b} (s_2);
	\end{tikzpicture}
	\caption{Beispiel eines einfachen NEA}
\end{figure}

Zu Beginn wird die Eingabemenge des Automaten bestimmt und die einzelnen Elemente als Spaltenköpfe in eine Tabelle eingetragen, wobei die erste Spalte keinen Spaltenkopf bekommt. In die erste Zeile der Tabelle werden nun in der ersten Spalte alle Startzustände des NEA aufgetragen. Für das Beispiel sieht die Tabelle nun so aus:

\begin{center}
	\begin{tabular}{l||l|l}
		& a & b \\ \hline \hline
		\(s_1, s_3\) & & \\ 
	\end{tabular}
\end{center}

Dann wird für jede Eingabe herausgesucht, in welche Zustände von den Zuständen aus gewechselt werden kann. Diese werden dann in die entsprechende Spalte eingetragen. Von den Zuständen \(s_1\) und \(s_3\) kann man beim Beispielautomaten durch die Eingabe von einem a nur zum Zustand \(s_2\) und mit einem b zu den Zuständen \(s_1\) und \(s_4\) kommen. Die Tabelle hat anschließend folgenden Stand:

\begin{center}
	\begin{tabular}{l||l|l}
		& a & b \\ \hline \hline
		\(s_1, s_3\) & \(s_2\) & \(s_1, s_4\) \\ 
	\end{tabular}
\end{center}

Es geht nun weiter, indem für jede Kombination von Zuständen, die durch eine Eingabe erreicht wurden, wieder erarbeitet wird, welche Zustände von dort aus erreicht werden. Im Beispiel müssen also als nächstes die Kombinationen \(s_2\) und \(s_1, s_4\) untersucht werden:

\begin{center}
	\begin{tabular}{l||l|l}
		& a & b \\ \hline \hline
		\(s_1, s_3\) & \(s_2\) & \(s_1, s_4\) \\ \hline
		\(s_2\) & \(s_2\) & \(s_2, s_5\) \\ \hline
		\(s_1, s_4\) & \(s_2\) & \(s_2\) \\ 
	\end{tabular}
\end{center}

Die vollständige Tabelle, wenn alle Kombinationen untersucht werden, hat dann die folgende Gestalt:

\begin{center}
	\begin{tabular}{l||l|l}
		& a & b \\ \hline \hline
		\(s_1, s_3\) & \(s_2\) & \(s_1, s_4\) \\ \hline
		\(s_2\) & \(s_2\) & \(s_2, s_5\) \\ \hline
		\(s_1, s_4\) & \(s_2\) & \(s_2\) \\ \hline
		\(s_2, s_5\) & \(s_2\) & \(s_2, s_5\) \\
	\end{tabular}
\end{center}

Daraus ergibt sich, dass ein DEA, der die gleichen Eingaben akzeptiert, aus vier Zuständen besteht. Diese kann man in Anlehnung an die ursprünglichen Zustände des NEA wie folgt bezeichnen: \(s_{1,3}, s_2, s_{1,4}\) und \(s_{2,5}\). Dabei sind alle Zustände als akzeptierte Zustände anzusehen, bei denen mindestens einer der Zustände, aus denen sie bestehen, selber ein akzeptierter Zustand war. In dem Beispiel sind dieses \(s_{1,4}\) und \(s_{2,5}\), da im NEA \(s_4\) und \(s_5\) akzeptierte Zustände sind.

So hat man direkt einen DEA mit Zustandsübergangstabelle. Aus dieser lässt sich auch auf Wunsch ein Zustandsübergangsdiagramm erstellen:

\begin{figure}[ht]
 \centering
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
		\node[state,initial]	(s_13) {$s_{1,3}$};
		\node[state]	(s_2) [right=of s_13]  {$s_2$};
		\node[state,accepting]	(s_14) [below=of s_13]  {$s_{1,4}$};
		\node[state,accepting]	(s_25) [below=of s_2]  {$s_{2,5}$};
		\path[->] 
			(s_13) edge node[above] {a} (s_2)
			(s_13) edge node[left] {b} (s_14)
			(s_2) edge[loop right] node[right] {a} ()
			(s_2) edge[bend left] node[right] {b} (s_25)
			(s_14) edge node[right] {a,b} (s_2)
			(s_25) edge[bend left] node[right] {a} (s_2)
			(s_25) edge[loop right] node[right] {b} ();
	\end{tikzpicture}
	\caption{Aus dem Beispiel NEA erzeugte DEA}
\end{figure}

Mit dieser Vorgehensweise lässt sich zu jedem NEA der passende DEA erzeugen. Auf diese Weise lassen sich zwei Sachen miteinander verbinden: Die Umsetzung eines DEA in einem Programm ist wesentlich komplizierter als die eines DEA. Sucht man aber zu einem Problem einen passenden Akzeptor, so lässt sich dieser aber in der Regel einfacher mit einem NEA realisieren. Bei der Aufgabe, ein Problem in ein Programm zu überführen, kann man sich dieses zunutze machen, indem man zuerst einen NEA erstellt, diesen in einen DEA überführt und daraus ein Programm entwickelt. Die Übersetzung eines DEA in ein Programm wird im nächsten Kapitel erläutert.

\begin{Aufgabe}
	Erstelle zu den drei gegebenen NEA jeweils den passenden DEA mit dem passenden Zustandsübergangsdiagramm:
	\begin{enumerate}[a)]
		\item \adjustbox{valign=t}{ \input{nea1.cir}}
		\item \adjustbox{valign=t}{\input{nea2.cir}}
		\item \adjustbox{valign=t}{\input{nea3.cir}}
	\end{enumerate}
	\AufgabeLoesung{
		\begin{enumerate}
			\item \adjustbox{valign=t}{\input{dea_aus_nea1.cir}}
			\item \adjustbox{valign=t}{\input{dea_aus_nea2.cir}}
			\item \adjustbox{valign=t}{\input{dea_aus_nea3.cir}}
		\end{enumerate}
	}
\end{Aufgabe}

\chapter{Umsetzung eines Automaten in ein Programm}
Bei der Umsetzung von Automaten in Programme sollen an dieser Stelle nur Akzeptoren betrachtet werden, die auch als Parser bezeichnet werden. Um die Aufgabe eines Akzeptors übernehmen zu können, muss ein Programm folgende Teile realisieren:
\begin{enumerate}
	\item Den aktuellen Zustand speichern und zu Beginn den Startzustand einnehmen.
	\item Die Eingabe Zeichen für Zeichen durchgehen.
	\item Aus dem aktuellen Eingabeelement und aktuellem Zustand auf den neuen Zustand schließen und diesen einnehmen.
	\item Am Ende der Eingabe zurückgeben, ob ein akzeptierter Zustand vorliegt.
\end{enumerate}

Eine Methode, die diese Elemente umsetzt, soll nun schrittweise an dem folgenden DEA vorgestellt werden. Dabei wird ein Pseudocode verwendet. Die Umsetzung in bekannte Programmiersprachen ist im Anhang (\ref{umsetzung_allgemein}) zu finden.

\begin{figure}[ht]
	\centering
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
		\node[state,initial]  (s_1)                {$s_1$};
		\node[state]          (s_2) [right=of s_1] {$s_2$};
		\node[state,accepting](s_3) [below=of s_1] {$s_3$};
		\path[->] 
			(s_1) edge             node {b}   (s_2)
			(s_1) edge[left]             node {a,c} (s_3)
			(s_3) edge[loop left] node {b}   ()
			(s_2) edge[bend left]  node {a,b} (s_3)
			(s_3) edge[bend left]  node {a}   (s_2);
	\end{tikzpicture}
	\caption{DEA, der in ein Programm übersetzt werden soll}
\end{figure}

Der erste Teil, die Speicherung des aktuellen Zustands, lässt sich mit einer einfachen Variable für Zahlen realisieren. Dieser wird der Startzustand übergeben.

\begin{lstlisting}
	zustand <- 1
\end{lstlisting}

Für den zweiten Teil wird die Zeichenkette zeichenweise vom Anfang bis zum Ende durchgegangen. Dieses erfolgt mit einer einfachen Wiederholungsstruktur, die läuft, bis das Ende der Zeichenkette erreicht ist.

\begin{lstlisting}
	pos <- 0
	Solange pos < Länge von wort:
		symbol <- Zeichen von wort an der Stelle pos
		...
		pos <- pos + 1
\end{lstlisting}

Innerhalb dieser Wiederholung muss jeweils aus der Kombination von aktuellem Zustand und dem aktuellen Zeichen ein neuer Zustand gewählt werden. Dieses geschieht durch doppelt geschachtelte bedingte Anweisungen. In der ersten Ebene wird nach dem aktuellen Zustand unterschieden.

\begin{lstlisting}
		Wenn zustand = 1:
			...
		Sonst Wenn zustand = 2:
			...
		Sonst:
			...
\end{lstlisting}

Da der Beispielautomat nur aus drei Zuständen besteht, werden auch nur diese drei unterschieden. Zu beachten ist dabei, dass immer mit \enquote{Sonst} gearbeitet wird, da innerhalb des Bereiches ein anderer Zustand schon gesetzt wird und damit das aktuelle Zeichen noch auf einen weiteren Zustand angewandt wird. 

Innerhalb der Unterscheidung nach Zuständen, findet die Unterscheidung bezüglich des aktuellen Zeichens statt. Dabei wird dann der neue Zustand zugewiesen oder die Methode mit der Rückgabe von \enquote{Nicht wahr} beendet. Letzteres passiert, wenn es einen Übergang in den \enquote{Müllzustand} gibt. Dieses wird hier am Beispiel für den Zustand~1 verdeutlicht:

\begin{lstlisting}
			Wenn symbol = 'a' oder symbol = 'c':
				zustand <- 3
			Sonst Wenn symbol = 'b':
				zustand <- 2
			Sonst:
				Gib zurück 'Nicht Wahr'
\end{lstlisting}

Zum Ende der Methode, wenn die komplette Zeichenkette durchlaufen wurde, muss sie eine Überprüfung und entsprechende Rückgabe machen, ob sich der Automat in einem akzeptierten Endzustand befindet.

\begin{lstlisting}
	Gib zurück das Ergebnis von (zustand = 3)
\end{lstlisting}

Zusammengesetzt sollte sich darauf die folgende Methode parser ergeben:

\begin{lstlisting}
definiere parser (wort):
	zustand <- 1
	pos <- 0
	Solange pos < Länge von wort:
		symbol <- Zeichen von wort an der Stelle pos
		Wenn zustand = 1:
			Wenn symbol = 'a' oder symbol = 'c':
				zustand <- 3
			Sonst Wenn symbol = 'b':
				zustand <- 2
			Sonst:
				Gib zurück 'Nicht Wahr'
		Sonst Wenn zustand = 2:
			Wenn symbol = 'a' oder symbol = 'c':
				zustand <- 3
			Sonst: 
				Gib zurück 'Nicht Wahr'
		Sonst:
			Wenn symbol = 'b' 
				zustand <- 3
			Sonst Wenn symbol = 'a':
				zustand <- 2
			Sonst:
				Gib zurück 'Nicht Wahr'
		pos <- pos + 1
	gib zurück das Ergebnis von (zustand = 3)
\end{lstlisting}

\begin{Aufgabe}
	Erstellen Sie zu dem folgenden Akzeptor eine passende Methode \lstinline|parser(wort)| in der im Unterricht verwendeten Programmiersprache. Testen Sie ihre Methode an verschiedenen Eingaben.

	\input{dea_fuer_parser.cir}
\end{Aufgabe}

\chapter{Grammatiken}
Den Aufbau der Zeichenketten, die von einem Automaten akzeptiert werden, lassen sich auch mit Hilfe von formalen Grammatiken darstellen. Als kleines Beispiel wird die Grammatik betrachtet, die nur die beiden Eingaben \enquote{abb} und \enquote{aaa} erlaubt:

\(N = \{\mbox{A, B, C, D}\} \) \\
\(\Sigma = \{\mbox{a, b}\} \) \\
\(P = \{\mbox{A\textrightarrow aB, B\textrightarrow aC\textbar bD, C\textrightarrow a, D\textrightarrow b}\}\) \\
\(S = \mbox{A}\)

Diese Grammatik besteht aus Produktionsregeln \(P\), die auf Symbole angewendet werden, um andere Symbole zu erhalten. Alle diese Symbole bilden das Vokabular \(V\), das sich aus den Terminalsymbole \(\Sigma\) und den Nichtterminalsymbole \(N\) zusammensetzt. Die Menge der Terminalsymbole entspricht dabei der Eingabemenge eines Automaten. Für die Nichtterminalsymbole werden in der Regel Großbuchstaben gewählt, die zum Aufstellen der Produktionsregeln benötigt werden. Begonnen wird dabei mit dem in \(S\) angegebenen Nichtterminalsymbol, dem Startsymbol.

Bei der Bildung der durch die Grammatik beschriebenen Wörter, wird immer ein Nichtterminalsymbol durch die Anwendung einer entsprechenden Produktionsregel ersetzt. So wird zur Bildung von \enquote{abb} aus A erst aB, dann abD und zum Schluss abb. Der vertikale Strich bei den Produktionsregeln steht dabei für ein Oder. Dadurch wird es ermöglicht, dass zwischen verschiedenen Möglichkeiten bei der Ersetzung ausgewählt werden kann. Außerdem ist die Ersetzung durch \(\epsilon\) möglich, das als das leere Wort bezeichnet wird. In diesem Fall wird das Nichtterminalsymbol entfernt.

\begin{Aufgaben}
	\item Geben Sie eine Erklärung zur Wortwahl bei den Begriffen Terminalsymbole und Nichtterminalsymbole an.
	\AufgabenHinweis{Das Adjektiv terminal stammt vom lateinischen terminare: abgrenzen, begrenzen, beenden.}
	\TextFeld{2cm}

	\item Gegeben ist folgende Grammatik:

		\(N = \{\mbox{A, B, C, D, E}\} \) \\
		\(\Sigma = \{\mbox{a, b, c}\} \) \\
		\(P = \{\mbox{A\textrightarrow Ba, B\textrightarrow aC\textbar bD, C\textrightarrow}\epsilon\mbox{\textbar aB, D\textrightarrow bC\textbar cE, E\textrightarrow aB\textbar}\epsilon\}\) \\  %Auch mal links und rechts anhängen.
		\(S = \mbox{A}\)

		Analysieren Sie, welche Wörter damit gebildet werden können und geben Sie das Zustandsübergangsdiagramm eines entsprechenden Automaten an.
	\AufgabenHinweis{Es ist hilfreich die Produktionsregeln einfach anzuwenden und bei den Auswahlmöglichkeiten beliebig zu wählen.}
	\AufgabenLoesung{
		\begin{figure}[ht]
			\centering
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
				\node[state,initial]	(s_0) {$s_0$};
				\node[state]	(s_1) [below=of s_0]  {$s_1$};
				\node[state]	(s_2) [right=of s_0]  {$s_2$};
				\node[state,accepting]	(s_3) [right=of s_2]  {$s_3$};
				\node[state]	(s_4) [right=of s_1]  {$s_4$};
				\path[->] 
					(s_0) edge node[above] {a} (s_2)
					(s_0) edge node[right] {b} (s_1)
					(s_1) edge node[right] {b} (s_2)
					(s_1) edge node[above] {c} (s_4)
					(s_2) edge node[above] {a} (s_3)
					(s_4) edge node[right] {a} (s_3)
					(s_2) edge[bend right] node[above] {a} (s_0);
			\end{tikzpicture}
			\caption{Zustandsübergangsdiagramm für einen Automaten, der gleiche Wörter akzeptiert, wie die gegebene Grammatik}
		\end{figure}
	}
	\TextFeld{5cm}

	\item Erstellen Sie eine Grammatik für Wörter die aus einer fast beliebigen Reihenfolge von a und b bestehen. Einschränkung dabei soll aber sein, dass wenn exakt nur zwei a oder b folgen, soll danach ein c stehen (Beispiel: ababbcaaabaac). Vergleichen Sie diese Grammatik mit dem Ergebnis von einem anderen Mitschüler.
	\AufgabenLoesung{Es gibt, ähnlich wie bei Automaten, keine eindeutige Lösung. Eine mögliche Lösung ist:

		\(N = \{\mbox{A, B, C, D, E}\} \) \\
		\(\Sigma = \{\mbox{a, b, c}\} \) \\
		\(P = \{\mbox{A\textrightarrow aB\textbar bC\textbar}\epsilon, \mbox{B\textrightarrow acbC\textbar aaD\textbar ac\textbar}\epsilon, \mbox{C\textrightarrow bcaB\textbar bbE\textbar bc\textbar}\epsilon, \mbox{D \textrightarrow aD\textbar bC\textbar}\epsilon, \mbox{E\textrightarrow bE\textbar aB\textbar}\epsilon \}\) \\  
		\(S = \mbox{A}\)
	}
	\TextFeld{2cm}
\end{Aufgaben}

\section{Reguläre Grammatiken}
Eine Untergruppe der Grammatiken sind die regulären Grammatiken. Bei ihnen werden besondere Bedingungen an die Produktionsregeln gestellt. Bei ihnen dürfen nur Ersetzungen durch ein Terminalsymbol, das leere Wort oder die Kombination von einem Terminal- und einem Nichtterminalsymbol genutzt werden. Dabei müssen die Kombinationen innerhalb der Grammatik immer die gleiche Reihenfolge haben. Je nach Reihenfolge wird dabei von einer rechtsregulären oder einer linksregulären Grammatik gesprochen.

Bei der linksregulären Grammatik, teilweise auch linkslineare Grammatik genannt, dürfen also nur Produktionsregeln der Form A\textrightarrow Ba, A\textrightarrow a oder A\textrightarrow\(\epsilon\) genutzt werden. Wörter die dadurch zusammengebaut werden, wachsen in die linke Richtung, wodurch sich auch der Name ableitet. Analog sind bei der rechtsregulären (rechtslineare) Grammatik nur Form A\textrightarrow aB, A\textrightarrow a oder A\textrightarrow\(\epsilon\) erlaubt. Dadurch verlängern sich die Wörter immer nach rechts.

Diese regulären Grammatiken haben den Vorteil, dass von ihnen sehr einfach ein Akzeptor abgeleitet werden kann. Die Gründe dafür werden später noch genauer beleuchtet. Es geht dabei soweit, dass sich für die akzeptierten Worte eines Akzeptors einfach eine Grammatik aufstellen lässt. Der Umkehrschluss, dass sich zu einer nicht reguläre Grammatik kein Akzeptor bauen lässt, trifft aber nicht zu.

\begin{Aufgaben}
	\item Geben Sie aufgrund der Produktionsregeln an, ob die dazugehörige Grammatik regulär ist und wenn ja, in welche Richtung.
	\begin{enumerate}
		\item  A\textrightarrow Aa\textbar Ba, B\textrightarrow Cb, C\textrightarrow Cb\textbar Da, D\textrightarrow Daa\textbar Eb, E\textrightarrow b
		\item A\textrightarrow aB\textbar bB, B\textrightarrow bC, C\textrightarrow \(\epsilon\)\textbar g\textbar d\textbar bA
		\item A\textrightarrow aBa, B\textrightarrow aB\textbar bC, C\textrightarrow bC\textbar bD, D \textrightarrow aE\textbar bE, E\textrightarrow b\textbar bE
	\end{enumerate}
	\AufgabenHinweis{Bevor Sie ihre Lösung kontrollieren, sollten Sie die Produktionsregeln mit den drei jeweils gültigen Mustern vergleichen.}
	\AufgabenLoesung{
		\begin{enumerate}
			\item Sie ist nicht regulär, da D\textrightarrow Daa gegen die Regeln verstößt.
			\item Sie ist rechtsregulär.
			\item Sie ist nicht regulär, da A\textrightarrow aBa gegen die Regeln verstößt.
		\end{enumerate}
	}
	\TextFeld{2cm}

	\item Modifizieren Sie die in der vorherigen Aufgabe angegebenen Grammatiken so, dass sie regulär sind.
	\AufgabenHinweis{Bei allen gegebenen ist dieses möglich, was aber nicht immer der Fall sein muss. Wenn es möglich ist, müssen die Regeln, die zu einem Konflikt führen, durch passende ersetzt werden.}
	\AufgabenLoesung{
		\begin{enumerate}
			\item Die Regel D\textrightarrow Daa\textbar Eb muss überführt werden in die beiden Regeln D\textrightarrow Fa\textbar Eb und F\textrightarrow Da.
			\item Sie ist bereits regulär.
			\item Die Regel A\textrightarrow aBa muss überführt werden in die Regel A\textrightarrow aB und die Regel E\textrightarrow b\textbar bE in die Regel E\textrightarrow bF\textbar bE  und F \textrightarrow a.
		\end{enumerate}
	}
	\TextFeld{3cm}

	\item Erstellen Sie zum folgenden, im Zustandsübergangsdiagramm angegebenen Akzeptor eine linksreguläre Grammatik.

		\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
			\node[state,initial]	(s_0) {$s_0$};
			\node[state,accepting]	(s_1) [right=of s_0]  {$s_1$};
			\node[state,accepting]	(s_2) [right=of s_1]  {$s_2$};
			\node[state]	(s_3) [right=of s_2]  {$s_3$};
			\path[->] 
				(s_0) edge[bend right] node[below] {0} (s_1)
				(s_1) edge[bend right] node[above] {1} (s_0)
				(s_1) edge node[above] {0} (s_2)
				(s_2) edge[bend right] node[below] {1} (s_3)
				(s_3) edge[bend right] node[above] {0} (s_2);
		\end{tikzpicture}

	\AufgabenHinweis{Es gibt zwei Möglichkeiten dazu: Man fängt beim Automaten hinten an und geht die Pfeile rückwärts oder man erstellt eine rechtsreguläre Grammatik und versucht sie umzustellen. Dabei kann man, bis auf das Startsymbol sagen: Ein Zustand ein Nichtterminalsymbol.}
	\AufgabenLoesung{
		\(N = \{\mbox{A, B, C, D, E}\} \) \\
		\(\Sigma = \{\mbox{1, 0}\} \) \\
		\(P = \{\mbox{A\textrightarrow 0B\textbar 0C\textbar 0E, B\textrightarrow} \epsilon\mbox{\textbar 1C, C\textrightarrow 0B, D\textrightarrow 0C\textbar 0E, E\textrightarrow 1D} \}\) \\  
		\(S = \mbox{A}\)
	}
	\TextFeld{2cm}
\end{Aufgaben}

\chapter{Reguläre Sprachen}
Mit dem Begriff Sprachen werden Sie wahrscheinlich als erstes die natürlichen und zum größten Teil gesprochene Sprachen verbinden. Daneben gibt es aber auch die konstruierten Sprachen. Zu diesen gehören auch die formalen Sprachen. Beispiele für formale Sprachen sind die Programmiersprachen, aber auch die in der theoretischen Informatik genutzten Sprachen. Zu diesen gehören auch alle regulären Sprachen.

Die allgemeine Definition einer Sprache \(L\) ist, dass sie aus Wörtern besteht, die aus einem Alphabet \(\Sigma\) gebildet werden. Jedes Wort besteht also nur aus aneinander gehangenen Zeichen eines festen Alphabets. Um die Wörter einer Sprache anzugeben, bedient man sich einer Aufzählung sowie der Benutzung verschiedener Hilfsmittel. So besteht die Sprache \(L = \{\mbox{abc, bbc}\} \) nur aus eben den beiden angegeben Wörtern. Die Sprache \(L = \{\mbox{a}^n\mbox{b}^m | n,m \geq 0 \}\) aus allen Wörtern, die aus einer beliebigen Anzahl von a, gefolgt von einer beliebigen Anzahl von b zusammen gesetzt sind. Das Leere Wort \(\epsilon\) ist damit auch Teil dieser Sprache.

Damit eine Sprache zu den regulären Sprachen gezählt wird, muss sie einige Eigenschaften erfüllen: Es muss einen endlichen Automaten geben, der alle Wörter der Sprache und kein weiteres Wort akzeptiert. Alternativ muss es möglich sein, zur Sprache eine reguläre Grammatik aufstellen zu können. Auch müssen sich die Wörter der Sprache mit einem regulären Ausdruck beschreiben lassen. Diese Ausdrücke werden im nächsten Kapitel genauer behandelt. Diese vier Angaben sind äquivalent zueinander: Die Sprache, die ein endlicher Automat akzeptiert, ist eine reguläre Sprache und sie lässt sich auch durch eine reguläre Grammatik beschreiben. Wie aber bereits im vorherigen Kapitel angedeutet, kann man aber nicht sagen, dass z.\,B. die Sprache einer nicht regulären Grammatik keine reguläre Sprache ist.

Durch diese Bedingungen ergeben sich die gleichen Einschränkungen, wie auch für Automaten. So sind alle Sprachen, in denen gezählt werden muss, wie z.\,B. bei Klammerausdrücken, keine regulären Sprachen. Dieses gilt also für Programmiersprachen, bei denen darauf geachtet werden muss, dass es zu jeder sich öffnenden Klammer auch eine schließende gibt. Alle möglichen Bezeichner einer Methode bilden aber eine reguläre Sprache.

\begin{Aufgaben}
	\item Geben Sie begründet an, welche der folgenden Sprachen regulär sind und welche nicht:
	\begin{enumerate}
		\item Die erlaubten \ProgSp-Kommentare
		\item Die erlaubten HTML-Texte
		\item Die korrekten arithmetischen Ausdrücke
		\item Die erlaubten Dateinamen
		\item Die erlaubten WWW-Adressen
	\end{enumerate}
	\AufgabenLoesung{Bei den Sprachen spielt die Abzählung die entscheidende Rolle:
		\begin{enumerate}
			\item Ist regulär.
			\item Ist nicht regulär, da zu jedem geöffneten Tag auch ein schließender gehört.
			\item Ist nicht regulär, da hier auch auf öffnende und schließende Klammern geachtet werden muss.
			\item Ist regulär.
			\item Ist regulär.
		\end{enumerate}
	}
	\TextFeld{3cm}

	\item Geben Sie die Sprache an, die folgender Automat akzeptiert:
		\AufgabenLoesung{ \( L = \{\mbox{a}, \mbox{abd}, \mbox{bc}^n\mbox{bb} | n \geq 2 \} \) }
	
		\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
			\node[state,initial]	(s_0) {$s_0$};
			\node[state,accepting]	(s_1) [right=of s_0]  {$s_1$};
			\node[state]	(s_2) [right=of s_1]  {$s_2$};
			\node[state,accepting]	(s_3) [right=of s_2]  {$s_3$};
			\node[state]	(s_4) [below=of s_0]  {$s_4$};
			\node[state]	(s_5) [right=of s_4]  {$s_5$};
			\node[state]	(s_6) [right=of s_5]  {$s_6$};
			\node[state]	(s_7) [right=of s_6]  {$s_7$};
			\node[state,accepting]	(s_8) [right=of s_7]  {$s_8$};
			\path[->] 
				(s_0) edge node[above] {a} (s_1)
				(s_1) edge node[above] {b} (s_2)
				(s_2) edge node[above] {d} (s_3)
				(s_0) edge node[right] {b} (s_4)
				(s_4) edge node[above] {c} (s_5)
				(s_5) edge node[above] {c} (s_6)
				(s_6) edge node[above] {b} (s_7)
				(s_7) edge node[above] {b} (s_8)
				(s_6) edge[loop below] node[below] {c} ();
		\end{tikzpicture}
	\TextFeld{1cm}
\end{Aufgaben}

% \section{Pumping Lemma}
% Pumping Lemma? -- ja 

\chapter{Reguläre Ausdrücke}
Eine Möglichkeit eine reguläre Sprache zu beschreiben sind die regulären Ausdrücke.  Obwohl die Grundidee hinter regulären Ausdrücken einfach ist, können einige Ausdrücke so kompliziert werden, das selbst erfahrene Benutzer zwar noch in der Lage, sie selbst zu schreiben, nicht aber einen solchen komplizierten Ausdruck von anderen Personen aber sofort zu verstehen. Dabei passt ein Ausdruck auf eine bestimmte Menge von Wörtern, die dann die zugehörige Sprache bilden. Dabei ist es auch möglich, dass er im einfachsten Fall nur auf ein einziges Wort passt. 

Eigentlich werden reguläre Ausdrücke eher im Bereich der Suche nach Mustern genutzt, das auch \textbf{Pattern Matching} genannt wird. Ein sehr bekanntes Beispiel für den Einsatz von regulären Ausdrücken ist das Programm \enquote{grep}, mit dem man in Dateien nach bestimmten Vorkommnissen suchen kann. Grep liefert dann alle Zeilen, in denen ein Teil der Zeile auf den regulären Ausdruck passt:

\begin{verbatim}
$ grep -n -E "Kuss" romeo_julia.txt 
2513:Im Kusse sich verzehrt.  Die Süßigkeit
4430:Des Odems, siegelt mit rechtmäßgem Kusse
4441:Dein Trank wirkt schnell.--Und so im Kusse sterb ich.
$
\end{verbatim}

Hier wurde in der Datei \enquote{romeo\_julia.txt} \cite[\url{https://www.gutenberg.org/ebooks/6996}]{gutenberg2014} nach dem Vorkommen von Kuss gesucht. Das Ergebnis liefert die Zeilen, die \enquote{Kusse} enthalten. Der Text enthält das Wort Kuss nicht. Bei einer Zeile wird durch grep geprüft, ob der reguläre Ausdruck auf einen Teil der Zeile passt. Dieses ist bei dem Wort Kusse der Fall, da das Wort Kuss Teil von Kusse ist.

Der Parameter \enquote{-n} bei grep ist dabei verantwortlich dafür, dass die Zeilennummer angeben wird. Durch das \enquote{-E} wird die moderne Syntax der regulären Ausdrücke genutzt. Dieser Parameter sollte immer mit angeben werden, da es  für reguläre Ausdrücke keine einheitliche Schreibweise gibt und so die hier angegebene genutzt werden kann.

Bei dem Ausdruck \enquote{Kuss} wurden nur die vier Zeichen aneinander gehangen. Um aber auch gleichzeitig nach Küssen zu suchen muss man die beiden Teile durch ein \textbar voneinander trennen. Es stellt, wie bei den Grammatiken den Operator \enquote{Oder} dar. Der reguläre Ausdruck wäre dann \enquote{Kuss\textbar küssen}.

\begin{verbatim}
$ grep -n -E "Kuss|küssen" romeo_julia.txt 
572:Die schöner Frauen Stirne küssen, bringt
2513:Im Kusse sich verzehrt.  Die Süßigkeit
3439:Ich steig hinab; laß dich noch einmal küssen!
4430:Des Odems, siegelt mit rechtmäßgem Kusse
4441:Dein Trank wirkt schnell.--Und so im Kusse sterb ich.
4552:Dir deine Lippen küssen.  Ach, vielleicht
$
\end{verbatim}

Hierbei wurde aber nicht beachtet, dass \enquote{küssen} auch als Nomen oder am Satzanfang verwendet werden kann. Anstatt drei Wörter direkt aneinander zu hängen, kann man auch mit Klammern einen entsprechenden Vorrang schaffen: Kuss\textbar (K\textbar k)üssen.

Ein weiteres wichtiges Hilfsmittel bei regulären Ausdrücken ist der sogenannte Kleene-Stern (\enquote{*}). Wird der Kleene-Stern hinter ein Zeichen gesetzt, so bedeutet dies, dass dieses Zeichen keinmal bis beliebig oft wiederholt werden darf. Damit findet grep bei \enquote{of*e} nicht nur Kartoffeln und Kaminofen, sondern auch Soest, da hier das e direkt auf das o folgt.

Sehr ähnlich verhalten sich die Zeichen ? und +. Beim Fragezeichen soll das Zeichen ein bis keinmal vorkommen. Ein mindestens einmaliges Vorkommen wird durch das + erreicht. Alle drei Zeichen können natürlich auch an eine Klammer gesetzt werden, so dass sie sich auf den Inhalt der Klammer beziehen.

Auch wenn bei Verwendung der regulären Ausdrücke bei der Suche Wörter gefunden werden, bei denen nur ein Teil mit dem Ausdruck übereinstimmt, so sind diese nicht Teil der Sprache, die durch den regulären Ausdruck beschrieben werden. Bei den Wörtern der Sprache muss der reguläre Ausdruck genau stimmen. So enthält die Sprache, die von \enquote{of*e} beschrieben wird nur die Wörter oe, ofe, offe, offfe usw..

\begin{Aufgaben}
	\item Geben Sie alle Wörter der Sprache an, die durch den Ausdruck \enquote{(1|2)(34)(5|6)} gebildet wird.
	\AufgabenLoesung{L = \{1345, 1346, 2345, 2346\}}
	\TextFeld{1cm}
	
	\item Suchen Sie alle Zeilen in der Datei, in denen Julia oder Romeo vorkommt. Ihre Anzahl können sie über den Parameter \enquote{-c} für count bekommen.
	\AufgabenLoesung{Es sind genau 156 Zeilen}
	\TextFeld{1cm}
	
	\item Geben Sie alle Worte von \enquote{(ab|cab)*} an, die eine maximale Länge von 6 haben.
	\AufgabenLoesung{\(\epsilon\), ab, abab, ababab, cab, cabcab, abcab, cabab}
	\TextFeld{1cm}
\end{Aufgaben}

Es gibt noch eine weitere Menge von Möglichkeiten bei regulären Ausdrücken, von denen hier nur ein paar aufgelistet werden sollen:
\begin{itemize}
	\item Der Punkt als Sonderzeichen steht für ein beliebiges Zeichen.
	\item Wenn ein Zeichen aus einer bestimmten Auswahl stammen soll, so kann man den Ausdruck mit eckigen Klammern abkürzen. Aus \enquote{0|1|2|3} wird einfach \enquote{[0123]}. Hängen die Zeichen zusammen kann man auch ein - verwenden: \enquote{[0-3]}.
	\item Kommt direkt nach einer eckigen Klammer ein \textasciicircum, so wird der Inhalt negiert. Der Ausdruck \enquote{[\textasciicircum abc]} bedeutet also ein beliebiges Zeichen außer ein a,b oder c.
	\item Mit einem \textasciicircum wird sonst auch der Anfang eines Wortes angegeben und mit \$ dessen Ende. So müssen Wörter für \enquote{\textasciicircum a.*z\$} die Wörter mit einem a beginnen und einem z enden. Dazwischen dürfen beliebige Zeichen mit in einer unbeschränkten Anzahl sein.
\end{itemize}

\chapter{Nicht endliche Automaten}
Durch ihre Endlichkeit bei den Zuständen haben die Automaten eine Einschränkung, so dass bestimmte Problemfälle nicht mit ihnen bearbeitet werden können. Das prominenteste unter ihnen ist das Problem, nur Wörter zu akzeptieren, bei denen die Anzahl der sich öffnenden Klammern mit der sich schließenden Klammern übereinstimmt. Theoretischen Automaten benötigen dafür eigentlich eine nicht beschränkte Anzahl von Zuständen, sie müssen also ein unendlicher Automat sein. Um diese Beschränkung zu umgehen gibt es zwei Möglichkeiten: Der Kellerautomaten und die Turingmaschine, die beide in den nächsten beiden Abschnitten erklärt werden.

\section{Kellerautomat}
Die Bezeichnung Kellerautomat hat seine Ursache in dem Keller, den dieser 
Automatentyp zusätzlich gegenüber den bisher bekannten Automaten aufweist. 
Die Bezeichnung Keller wird im englischen Sprachraum mit Stack übersetzt. 
Da etliche ausgezeichnete Informatiklehrwerke und Umsetzungen in Programmiersprachen
englischsprachige Bezeichner enthalten, wird der Begriff Stack auch im Deutschen verwendet.
Eine weitere, allgemeinverständliche, deutsche Bezeichnung ist Stapel. 
In einen Keller/Stack/Stapel kann ein Automat theoretisch unendlich viele Zusatzeingaben ablegen. Um einen Stack nutzen zu können, ist der Zustandsübergang bei diesem Automaten nicht nur von der Eingabe und dem bisherigen Zustand abhängig, sondern auch vom aktuell obersten Element auf dem Stack. Dieses oberste Element wird vor jedem Übergang vom Stack herunter genommen. Es erfolgt neben dem Übergang in einen neuen Zustand auch das Ablegen von einem oder mehreren Elementen auf den Stack.

Zur Realisierung eines Akzeptors ist, gegenüber der Definition eines bisher bekannten endlichen Automaten, es für einen Kellerautomaten auch nötig das Alphabet der Zustände \(\Gamma\) sowie ein Zeichen \(\#\) für die Startbelegung des Stacks mit anzugeben. Wenn dieses das oberste Element des Stacks ist, so ist dieser als leer anzusehen. Auch beim Zustandsübergangsdiagramm gibt es Veränderungen: So wird hier bei einem Übergang neben der Eingabe auch das zugehörige oberste Stackelement und das oder die Elemente, die wieder auf den Stack gelegt werden soll mit angegeben. Die Schreibweise ist dabei \(<\)Eingabe, oberstes Element; neue Elemente\(>\).

Um den Aufbau noch einmal zu verdeutlichen, wird die Definition eines Kellerautomat genauer betrachtet, der die Sprache \(abc^nd^nb\) akzeptiert. Das Alphabet des Kellers besteht dabei aus zwei Zeichen, wobei 0 als Startwert \(\#\) für den Keller gewählt wurde. Immer dann wenn ein \(c\) an der passenden Stelle in der Eingabe kommt, wird auch ein c zusätzlich zu dem bisher oben aufliegenden Zeichen auf den Stack gelegt. Jedes d entfernt dann das oberste c, indem die leere Eingabe \(\epsilon\) aufgelegt wird.

\begin{figure}[ht]
	\(\Sigma = \{a, b, c, d\} \)\\
	\(Z = \{s_0, s_1, s_2, s_3, s_4, s_5\}\)\\
	\(z_0 = s_0\)\\
	\(E = \{s_5\}\)\\
	\(\Gamma = \{c,0\} \)\\
	\(\# = 0\)\\
	\(\varphi = \)\\
	\hspace*{0.7cm}
	\begin{tikzpicture}[shorten >=1pt,node distance=3cm and 3cm,on grid,auto]
		\node[state,initial]	(s_0) {$s_0$};
		\node[state]	(s_1) [right=of s_0]  {$s_1$};
		\node[state]	(s_2) [right=of s_1]  {$s_2$};
		\node[state]	(s_3) [above=of s_2]  {$s_3$};
		\node[state]	(s_4) [right=of s_3]  {$s_4$};
		\node[state,accepting]	(s_5) [right=of s_2]  {$s_5$};
		\path[->] 
				(s_0) edge node[above] {a,0;0} (s_1)
				(s_1) edge node[above] {b,0;0} (s_2)
				(s_2) edge node[above] {b,0;0} (s_5)
				(s_2) edge node[left] {c,0;c0} (s_3)
				(s_3) edge[loop left] node[above] {c,c;cc} ()
				(s_3) edge node[above] {d,c;\(\epsilon\)} (s_4)
				(s_4) edge[loop right] node[above] {d,c:\(\epsilon\)} ()
				(s_4) edge node[right] {b,0;0} (s_5);
	\end{tikzpicture}
	\caption{Kellerautomat der \(abc^nd^nb\) akzeptiert.}
\end{figure}

Möchte man mit einem solchen Kellerautomaten die Sprache \(a^nb^n\) akzeptieren, so muss sichergestellt sein, dass am Ende des Wortes nicht nur ein akzeptierter Zustand erreicht wurde, sondern auch der Keller leer ist. Bei dem vorherigen Beispiel trat dieses Problem nicht auf, da am Ende ein einzelnes \(b\) stehen musste. Mit einer simplen Ergänzung lässt sich die benötigte Bedingung realisieren: Der letzte Übergang zu einem akzeptierenden Zustand bezieht sich nur auf das oberste Element des Stacks und als Eingabe wird \(\epsilon\) angegeben, da am Ende des eingelesenen Wortes keine weitere Eingabe mehr erfolgt.

\begin{Aufgaben}
	\item Erstellen Sie einen Kellerautomaten, der das Klammerproblem löst, also alle Eingaben akzeptiert bei denen es zu jeder öffnenden Klammer auch eine schließende Klammer gibt. Verwenden sie zur Vereinfachung neben den Klammern für alle anderen Symbole in der Eingabe ein Asterisk.
	\AufgabenHinweis{Der letzte Abschnitt vor der Aufgabe sollte beachtet werden und die Anzahl der Zustände ist sehr gering.}
	\AufgabenLoesung{Der zweite Zustand bei der Lösung wird nur gebraucht, um am Ende den Stack darauf zu überprüfen, dass dieser leer ist.
		\begin{figure}[ht]
			\(\Sigma = \{a,\ldots, z, a,\ldots, Z, (, )\} \)\\
			\(Z = \{s_0, s_1\}\)\\
			\(z_0 = s_0\)\\
			\(E = \{s_1\}\)\\
			\(\Gamma = \{(),0\} \)\\
			\(\# = 0\)\\
			\(\varphi = \)\\
			\hspace*{0.7cm}
			\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
				\scaleTikz{0.8}
				\node[state,initial]	(s_0) {$s_{0}$};
				\node[state,accepting]	(s_1) [right=of s_0]  {$s_{1}$};
				\path[->] 
					(s_0) edge node[above] {\(\epsilon\),0,0} (s_1)
					(s_0) edge[loop above] node[above,text width=1cm] {*,(;( \\ *,0;0 } ()
					(s_0) edge[loop below] node[below,text width=1cm] {(,(;((\\ (,0,(0 \\ ),(,\(\epsilon\)} ();
			\end{tikzpicture}
			\caption{Lösung für das Klammerproblem mit einem Kellerautomaten}
		\end{figure}
	}
	\TextFeld{5cm}
\end{Aufgaben}


\section{Turingmaschine}
\todo[inline]{Turingmaschine: Gleich mächtig wie ein Kellerautomat mit zwei Kellern}

\chapter{Sammlung von Aufgaben}
Zur Übung und Vertiefung sind hier verschiedene Aufgaben angegeben.

\begin{Aufgaben}
	\item Geben Sie an, welche fünf Elemente zur vollständigen Beschreibung eins endlichen Automaten gehören. Gehen Sie dabei auf die Unterschiede zwischen einem Transduktor und einem Akzeptor ein.
	\AufgabenLoesung{Für einen Transduktor benötigt man die Menge der Zustände \(Z\), die Eingabe \(\Sigma\), die Ausgabe \(A\), den Startzustand \(z_0\) und die Zustandsübergangsfunktion \(\varphi\). Letztere kann entweder durch eine Tabelle oder ein Diagramm erfolgen. Beim Akzeptor wird anstelle der Ausgabemenge die Menge der akzeptierten Endzustände \(E\) als Angabe benötigt.}
	\TextFeld{3cm}

	\item Betrachten Sie den Akzeptor für Klassenbezeichner aus Abbildung \ref{Akzeptor_Klassenbezeichner} und verändern ihn so, dass der Klassenname mindestens vier Zeichen lang ist. Sie müssen nur das Zustandsübergangsdiagramm angeben.
	\TextFeld{4cm}

	\item Erstellen Sie einen Automaten, an dem für 1,50 Euro in 1 Euro oder 50 Cent Stücken, ein spezielles Buch ausgeliehen werden kann. Die Besonderheit dieses Automaten soll darin liegen, dass er nur maximal drei dieser Bücher beherbergen kann. Entsprechend soll er auf Eingaben reagieren, wenn er aktuelle keine Bücher mehr hat bzw. zu viele Bücher versucht werden zurückzugeben.
	
	\item Bei einer Verkehrsampel dürfen die Lichter nur in bestimmten Kombinationen leuchten. Erstellen Sie einen Akzeptor, dem die Schaltzustände der drei Lampen in der Reihenfolge rot, gelb und grün als ein oder aus übergeben werden. Er soll nur die gültigen Farbkombinationen akzeptieren.
	\AufgabenHinweis{Es gibt nur vier verschiedene Farbkombination, die akzeptiert werden. Schreiben Sie sich diese explizit auf um dafür den Akzeptor zu erstellen.}
	\TextFeld{4cm}
\end{Aufgaben}

\appendix

\chapter{Hinweise}
\hinweiszeigen

\chapter{Lösungen}
 \loesungzeigen

\chapter{Umsetzungen in Programmiersprachen} \label{umsetzung_allgemein}
\section{Java}
Die Umsetzung des Parsers in der Programmiersprache Java:
\begin{lstlisting}[language=Java]
public boolean parser(String wort) {
	int zustand = 1;
	int pos = 0;
	while (pos < wort.length()) {
		char symbol = wort.charAt(pos);
		if (zustand == 1) {
			if (symbol == 'a' || symbol == 'c') {
				zustand = 3;
			} else if (symbol == 'b') {
				zustand = 2;
			} else {
				return false;
			}
		} else if (zustand == 2) {
			if (symbol == 'a' || symbol == 'b') {
				zustand = 3;
			} else {
				return false;
			}
		} else { //zustand == 3
			if (symbol == 'b') {
				zustand = 3;
			} else if (symbol == 'a') {
				zustand = 2;
			} else {
				return false;
			}
		}
		pos ++;
	}
	return (zustand == 3);
}
\end{lstlisting}

\section{Python}
Die Umsetzung des Parsers in der Programmiersprache Python:
\begin{lstlisting}[language=python]
def parser(wort):
	zustand = 1
	pos = 0
	while pos < len(wort):
		symbol = wort[pos]
		if zustand == 1:
			if symbol == 'a' or symbol == 'c':
				zustand = 3
			elif symbol == 'b':
				zustand = 2
			else:
				return False
		elif zustand == 2:
			if symbol == 'a' or symbol == 'b':
				zustand = 3
			else:
				return False
		else:  #zustand == 3
			if symbol == 'b':
				zustand = 3
			elif symbol == 'a':
				zustand = 2
			else:
				return False
		pos += 1
	return zustand == 3
\end{lstlisting}



\bibliography{../../zusatz/projekt}

\nocite{MSWNW2012}
\nocite{TantauIF2012}
\nocite{Clausing2003}

\listoftodos
\todototoc


\end{document}
