\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 2}
\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}
Zeige: $\displaystyle \bigcup \{A_i \; | \; i \in \SetN\}$ ist abzählbar. \\[0.3cm]
Beweis: \\
Sei $A_i := \{a_{i0}, a_{i1}, ..., a_{i{k_i}}\}, \; k_i \in \SetN$ fest, $i \in \SetN$ beliebig. \\
Definiere weiterhin
$$B_i := \{a_{im} \; | \; m \in \SetN\} \; \forall i \in \SetN$$
Dann gilt: \\
Jede Menge $B_i, i \in \SetN$, ist wegen $m \in \SetN$ abzählbar, und die Menge aller $B_i$ ist wegen $i \in \SetN$ ebenfalls abzählbar. Nach einem Satz aus der Vorlesung ist
die Vereinigung abzählbar vieler abzählbarer Mengen ebenfalls abzählbar.
$$\Rightarrow \bigcup \{B_i \; | \; i \in \SetN\} \text{ ist abzählbar} \quad (*)$$
Weiterhin gilt:
\begin{eqnarray*}
	& & A_i \subset B_i \quad \forall i \in \SetN \\
	& \Rightarrow & \bigcup \{A_i \; | \; i \in \SetN\} \subset \bigcup \{B_i \; | \; i \in \SetN\} \\
	& \stackrel{(*)}{\Rightarrow} & \bigcup \{A_i \; | \; i \in \SetN\} \text{ ist abzählbar.}
\end{eqnarray*}
\QED

\newpage
\section*{Aufgabe 2}
Der Automat geht in den nächsten Zustand über, wenn er ein $a$ liest.
\bild{12}{a2.jpg}{Automat zu Aufgabe 2}{}

\newpage
\section*{Aufgabe 3}
$$L = \{w \in \{a,b\}^* \; | \; (\#a \text{'s in } w) \mod 3 = 0 \AND (\#b \text{'s in } w) \mod 3 = 0\}$$

\subsubsection*{(a)}
\begin{eqnarray*}
	C_L (aaabbb) & = & L \\
	C_L (aaa) & = & L \\
	C_L (bbb) & = & L \\
	C_L (aabbb) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 1 \AND (\#b \text{'s in } x) \mod 3 = 0\} \\
	& = & L_1 \\
	C_L (abbb) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 2 \AND (\#b \text{'s in } x) \mod 3 = 0\} \\
	& = & L_2 \\
	C_L (aaabb) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 0 \AND (\#b \text{'s in } x) \mod 3 = 1\} \\
	& = & L_3 \\
	C_L (aaab) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 =  0 \AND (\#b \text{'s in } x) \mod 3 = 2\} \\
	& = & L_4 \\
	C_L (aabb) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 1 \AND (\#b \text{'s in } x) \mod 3 = 1\} \\
	& = & L_5 \\
	C_L (abb) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 2 \AND (\#b \text{'s in } x) \mod 3 = 1\} \\
	& = & L_6 \\
	C_L (aab) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 1 \AND (\#b \text{'s in } x) \mod 3 = 2\} \\
	& = & L_7 \\
	C_L (ab) & = & \{x \in \{a,b\}^* \; | \; (\#a \text{'s in } x) \mod 3 = 2 \AND (\#b \text{'s in } x) \mod 3 = 2\} \\
	& = & L_8
\end{eqnarray*}
$$\mathcal{F}_L = L \cup L_1 \cup L_2 \cup L_3 \cup L_4 \cup L_5 \cup L_6 \cup L_7 \cup L_8$$

\subsubsection*{(b)}
Zustände: $\{0,1,2\} \times \{0,1,2\}$ \\
Startzustand: $(0,0)$ \\
Endzustand: $(0,0)$ \\
Übergangsfunktion:
$$(x,y) \Rightarrow \left\{\begin{array}{cl}((x+1) \mod 3, y) & : \text{liest } a \\ (x,(y+1) \mod 3) & : \text{liest } b\end{array}\right.$$
\newpage
Zeichnung:

\newpage
\section*{Aufgabe 4}
\begin{enumerate}
	\item $0^*1^*$. \\
		Der Automat liest im Zustand $A$ endlich viele 0. Liest er eine 1 geht er in Zustand $B$ über. Dort akzeptiert er oder liest er eine endliche Folge von 1 und akzeptiert dann.
		Akzeptiert er hier noch nicht, sondern liest noch eine 0, dann geht der Automat in Zustand $C$ über, wo er in einer endlosen Schleife hängt. Da Zustand $C$ kein akzeptierender
		Endzustand ist, akzeptiert der Automat nur $0^*1^*$.
	\item $(0^*1^*)^*01$. \\
		Der Automat liest im Zustand $A$ endlich viele 0. Beim Lesen einer 1 geht er in Zustand $B$ über. Dort kann er entweder eine endliche Folge von 1 lesen oder er geht beim Lesen einer
		0 in den Zustand $C$ über. Geht er von Zustand $C$ beim Lesen von 0 in Zustand $A$ über, beginnt der eben beschriebene Vorgang von vorne. Liest er jedoch eine 1, so geht er in
		Zustand $D$ über und kann dort akzeptieren. Akzeptiert er dort noch nicht, so geht er beim Lesen einer 0 wieder in Zustand $A$ über und es geht von vorne los (siehe Anfang der Beschreibung).
		Liest er eine 1, so geht er in Zustand $B$ über und die oben beschriebenen Vorgänge gehen ab Zustand $B$ weiter.
\end{enumerate}

\newpage
\section*{Aufgabe 5}
\begin{enumerate}
	\item Variante: \\
		Ein endlicher Automat kann sich keine Zahl merken, die größer ist als die begrenzte Anzahl seiner Zustände. \\
		\begin{enumerate}[(a)]
			\item Er kann sich nicht merken, wieviele $a$'s es schon waren, also auch nicht, ob es eine 2er Potenz ist.
			\item Er kann sich die Differenz zwischen $a$'s und $b$' nicht merken.
		\end{enumerate}
	\item Variante:
		\begin{enumerate}[(a)]
			\item $$L_1 = \{a^{2^n} \; | \; n \in \SetN\}$$
				Sei $N$ die nächst größere 2er Potenz nach der Zahl des Pumping Lemmas für $L_1$. Dann ist $w=a^{2 \cdot N} \in L_1$ (da $2\cdot N = 2^{(1+\log_2 N)}$, $|w| > N$. \\
				Dann gibt es eine Zerlegung $w=xyz$ mit $|y| > 0, |xy| \le N$, sodass für alle $i$ $xy^iz$ auch $\in L_1$. \\
				Nach dem Pumping Lemma muss $w_2 = wy^2z = wyyz \in L_1$ sein.
				$$|w_2| = |wyyz| = |wyz| + |y| \in \{|w|+1,...,|w|+N\}$$
				Das nächst längere Wort nach $w$ in $L_1$ ist aber $a^{4 \cdot N}$ \FLASH
			\item $$L_2 = \{w \in \{a,b\}^* \; | \; \#a(w) = \#b(w)\}$$
				Sei $N$ die Zahl des Pumping Lemmas für $L_2$. Dann ist $w = a^Nb^N \in L_2$ (da $\#a(w) = \#b(w) = N$). $|w| > N$. \\
				Dann gibt es eine Zerlegung $w=xyz$ mit $|y| > 0, |xy| \le N$, sodass für alle $i$ $xy^iz$ auch $\in L_2$. \\
				Da $w=a^Nb^N$, besteht $xy$ nur aus $a$'s. Also $w=a^{|x|}a^{|y|}a^{(N-|x|-|y|)}b^N$. \\
				Dann ist nach dem Pumping Lemma auch $w_i = a^{|x|}[a^{|y|}]^i a^{(N-|y|)}b^N \in L_2$. Aber $|y| > 0$. \FLASH
		\end{enumerate}
\end{enumerate}


\end{document}
