\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 7 \\
        Übungsgruppe 7 - Mi, 16-18 Uhr \\
        Elena Kvassova}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
        Dirk Heine (Matrikelnummer 2030941)}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1}
Der Automat akzeptiert Zahlen, die vor dem Komma beliebig viele Ziffern aus der Menge \{0,...,9\} haben können und nach dem Komma die
Ziffern \{1,2,4,5,7,8\}. Diese Zahlen kann man als Dezimalzahlen charakterisieren.

\section*{Aufgabe 3}
Es ist $Q=\{q_0, q_1, ..., q_7\}$, $\Sigma=\{0,1\}$ und $F=\{q_3, q_4, q_6\}$. \\
Der einfacheren Schreibweise wegen drehen wir die Paare in die lexikographische Reihenfolge.
\begin{enumerate}[1.]
	\item Die Paare $(q_0, q_3)$, $(q_1, q_3)$, $(q_2, q_3)$, $(q_3, q_4)$, $(q_3, q_5)$, $(q_3, q_6)$, $(q_3, q_7)$, 
		$(q_0, q_4)$, $(q_1, q_4)$, $(q_2, q_4)$, $(q_4, q_5)$, $(q_4, q_6)$, $(q_4, q_7)$, $(q_0, q_6)$, 
		$(q_1, q_6)$, $(q_2, q_6)$, $(q_5, q_6)$ und $(q_6, q_7)$ werden markiert, da $F=\{q_3, q_4, q_6\}$ ist.
	\item Wir durchlaufen die unmarkierten Paare in der Reihenfolge $(q_0, q_1)$, $(q_0, q_2)$, $(q_0, q_5)$, 
		$(q_0, q_7)$, $(q_1, q_2)$, $(q_1, q_5)$, $(q_1, q_7)$, $(q_2, q_5)$, $(q_2, q_7)$ und $(q_5, q_7)$.
	
	\begin{itemize}
		\item $(q_0, q_1)$: Die $\delta$-Paare $(\{\delta(a,x), \delta(b,x)\} \text{ für } x\in \{0,1\})$ sind
			$(q_1, q_2)$ (unmarkiert $u$) und $(q_3, q_5)$ (markiert $m$). Also wird $(q_0, q_1)$ markiert.
			Da $L(q_0,q_1)$ leer ist, geschieht nichts weiter.
			
		\item $(q_0, q_2)$: $\delta$-Paare sind $(q_1, q_2)=u$ und $(q_4, q_5)=m$. Also wird $(q_0, q_2)$ markiert.
			Da $L(q_0, q_2)$ leer ist, geschieht nichts weiter.
			
		\item $(q_0, q_5)$: $\delta$-Paare sind $(q_1, q_6)=m$ und $(q_5, q_7)=u$. Also wird $(q_0, q_5)$ markiert.
			Da $L(q_0, q_5)$ leer ist, geschieht nichts weiter.
			
		\item $(q_0, q_7)$: $\delta$-Paare sind $(q_1, q_7)=u$ und $(q_5, q_7)=u$, also $(q_0, q_7) \rightarrow L(q_1, q_7)$
			und $(q_0, q_7) \rightarrow L(q_5, q_7)$.
			
		\item $(q_1, q_2)$: $\delta$-Paare sind $(q_2, q_2)$ (kein Paar) und $(q_3, q_4)=m$. Also wird $(q_1, q_2)$ markiert.
			Da $L(q_1, q_2)$ leer ist, geschieht nichts weiter.
			
		\item $(q_1, q_5)$: $\delta$-Paare sind $(q_2, q_6)=m$ und $(q_3, q_7)=m$. Also wird $(q_1, q_5)$ markiert.
			Da $L(q_1, q_5)$ leer ist, geschieht nichts weiter.
			
		\item $(q_1, q_7)$: $\delta$-Paare sind $(q_2, q_7)=u$ und $(q_3, q_7)=m$. Also wird $(q_1, q_7)$ markiert.
			$L(q_1, q_7)$ enthält $(q_0, q_7)$, das markiert wird. Da $L(q_0, q_7)$ leer ist, geschieht nichts weiter.
			
		\item $(q_2, q_5)$: $\delta$-Paare sind $(q_2, q_6)=m$ und $(q_4, q_7)=m$. Also wird $(q_2, q_5)$ markiert.
			Da $L(q_2, q_5)$ leer ist, geschieht nichts weiter.
			
		\item $(q_2, q_7)$: $\delta$-Paare sind $(q_2, q_7)=u$ und $(q_4, q_7)=m$. Also wird $(q_2, q_7)$ markiert.
			Da $L(q_2, q_7)$ leer ist, geschieht nichts weiter.
			
		\item $(q_5, q_7)$: $\delta$-Paare sind $(q_6, q_7)=m$ und $(q_7, q_7)$ (kein Paar). Also wird $(q_5, q_7)$ markiert.
			$L(q_5, q_7)$ enthält $(q_0, q_7)$, das markiert wird. Da $L(q_0, q_7)$ leer ist, geschieht nichts weiter.
	\end{itemize}
\end{enumerate}

\end{document}
