\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 3}
\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)}
Idee: \\
Ein NEA bzw. DEA kann sich nicht merken, wie groß die Differenz zwischen den $a$'s und $b$'s im Präfix $u$ ist. Somit gibt es für die Sprache $L_a$ keinen NEA oder DEA, der sie akzeptiert. Die Sprache $L_a$ ist also nicht regulär. \\[0.3cm]
Beweis durch Myhill-Nerode: \\
$L_a$ ist keine DEA-Sprache $\Leftrightarrow \mathcal{F}_{L_a} = \{C_{L_a}(w) \; | \; w \in \{a,b\}^*\}$ ist nicht endlich. \\
Angenommen, es gibt einen DEA $M = (\Sigma, Q, s, F, \Delta)$ mit $L_a(M) = L_a$. Dann muss gelten:
$$w \in \{a,b\}^*: \; C_{L_a}(w) = \bigcup \{L_{a_q'} \; | \; q' \in \delta_q(w)\}$$
Die Zustandsmenge $Q$ ist jedoch nicht endlich, da man für jede Differenz von $a$ und $b$ im Präfix $u$ von $w$ einen neuen Zustand bräuchte und die Differenz beliebig groß werden kann. \\
Da die Zustandsmenge $Q$ nicht endlich ist, ist die Anzahl der verschiedenen $\delta_q(w)$ nicht endlich.
$$\Rightarrow \{C_{L_a}(w) \; | \; w \in \{a,b\}^*\} \text{ ist nicht endlich.}$$
Somit ist durch Myhill-Nerode bewiesen, dass die Sprache $L_a$ nicht regulär ist.

\subsubsection*{(b)}
Die Sprache $L_b$ ist regulär.
\bild{12}{b3a1b.png}{Aufgabe 1b: NEA, der die Sprache akzeptiert}{a1b}

\subsubsection*{(c)}
Idee: \\
Ein NEA oder DEA kann weiß nicht, wieviele $a$'s er schon gelesen hat und kann somit auch nicht entscheiden, ob die Anzahl der $b$'s ein ganzzahliges Vielfaches der Anzahl der $a$'s ist. Die Sprache $L_c$ ist nicht regulär. \\[0.3cm]
Beweis durch Myhill-Nerode: \\
$L_c$ ist keine DEA-Sprache $\Leftrightarrow \mathcal{F}_{L_c} = \{C_{L_c}(w) \; | \; w \in \Sigma^*\}$ ist nicht endlich. \\
Angenommen, es gibt einen DEA $M = (\Sigma, Q, s, F, \Delta)$ mit $L_c(M) = L_c$. Dann muss gelten:
$$w \in \{a,b\}^*: \; C_{L_c}(w) = \bigcup \{L_{c_q'} \; | \; q' \in \delta_q(w)\}$$
Die Zustandsmenge $Q$ ist jedoch nicht endlich, da man für jedes $i$ alle ganzzahligen Vielfache von $i$ an zusätzlichen Zuständen bräuchte, um die Sprache $L_c$ zu entscheiden. \\
Da die Zustandsmenge $Q$ nicht endlich ist, ist die Anzahl der verschiedenen $\delta_q(w)$ nicht endlich.
$$\Rightarrow \{C_{L_c}(w) \; | \; w \in \{a,b\}^*\} \text{ ist nicht endlich.}$$
Somit ist durch Myhill-Nerode bewiesen, dass die Sprache $L_c$ nicht regulär ist.

\subsubsection*{(d)}
Die Sprache $L_d$ ist regulär. \\
Anmerkung zum Automaten:
\begin{eqnarray*}
	Q & = & \{0,...,5\} \\
	s & = & 0 \\
	F & = & \{0\}
\end{eqnarray*}
Übergang: \\
Im Zustand $q$ geht der Automat nach Eingabe von $x$ zu $(2q + x) \mod 6$. \\[0.5cm]
In der Zeichnung werden die Binärzahlen der Übersichtlichkeit halber als Dezimalzahlen (modulo 6) dargestellt.
\bild{14}{b3a1d.png}{Aufgabe 1d}{a1d}


\newpage

\section*{Aufgabe 2}
\subsubsection*{(a)}
\bild{12}{b3a2a.png}{Aufgabe 2a}{a2a}

\subsubsection*{(b)}
\bild{16}{b3a2b.png}{Aufgabe 2b}{a2b}


\newpage

\section*{Aufgabe 3}
\subsubsection*{(a)}
\bild{12}{b3a3a.png}{Aufgabe 3a}{a3a}
Der Automat besitzt 4 Zustände.

\subsubsection*{(b)}
Eine untere Schranke für die Anzahl der Zustände eines äquivalenten DEA, der die Sprache akzeptiert ist:
$$2^{2(k+1)} = 2^{|Q|}$$

\end{document}
