\documentclass[12pt]{article}

%\usepackage{ngerman}
\usepackage{a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{stmaryrd}
\usepackage{enumerate}
%\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}
\usepackage{cancel}
\usepackage[usenames]{color}
\usepackage{gastex}

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 2}
\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}
$\{0,1\}^{\N} \subset \N^{\N} \Rightarrow \exists$ Surjektion von $\N^{\N} \to \{0,1\}^{\N}$. \\
Fasse jede Funktion $f: \N \to \{0,1\}$ als unbeschränkten Bitstring $b$ auf. \\
Betrachte Funktion $g(x)$ mit
$$g: x \mapsto \begin{cases}\# \mbox{ Nullen zwischen x-ten und (x+1)-ten Eins} & \mbox{falls } \# \mbox{ Nullen endlich} \\ \# \mbox{ Einsen zwischen x-ten und (x+1)-ten Null} & \mbox{sonst}\end{cases}$$
Für $x=0$ sei $g(x)=g(0)$ zu verestehen als
$$g: 0 \mapsto \begin{cases}\# \mbox{ Nullen vor 1. Eins} & \mbox{falls } \# \mbox{ Nullen endlich} \\ \# \mbox{ Einsen vor 1. Null} & \mbox{sonst}\end{cases}$$
$\Rightarrow \exists$ Surjektion von $\N^{\N} \to \{0,1\}^{\N}$ und $\exists$ Surjektion von $\{0,1\}^{\N} \to \N^{\N}$. \\
$\Rightarrow |\{0,1\}^{\N}| = |\N^{\N}|$. \QED
%\textbf{Behauptung:} $\N^{\N}$ und $\{0,1\}^{\N}$ sind nicht gleichmächtig, d.h. es gibt keine Bijektion $\N^{\N} \to \{0,1\}^{\N}$. \\
%\textbf{Beweis:} \\
%Es genügt zu zeigen, dass es keine Surjektion $\N^{\N} \to \{0,1\}^{\N}$ gibt. \\
%Annahme: Es gäbe doch eine Surjektion $f: \N^{\N} \to \{0,1\}^{\N}$, d.h.
%$$\forall h \in \{0,1\}^{\N}, \; \exists \; g_h \in \N^{\N}: \underbrace{f(g_h)}_{\in \{0,1\}^{\N}} = h \quad (*)$$
%Sei $h = h_f: \N \to \{0,1\}; n \mapsto \begin{cases}1 & \mbox{falls } f(g_{h_f})(n) = 0 \\ 0 & \mbox{falls } f(g_{h_f})(n) = 1\end{cases}$ \\\\
%Dann gilt für beliebiges $m \in \N$:
%\begin{itemize}
%    \item Ist
%        \begin{eqnarray*}
%            f(g_{h_f})(m) = 0 & \Rightarrow & h_f(m) = 1 \\
%            & \Rightarrow & f(g_{h_f})(m) \neq h_f(m) \\
%            & \Rightarrow & f(g_{h_f}) \neq h_f
%        \end{eqnarray*}
%    \item Andernfalls ist 
%        \begin{eqnarray*}
%            f(g_{h_f})(m) = 1 & \Rightarrow & h_f(m) = 0 \\
%            & \Rightarrow & f(g_{h_f})(m) \neq h_f(m) \\
%            & \Rightarrow & f(g_{h_f}) \neq h_f
%        \end{eqnarray*}
%\end{itemize}
%Beides steht im Widerspruch zur Annahme $(*)$ $\Rightarrow$ Die Annahme ist falsch. \\\\
%$\Rightarrow$ Es gibt keine Surjektion $\N^{\N} \to \{0,1\}^{\N}$ und somit auch keine \\
%Bijektion $\N^{\N} \to \{0,1\}^{\N}$, d.h. $\N^{\N}$ und $\{0,1\}^{\N}$ sind nicht gleichmächtig. \QED

\section*{Aufgabe 2}
\subsubsection*{(a)}
\begin{center}
\begin{picture}(92,102)(0,-102)
\put(0,-102){{}}
\node[Nmarks=r,Nmr=0.0](n15)(44.0,-28.0){}
\node(n16)(64.0,-28.0){}
\node(n17)(84.0,-28.0){}
\node(n18)(84.0,-48.0){}
\node(n19)(64.0,-48.0){}
\node(n20)(64.0,-68.0){}
\node(n21)(84.0,-68.0){}
\node(n22)(84.0,-88.0){}
\node(n23)(64.0,-88.0){}
\node(n24)(44.0,-88.0){}
\node(n25)(44.0,-68.0){}
\node(n26)(44.0,-48.0){}
\drawedge(n15,n16){b}
\drawedge(n16,n17){b}
\drawedge(n17,n18){a}
\drawedge(n18,n21){a}
\drawedge(n21,n22){a}
\drawedge(n24,n23){b}
\drawedge(n23,n22){b}
\drawedge(n25,n20){b}
\drawedge(n20,n21){b}
\drawedge(n26,n19){b}
\drawedge(n19,n18){b}
\drawedge(n15,n26){a}
\drawedge(n26,n25){a}
\drawedge(n25,n24){a}
\drawedge(n16,n19){a}
\drawedge(n19,n20){a}
\drawedge(n20,n23){a}
\drawedge[curvedepth=8.0](n23,n16){a}
\drawedge[curvedepth=8.0](n22,n17){a}
\drawedge[curvedepth=8.0](n24,n15){a}
\drawedge[curvedepth=5.84](n17,n15){b}
\drawedge[curvedepth=6.22](n18,n26){b}
\drawedge[curvedepth=5.97](n21,n25){b}
\drawedge[curvedepth=5.84](n22,n24){b}
\end{picture}
\end{center}

\subsubsection*{(b)}
\begin{center}
\begin{picture}(136,111)(0,-111)
\put(0,-111){{}}
\node[NLangle=0.0,Nmr=0.0](n27)(76.0,-28.0){S}
\node[NLangle=0.0,Nmarks=r](n28)(56.0,-48.0){0}
\node[NLangle=0.0](n29)(92.0,-48.0){1}
\node[NLangle=0.0](n30)(56.0,-68.0){3}
\node[NLangle=0.0](n31)(56.0,-88.0){6}
\node[NLangle=0.0](n32)(92.0,-88.0){5}
\node[NLangle=0.0](n33)(92.0,-68.0){2}
\node[NLangle=0.0](n34)(128.0,-68.0){4}
\drawedge[curvedepth=2.29](n33,n34){0}
\drawedge[curvedepth=2.29](n34,n33){1}
\drawedge(n27,n28){0}
\drawedge(n27,n29){1}
\drawedge(n29,n33){0}
\drawedge(n33,n32){1}
\drawedge(n32,n34){1}
\drawedge(n34,n29){0}
\drawedge(n29,n30){1}
\drawedge(n30,n31){0}
\drawedge(n31,n32){0}
\drawedge(n30,n28){1}
\drawedge(n28,n29){1}
\drawloop[loopangle=135.0](n28){0}
\drawloop[loopangle=225.52](n31){1}
\drawedge(n32,n30){0}
\end{picture}
\end{center}

\subsubsection*{(c)}
Sei $S$ die Menge der Quadratzahlen. Sei $S' \subset S$ mit der Form $1^n0^n01, n \in \N$, also
$$S'=\{w | w = 2^{2a} - 2^{2a+1} + 1\} \quad \forall a \in \N$$
(Es gilt $2^{2a} - 2^{a+1} + 1 = (2^a-1)^2 \in S \quad \forall a \in \N$). \\\\
Ist $a=1, b=0$ so hat man also mit $v \in S'$ Worte der Form $v=a^nb^n01$. Für Worte dieser Form
gibt es jedoch keine DEA-Sprache, da in der Vorlesung gezeigt wurde, dass $L=\{a^nb^n | n \in \N\}$
keine DEA-Sprache ist. \\
Die einzige Möglichkeit, Worte der Form $1^n0^n01$ zu akzeptieren wäre, die "0"-en in einer Schleife
zu überlesen, sie also zu ignorieren. Solche Worte wären dann aber auch z.B. $1^m1^n01$ mit $m,n \in \N$ und $m \ne n$.
Sie sind aber in der Regel keine Quadratzahlen: \\
$\exists v \in \{1^m1^n01\}$ mit $v \notin S$, z.B. $m=4, n=3$:
$$\left<111100001\right> = 2^9 - 2^5 + 1 = 512 - 32 + 1 = 481 \notin S$$
Somit hat $1^n$ für jedes $n$ eine Fortsetzungssprache, die sich von denen der Worte $1^{n'}$ mit $n' \ne n$ unterscheidet.
Da aber $n \in \N$, somit $\{w | w = 1^n0^n01, n \in \N\}$ unendlich (mindestens eine pro Wort der Teilmenge $S'$), somit ist
$\mathcal{F}$ endlich. \\
$\Rightarrow \not\exists$ DEA. \QED

\subsubsection*{(d)}
Man kann hier keinen DEA konstruieren. Denn: \\
Seien $a,b \in \N$, $a$ prim, $b<a$. Dann lässt sich sicher sagen, dass $ggT(a,b)=1$. Außerdem ist $2^n$ teilerfremd $a$, $\forall a>2, n \in \N$. \\
Aus diesen Eigenschaften folgt $ggT(a,b \cdot 2^{|a|})=1$, was eine Primfaktorzerlegung einfach zeigt. $|a|$ sei hierbei die Länge des Binärwortes $a$. \\
Nach dem Satz von Dirichlet ist jetzt aber
$$\exists x \quad c := a + x \cdot (b \cdot 2^{|a|})$$
prim, wobei das $x\in \N$ eine bestimmte Zahl ist, für die das gilt. \\
Wenn man das rückwärts gelesene Wort betrachtet, hat jedes $a \in \{p | p \mbox{ ist prim}\}$ mindestens eine Fortsetzungssprache, die von seiner jeweiligen Länge als Binärwert abhängt. \\
Da es aber unendlich viele Primzahlen und damit auch beliebig lange Bitstring-Darstellungen solcher Zahlen gibt, muss die Menge aller Fortsetzungssprachen $\mathcal{F}$ unendlich sein. \\
$\Rightarrow \not\exists$ DEA, der das akzeptiert.

\newpage
\section*{Aufgabe 3}
\begin{itemize}
    \item $\overline{L}$: \\
        Sei $M$ der Automat, der $L$ akzeptiert. Es existiert ein Automat $M'=(\Sigma, Q', s', F', \Delta')$, der $\overline{L}$ akzeptiert. $M'$ sieht wie $M$ aus mit folgenden Unterschieden:
        \begin{itemize}
            \item alle Endzustände von $M$ sind in $M'$ keine Endzustände und alle nicht-Endzustände von $M$ sind in $M'$ Endzustände.
            \item $M'$ besitzt noch einen weiteren Endzustand, in den der Automat $M'$ für ein eingelesenes Zeichen übergeht, d.h.
                $$\Delta'=\{(q,a,\beta) | (q,a,q') \notin \Delta \mbox{ für } q,q' \in Q, a \in \Sigma\}$$
        \end{itemize}
    \item $L \cap L'$: \\
        $L \cap L' \Rightarrow$ Es existieren Automaten $M$, der $L$ akzeptiert, und $M'$, der $L'$ akzeptiert. Nach dem Satz von Myhill-Nerode gilt: \\
        $L \subset \Sigma^*$ DEA-Sprache $\Leftrightarrow \mathcal{F}$ endlich. \\
        $\Rightarrow \mathcal{F}_L \cap \mathcal{F}_{L'}$ endlich \\
        $\Rightarrow L \cap L'$ DEA-Sprache.
    \item $L \cup L'$: \\
        analog zu $L \cap L'$: $\mathcal{F}_L \cap \mathcal{F}_{L'}$ endlich $\Rightarrow L \cup L'$ DEA-Sprache.
\end{itemize}

\end{document}