\documentclass[12pt]{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 4}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Di, 9-11 Uhr, Andreas Augustin \\
	}
\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{\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)}
$$L_a = \{w \in \{a,b\}^* \; | \; \#_a(w) \le \#_b(w) \text{ und } aa \text{ ist kein Teilwort von } w\}$$
\bild{8}{a1a.png}{Automat zu Aufgabe 1a}{a1a} \\
Die Sprache ist regulär. \\
Regulärer Ausdruck:
$$b^*(ab)^*(bb^*a)^*b^*$$

\subsubsection*{(b)}
$$L_b = \{w \in \{a,b\}^* \; | \; \#_a(w) \le \#_b(w) \text{ und } aaa \text{ ist kein Teilwort von } w\}$$
Idee: \\
Die Sprache ist nicht regulär, da man für jede Permutation z.B. von dem Wort $abbbbaa$ ($a,bbbaba, abbbaab, abbabab, ...$) neue
Zustände bräuchte. Anders ausgedrückt: die Menge der Fortsetzungssprachen ist nicht endlich. \\
Beweis durch Myhill-Nerode: \\
$L_b$ ist keine DEA-Sprache $\Leftrightarrow \mathcal{F}_{L_b} = \{C_{L_b}(w) \; | \; w \in \{a,b\}^*\}$ ist nicht endlich. \\
Angenommen, es gibt einen DEA $M=(\Sigma, Q, s, F, \Delta)$ mit $L_b(M) = L_b$. Dann muss gelten:
$$w \in \{a,b\}^*: C_{L_b}(w) = \bigcup\{L_{b_{q'}} \; | \; q' \in \delta_q(w)\}$$
Die Zustandsmenge $Q$ ist jedoch nicht endlich, da man für jede Anordnung (Permutation) der $a$'s und $b$'s im Wort neue Zustände bräuchte (vgl. Idee). \\
Da die Zustandsmenge $Q$ nicht endlich ist, ist die Anzahl der verschiedenen $\delta_q(w)$ nicht endlich.
$$\Rightarrow \{C_{L_b}(w) \; | \; w \in \{a,b\}^*\} \text{ ist nicht endlich}$$
Somit ist nach Myhill-Nerode die Sprache $L_b$ nicht regulär.

\subsubsection*{(c)}
$$L_c = \{w \in \{a,b\}^* \; | \; \#_a(w) \text{ gerade}\}$$
\bild{6}{a1c.png}{Automat zu Aufgabe 1c}{a1c} \\
Die Sprache ist regulär. \\
Regulärer Ausdruck:
$$(b^*ab^*a)^*b^*$$


\newpage

\section*{Aufgabe 2}
nach Regel 1:
\begin{eqnarray*}
	\{0,3\} & \in & U \\
	\{1,3\} & \in & U \\
	\{2,3\} & \in & U \\
	\{4,3\} & \in & U \\
	\{6,3\} & \in & U \\
	\{7,3\} & \in & U \\
	\{0,5\} & \in & U \\
	\{1,5\} & \in & U \\
	\{2,5\} & \in & U \\
	\{4,5\} & \in & U \\
	\{6,5\} & \in & U \\
	\{7,5\} & \in & U
\end{eqnarray*}
nach Regel 2:
\begin{eqnarray*}
	\{0,1\} \stackrel{b}{\rightarrow} \{3,5\} \Rightarrow \{0,1\} & \in & U \\
	\{0,2\} \stackrel{b}{\rightarrow} \{3,5\} \Rightarrow \{0,2\} & \in & U \\
	\{0,4\} \stackrel{b}{\rightarrow} \{0,5\} \Rightarrow \{0,4\} & \in & U \\
	\{0,6\} \stackrel{b}{\rightarrow} \{5,7\} \Rightarrow \{0,6\} & \in & U \\
	\{0,7\} \stackrel{b}{\rightarrow} \{0,5\} \Rightarrow \{0,7\} & \in & U \\[0.3cm]
	\{1,2\} \stackrel{a}{\rightarrow} \{2,2\}, \{1,2\} \stackrel{b}{\rightarrow} \{3,3\} \Rightarrow \{1,2\} & \not\in & U \\
	\{1,4\} \stackrel{b}{\rightarrow} \{0,3\} \Rightarrow \{1,4\} & \in & U \\
	\{1,6\} \stackrel{a}{\rightarrow} \{2,5\} \Rightarrow \{1,6\} & \in & U \\[0.3cm]
	\{2,4\} \stackrel{a}{\rightarrow} \{1,2\} \Rightarrow \{2,4\} & \in & U \\
	\{2,6\} \stackrel{a}{\rightarrow} \{2,5\} \Rightarrow \{2,6\} & \in & U \\
	\{2,7\} \stackrel{b}{\rightarrow} \{0,3\} \Rightarrow \{2,7\} & \in & U \\[0.3cm]
	\{3,5\} \stackrel{a}{\rightarrow} \{3,4\} \Rightarrow \{3,5\} & \in & U \\[0.3cm]
	\{4,6\} \stackrel{b}{\rightarrow} \{1,5\} \Rightarrow \{4,6\} & \in & U \\
	\{4,7\} \stackrel{a}{\rightarrow} \{1,2\}, \{4,7\} \stackrel{b}{\rightarrow} \{0,0\} \Rightarrow \{4,7\} & \not\in & U \\[0.3cm]
	\{6,7\} \stackrel{b}{\rightarrow} \{0,7\} \Rightarrow \{6,7\} & \in & U
\end{eqnarray*}
\begin{center}
\begin{tabular}{c|ccccccc}
	  & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline
	0 & X & X & X & X & X & X & X \\
	1 & X & X & X & X & X &   &   \\
	2 & X & X & X & X & X &   &   \\
	3 & X & X & X & X &   &   &   \\
	4 &   & X & X &   &   &   &   \\
	5 & X & X &   &   &   &   &   \\
	6 & X &   &   &   &   &   &
\end{tabular}
\end{center}
\bild{10}{a2.png}{Automat zu Aufgabe 2}{a2}


\newpage

\section*{Aufgabe 3}
GKB-Sprachen sind äquivalent zu regulären Sprachen, da man das Übergangsdiagramm eines Automaten als gerichteten Graphen mit Kantenbeschriftung auffassen kann.


\section*{Aufgabe 4}
Gegeben: \\
DEA $M$ mit $\Sigma$ Eingabealphabet und $n$ Zuständen. Es soll gelten:
$$L(M) = \Sigma^* \Leftrightarrow M \text{ akzeptiert alle Worte über } \Sigma \text{ der Länge höchstens } n$$
Zu zeigen: \\
$L$ ist DEA-Sprache. \\[0.3cm]
Beweis durch Myhill-Nerode: \\
$M=(\Sigma, Q, s, F, \Delta)$. Zeige, dass $\mathcal{F}_L$ endlich.
$$w \in \Sigma^*: C_L(w) = \bigcup \{L_{q'} \; | \; q' \in \delta_q(w)\}$$
Die Zustandsmenge $Q$ ist endlich (da $M$ $n$ Zuständen hat) $\Rightarrow \#$ der verschiedenen $\delta_q(w)$'s ist endlich.
$$\Rightarrow \{C_L(w) \; | \; w \in \Sigma^*\} \text{ endlich}$$

\end{document}
