\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{}
\author{}
\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}
	}

\noindent Beispiel:\\
$$u \in \{a,b\}^*$$
\begin{eqnarray*}
	u & = & u_1 ... u_n \\
	u^R & = & u_n ... u_1
\end{eqnarray*}
$$u \$ u^R \$ $$
\begin{center}
\begin{tabular}{c|c|c|c|c|c}
	derz. Zustand & EK & AK & neuer Zustand & EK & AK \\
	0 (Anfangszustand) & a & Z & 1 & $\rightarrow$ & uparrow A \\
	0 & b & Z & 1 & $\rightarrow$ & uparrow B \\
	0 & \$ & Z & 3 & $\rightarrow$ & - \\
	1 & a & A & 1 & $\rightarrow$ & uparrow A \\
	1 & a & B & 1 & $\rightarrow$ & uparrow A \\
	1 & b & A & 1 & $\rightarrow$ & uparrow B \\
	1 & b & B & 1 & $\rightarrow$ & uparrow B \\
	1 & \$ & A & 2 & $\rightarrow$ & A \\
	1 & \$ & B & 2 & $\rightarrow$ & B \\
	2 & a & A & 2 & $\rightarrow$ & downarrow \\
	2 & b & B & 2 & $\rightarrow$ & downarrow \\
	2 & \$ & Z & 3 (Endzustand) & $\rightarrow$ & downarrow
\end{tabular}
\end{center}
3. Turing Maschine \\
TODO: Bild einfügen \\
Anfangskonfiguration: Startzustand, Eingabekopf ganz links \\
Endkonfiguration: Maschine im Endzustand \\[0.3cm]
Regeln: \\
Wenn Zustand $=q$, Eingabekopf liest $a$, Arbeitskopf liest $A$, dann neuen Zustand $q'$, Eingabekopf $\rightarrow, \cdot$, Arbeitskopf $A', \leftarrow, \cdot, \rightarrow$ \\[0.3cm]
Beispiel: $u \in \{a,b\}^*$
$$u \$ u^R \$ u \$ $$
\begin{center}
\begin{tabular}{c|c}
	DEA & det. endlicher Automat \\
	NEA & nichtdet. endlicher Automat \\
	DKA & det. Keller Automat \\
	NKA & nichtdet. Keller Automat \\
	DTM & det. Turing Maschine \\
	NTM & nichtdet. Turing Maschine
\end{tabular}
\end{center}
Def.: \\
Eine Sprache $L$ ist eine DEA Sprache, wenn es einen DEA gibt, der $L$ akzeptiert. \\
NEA-Sprache, ..., NTM-Sprache analog definiert. \\[0.5cm]
Lemma: \\
Jede DEA-Sprache ist eine NEA-Sprache. \\
Jede DKA-Sprache ist eine NKA-Sprache. \\
Jede DTM-Sprache ist eine NTM-Sprache. \\[0.5cm]
Lemma: \\
Jede DEA-Sprache ist eine DKA-Sprache. \\
Jede NEA-Sprache ist eine NKA-Sprache. \\
Jede DKA-Sprache ist eine DTM-Sprache. \\
Jede NKA-Sprache ist eine NTM-Sprache. \\
TODO: Bild einfügen \\
Fragen:
\begin{enumerate}[1.]
	\item Welche Inklusionen sind strikt?
	\item Gegeben ein NKA. Gibt es einen DEA, der genau die gleiche Sprache akzeptiert?
	\item Gegeben zwei Maschinen: akzeptieren sie die gleiche Sprache? \\[0.3cm]
\end{enumerate}
Mengenlehre \\
$$f: \quad A \rightarrow B \quad \text{Funktion}$$
Injektion: $\forall a,b \in A: a \ne b \Rightarrow f(a) \ne f(b)$ \\
Surjektion: $\forall b \in B, \exists a \in A: f(a) =b$ \\
Bijektion: Surjektion und Injektion (eineindeutige Zuordnung) \\[0.3cm]
Def.: \\
$A$ und $B$ heißen gleich mächtig, wenn es eine Bijektion zwischen $A$ und $B$ gibt. \\
Bsp.: \\
$G$ nicht neg. geraden Zahlen $\{0,2,4,6,...\}$ \\
$\SetN$ und $G$ sind gleichmächtig. \\
Bew.: $f(x) = 2x$ ist Bijektion! \\[0.3cm]
Def.: \\
$A$ heißt endlich, wenn $\exists k \in \SetN$ sodass $A$ gleichmächtig wie $\{0,...,k-1\}$.
$$A=\{a_0,a_1,...,a_{k-1}\}$$
$A$ heißt abzählbar, wenn $A$ endlich oder $A$ gleichmächtig wie $\SetN$. \\[0.3cm]
Lemma: \\
$A_1,A_2,...,A_k$ endliche Mengen $k \in \SetN$.
\begin{itemize}
	\item $A_1 \cup A_2 \cup ... \cup A_k$ ist endlich.
	\item $A_1 \times A_2 \times ... \times A_k$ ist endlich.
	\item $A_1^k$ ist endlich.
\end{itemize}
Lemma: \\
$A_0, A_1, ...$ sei unendliche Folge von disjunkten endlichen Mengen. Dann ist
$$\bigcup_{i \in \SetN} A_i$$
abzählbar (unendlich). \\[0.3cm]
Lemma: \\
Wenn $A,B$ abzählbar unendlich $\Rightarrow A \times B$ abzählbar unendlich. \\
Bew.: $\SetN; \SetN$
\begin{center}
\begin{tabular}{cccccc}
	& 0 & 1 & 2 & 3 & 4 \\
	0 & (0,0) & (0,1) & (0,2) & (0,3) & (0,4) \\
	1 & (1,0) & (1,1) & (1,2) & (1,3) & (1,4) \\
	2 & (2,0) & (2,1) & (2,2) & (2,3) & (2,4) \\
	3 & (3,0) & (3,1) & (3,2) & (3,3) & (3,4)
\end{tabular}
\end{center}
\begin{eqnarray*}
	c_i & = & \{(a_j,b_k) | j+k = i\} \\
	A \times B & = & \bigcup_{i \in \SetN} c_i
\end{eqnarray*}
$c_i$ disjunkt, $|c_i| = i+1$ \\[0.3cm]
Lemma: \\
Sei $A$ abzählbar unendlich.
$$2^A = \{B | B \subset A\}$$
$2^A$ ist NICHT abzählbar. \\
Bew.: $A=\{a_0,a_1,...\}$ \\
$B \subset A$ kann mit \glqq unendlicher\grqq\ Bitfolge $s_B$ identifiziert werden.
$$s_b(i) = \left\{ \begin{array}{cc}1 & a_i \in B \\ 0 & a_i \not\in B\end{array}\right.$$
$B=\{1,3,7\}$: $010100010...$ \\
$B=\{1,3,5,7\}$: $010101010101...$ \\
$2^A$ ist nicht abzählbar, d.h. $f: \SetN \rightarrow 2^A \Rightarrow f$ ist keine Bijektion (z.b. weil $f$ keine Surjektion). \\
\begin{eqnarray*}
	f(0) = B_0 & : & s_{B_0} = 0110011... \\
	f(1) = B_1 & : & s_{B_1} = 11100010...1
\end{eqnarray*}
Möchte zeigen: $\exists B \subset A$ sodass $\forall n \in \SetN: f(n) \ne B$ \\
$\Leftrightarrow$ suche Bitfolge, die in Auflistung nicht vorkommt, sich also von jedem $s_{B_i}$ unterscheidet.
$$s_B(i) = 1-s_{B_i}(i)$$
$s_B$ unterscheidet sich von jedem $s_{B_i}$ (an Stelle $i$) \\
$\Rightarrow$ Cantar'sche Diagonalisierungsverfahren.

\end{document}
