\documentclass[loesungsseite]{schullzk}
\usepackage[utf8]{inputenc}

% 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 der Informatikfachseminare Arnsberg, Hamm und Solingen}]{hyperref}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\ihead{Kapiteltests zu Automaten, Sprachen, \ldots}
\chead{}

\svnid{$Id: leitprogramm_automaten_kapiteltest.tex 1340 2015-09-17 20:56:33Z pieper $}

\begin{document}

\section*{Zu Kapitel 2}
\begin{enumerate}
	\item Beschreiben Sie mit eigenen Worten, was ein Fehlerzustand ist, wie man ihn erreicht und auf welche Weise er in Zustandsübergangsdiagrammen eingezeichnet wird.
	\item Geben Sie einen vollständigen Automaten mit einer Zustandsübergangstabelle an, der folgende Situation realisiert:
	
	In einem Freizeitpark befindet sich eine Wasserrutsche mit Booten. Am Ende der Wasserrutsche gibt es einen Sensor, der registriert, ob der Auslaufbereich von einem Boot belegt wird und wann dieser Auslaufbereich wieder frei ist. Ein weiterer Sensor gibt an, ob sich ein Boot auf der Startrampe befindet oder nicht. Das Starten des Bootes muss durch einen Mitarbeiter mit Hilfe eines Knopfes geschehen. Dabei bekommt der Mitarbeiter durch eine Ampel angezeigt, ob er die Rutsche, durch Anheben der Startrampe, starten kann. Das Absenken der Startrampe geschieht automatisch und wird an den Automaten weitergegeben. Außerdem bekommt ein Parkbesucher durch eine weitere Ampel angezeigt, ob er ein Boot auflegen darf.

	Gehen Sie für den Startzustand von der Öffnung des Parks am Morgen aus. Zur Übersichtlichkeit ist es praktisch, bei jedem Zustand in Stichpunkten mit anzugeben, was er repräsentiert. Außerdem müssen nur solche Fälle bei der Eingabe betrachtet werden, die dem normalen Ablauf entsprechen.
\end{enumerate}

\loesung{
	\begin{enumerate}
		\item 

		\item 
			\(\Sigma = \{\mbox{BootAuf, Knopf, RampeRunter, AuslaufVoll, AuslaufFrei}\} \)\\
			\(A = \{\mbox{MgBr, Mr, Bg, Mg, -}\}\)\\
			\(Z = \{s_0, s_1, s_2, s_3, s_4, s_5, s_6, s_7, s_8\}\)\\
			\(z_0 = s_0\)\\
			\(\varphi = \)\\
			\begin{tabular}{l|lllll|l}
				& BootAuf & Knopf & RampeRunter & AuslaufVoll & AuslaufFrei & \\
				\hline
				\(s_0\) & \(s_1 / MgBr\) & & & & & Startzustand, alles frei \\
				\(s_1\) & & \(s_2 / Mr \) & & & & Boot wartet\\
				\(s_2\) & & & \(s_3 / Bg \) & \(s_4 / - \) & & Boot startet\\
				\(s_3\) & \(s_8 / Br \) & & & \(s_6 / - \)  & & Rampe unten, Boot fährt\\
				\(s_4\) & & & \(s_6 / Bg \) & & \(s_5 / - \) & Boot unten, Rampe oben\\
				\(s_5\) & & & \(s_0 / Bg \) & & & Rampe oben, Auslauf voll \\
				\(s_6\) & \(s_7 / Br\) & & & & \(s_0 / -\) & Rampe frei, Auslauf voll\\
				\(s_7\) & & & & & \(s_1 / Mg\) & Boot wartet, Auslauf voll \\
				\(s_8\) & & & & \(s_7 / -\) & & Boot wartet, Boot fährt \\
			\end{tabular}
	\end{enumerate}
}

\clearpage

\section*{Zu Kapitel 3}

\begin{enumerate}
	\item Erläutern Sie die Unterschiede zwischen einem Akzeptor und einem Transduktor.
	\item Geben Sie an, was einen endlichen Automaten endlich macht.
	\item Erstellen Sie das Zustandsübergangsdiagramm für einen Automaten, der die Eingaben abab und abba akzeptiert.
	\item Vergleichen Sie nichtdeterministische endliche Automaten (NEA) und deterministische endliche Automaten (DEA) miteinander bzgl. ihrer Gemeinsamkeiten und Unterschiede.
\end{enumerate}


\loesung{
}

\clearpage

\section*{Zu Kapitel 5}

\begin{enumerate}
	\item Erläutern Sie den Aufbau eine rechtsregulären Grammatik an einem kleinen Beispiel.
	\item Begründen Sie, weshalb eine Grammatik mit folgenden Produktionsregeln nicht regulär ist und geben Sie Wörter an, die mit dieser Grammatik gebildet werden können. Gestartet wird mit A:\\
	\(P = \{\mbox{A\textrightarrow aA\textbar B, B\textrightarrow aCa\textbar C, C\textrightarrow b\textbar bC}\}\) 
\end{enumerate}


\loesung{
}

\clearpage

\section*{Zu Kapitel 6}

\begin{enumerate}
	\item Beschreiben Sie, was eine reguläre Sprache ist und welche Einschränkungen sie hat.
	\item Geben Sie zu der folgenden regulären Sprache das Zustandsübergangsdiagramm eines entsprechenden Akzeptors an: \\
	\(L = \{\mbox{ab,b,ca}^n,\mbox{c}^m\mbox{a} | n,m \geq 0 \}\)
\end{enumerate}


\loesung{
}


\end{document}
