\documentclass[12pt]{article}

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

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 3}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\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}
\subsubsection*{(a)}
Seien $k \ge 0$ und $m,n > 0$.
\begin{eqnarray*}
	F_L(a^m) & = & \{a^k b^n a^{m+k+n}\} \\
	F_L(a^mb^n) & = & \{b^k a^{m+n+k}\} \\
	F_L(a^mb^na^k) & = & \{a^{m+n-k}\} \\
	F_L(\varepsilon) & = & L \\
	F_L(a^mb^na^{n+m}) & = & \{\varepsilon\} \\\\
	\Rightarrow \mathcal{F}_L & = & \{F_L(a^m), F_L(a^mb^n), F_L(a^mb^na^k), F_L(a^mb^na^{n+m}), F_L(\varepsilon)\}
\end{eqnarray*}

\subsubsection*{(b)}
Seien $u,u' \in \{a,b\}^*$.
\begin{itemize}
	\item $u$ enthält $\ge 3$ aufeinanderfolgende $a$'s: $(u \notin L(M)) \Rightarrow F_L(u) = \emptyset$
	\item $u$ enthält $< 3$ aufeinanderfolgende $a$'s: $(u' \in L(M))$
\end{itemize}
Sei $\varepsilon := \# a$'s am Ende von $u'$ (da $u \in L(M): \varepsilon < 3$). \\
$F_L(u') = \{(a^{i_k}b^{j_k})^k\} \quad k \in \SetN, i_k, j_k \in \SetN \quad \forall i,j \in \SetN, i_0 < 3-\varepsilon$. \\
$\Rightarrow \mathcal{F}_L = \{F_L(u')\}$.

\subsubsection*{(c)}
Sei $u \in \Sigma^*$ mit $m=\#_a(u)$ und $n=\#_b(u)$. \\
$F_L(u) = \{u' | \#_a(u')-\#_b(u') = \#_b(u)-\#_a(u)\}$. \\
$\Rightarrow \mathcal{F}_L \{F_L(u)\}$.

\newpage
\section*{Aufgabe 2}
\bild{16}{a2}{DEA M' zu Aufgabe 2}{a2dea}
\noindent Man beginnt bei Zustand 0 von $M$ und überführt ihn in Zustand $\{0\}$ von $M'$. Dann verfolgt man alle Kanten und fasst alle Zustände, die über Einlesen eines Zeichens erreicht werden, zu einem neuen Zustand zusammen. Enthält einer der zusammengesetzten Zustände einen Endzuständ, ist auch der neue Zustand ein solcher. Man rekurriert, wobei man bei jedem Zustand die Menge aller Kanten der jeweiligen Zustände von $M$ betrachtet und zusammengefasst verfolgt. Man erhält $M'$ mit
\begin{eqnarray*}
	M' &=& (\Sigma, Q, s, F, \Delta) \\
	\Sigma &=& \{a,b\} \\
	Q &=& \{\{0\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{0,1,2\},\{1,2,3\},\{2,3\}\} \\
	s &=& \{0\} \\
	F &=& Q \setminus \{\{s\} \cup \{2\}\} \\
	\Delta &&\mbox{ sei über die Skizze oben gegeben}
\end{eqnarray*}

\newpage
\section*{Aufgabe 3}
\bild{12}{a3}{Minimaler DEA zu Aufgabe 3}{a3dea}
\begin{center}
\begin{tabular}{c|ccccc}
4 & U &&&& \\
3 & U & N &&& \\
2 & U & U & U && \\
1 & U & U & U & N & \\
0 & U & U & U & U & U \\ \hline
& 5 & 4 & 3 & 2 & 1
\end{tabular}
\end{center}

\noindent Zu Beginn der Betrachtung stelle ich fest, dass es im DEA $M$ keinen Zustand gibt, der nicht vom Startzustand aus nicht zu erreichen wäre. Nun überprüft man alle Paare von Zuständen auf Unterscheidbarkeit. Hierbei sind sofort alle Paare, deren eine Komponente ein Endzustand ist, unterscheidbar. Somit ist 5 zu jedem anderen Zustand unterscheidbar und wird dadurch in $\{5\}$ überführt. \\
Auch 1 und 3 sind unterscheidbar, da 3 mit beiden Kanten auf einen Endzustand zeigt und 1 nicht. Selbiges gilt analog für 2 und 3, 1 und 4, 0 und 3, 0 und 4, sowie 2 und 4. \\
3 und 4 sind \textit{nicht} unterscheidbar, da sie beide mit beiden Kanten auf einen Endzustand zeigen. \\
Von 1 und 2 erreicht man jeweils mit einem beliebigen Wort $w \in \{a,b\}^2$ ein Endzustand, was für 0 nicht gilt. Somit sind 0 und 1, sowie 0 und 2 unterscheidbar. \\
1 und 2 sind \text{nicht} unterscheidbar, da beide mit den gleichen Kanten auf den neuen Zustand $\{3,4\}$, hervorgegangen aus den nichtunterscheidbaren Zuständen 3 und 4, zeigen. Man fasst sie daher zum Zustand $\{1,2\}$ zusammen. \\
Den - wie eben gezeigt - zu allen anderen unterscheidbaren Knoten 0 macht man zu $\{0\}$ und erhält die oben angegebene Visualisierung von $M'$. \\
$M'$ lässt sich wie folgt formal spezifizieren:
\begin{eqnarray*}
	M' &=& (\Sigma, Q, s, F, \Delta) \\
	\Sigma &=& \{a,b\} \\
	Q &=& \{\{0\}, \{1,2\}, \{3,4\}, \{5\}\} \\
	s &=& \{0\} \\
	F &=& \{\{5\}\} \\
	\Delta &&\mbox{ sei über die Skizze oben gegeben}
\end{eqnarray*}

\end{document}