\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 5}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
				Dirk Heine - Matrikelnummer 2030941 \\
		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)}
Bearbeitet von {\bfseries Dirk Heine}
$$L_a = \{w \in \{a,b\}^* \; | \; \#_a(w) \ge 2 \cdot \#_b(w)\}$$
Die Sprache ist eine NKA-Sprache.
\begin{eqnarray*}
	\Sigma & = & \{a,b\} \\
	\Gamma & = & \{A,B,\$\} \\
	Q & = & \{q_1,..., q_8\} \\
	s & = & q_0 \\
	F & = &\{q_7\} \\
	\Delta & = & \{ (q_0, a, \$, A\$,q_1), \\
	& & (q_0, b, \$, B\$, q_3), \\
	& & (q_0, \varepsilon, A, \varepsilon, q_6), \\
	& & (q_0, \varepsilon, B, B, q_4), \\
	& & (q_0, \varepsilon, \$, \$, q_7), \\
	& & (q_1, a, A, AA, q_2), \\
	& & (q_1, b, A, B, q_4), \\
	& & (q_2, a, A, AA, q_2), \\
	& & (q_2, b, A, \varepsilon, q_5), \\
	& & (q_2, \varepsilon, A, \varepsilon, q_6), \\
	& & (q_3, \varepsilon, B, BB, q_4), \\
	& & (q_4, a, B, \varepsilon, q_0), \\
	& & (q_4, b, B, BB, q_3), \\
	& & (q_5, \varepsilon, A, \varepsilon, q_2), \\
	& & (q_6, \varepsilon, A, \varepsilon, q_6), \\
	& & (q_6, \varepsilon, B, \varepsilon, q_8), \\
	& & (q_6, \varepsilon, \$, \$, q_7)\}
\end{eqnarray*}

\subsubsection*{(b)}
Bearbeitet von {\bfseries Jan Hendrik Dithmar}
$$L_b = \{w \in \{a,b\}^* \; | \; \#_a(w) \mod 5 \le \#_b(w) \mod 5\}$$
Die Sprache ist regulär.
\newpage
Automat zu Aufgabe 1 (b):
%\bild{16}{a1b.png}{Graph zu Aufgabe 1 (b)}{a1b}
\newpage
\subsubsection*{(c)}
Bearbeitet von {\bfseries Jan Hendrik Dithmar}
$$L_c = \{w \in \{a,b\}^* \; | \; \#_a(w) \mod \#_b(w) = 0\}$$
Diese Sprache ist nicht-NKA. \\
Beweis durch das Pumping-Lemma: \\
Wähle $z = a^{2N}b^N \in L$, wobei $N \in \SetN$ die Konstante nach dem Pumping-Lemma ist, $|vwx| \le N, |vx| \ge 1$.
Es soll gelten:
$$\exists i \in \SetN: uv^iwx^iy \not \in L$$
Wähle $i=2$: \\[0.3cm]
1. Fall: \\
$vwx$ enthält keine $a$'s $\Rightarrow uv^iwx^iy = uv^2wx^2y \not \in L$ \\[0.3cm]
2. Fall: \\
$vwx$ enthält keine $b$'s $\Rightarrow uv^iwx^iy = uv^2wx^2y \not \in L$ \\[0.3cm]
In beiden Fällen hat man entweder eine \glqq ungerade\grqq\ Anzahl an $a$'s oder an $b$'s, sodass $\#_a(w) \mod \#_b(w) \ne 0$.

\newpage
\section*{Aufgabe 5}
\subsubsection*{(a)}
Bearbeitet von {\bfseries Jan Hendrik Dithmar} \\[0.5cm]
\begin{tabular}{rl}
	$\Sigma$ & Eingabealphabet \\
	$\tilde{Q} = Q \cup Q' \cup \{\tilde{s}\}$ & Zustandsmenge \\
	$\tilde{s}$ & Startzustand \\
	$\tilde{F} = F \cup F'$ & Endzustände \\
	$\Delta \cup \Delta' \cup \{(\tilde{s}, \varepsilon, s), (\tilde{s},\varepsilon,s')\}$ & Regeln
\end{tabular} \\
mit
$$M=(\Sigma, Q, s, F, \Delta)$$
und
$$M'=(\Sigma, Q', s', F', \Delta')$$
wobei
$$\Delta \subset Q \times \Sigma \times Q$$
und
$$\Delta' \subset Q' \times \Sigma \times Q'$$
Lasse $M$ und $M'$ parallel laufen. Verweilt der Lesekopf auf der gleichen Bandzelle, so liegt ein $\varepsilon$-Übergang vor. \\
Anmerkung: Ein 2-Kopf-Automat ist nichts anderes als zwei Automaten, die parallel laufen und mit Hilfe eines $\varepsilon$-Überganges von einem zentralen Startzustand $\tilde{s}$ zu den Startzuständen $s$ und $s'$ der jeweiligen Maschinen $M$ und $M'$ \glqq gestartet\grqq\ werden.

\subsubsection*{(b)}
Bearbeitet von {\bfseries Dirk Heine} \\
$$\{w \in \{a,b\}^* \; | \; q_k \in \delta_{\tilde{s}}(w) \AND q_k \in \tilde{F}, \; k \in \SetN\}$$
Die Maschine akzeptiert alle Worte, die entweder von $M$ oder $M'$ akzeptiert werden.

\subsubsection*{(c)}
Bearbeitet von {\bfseries Jan Hendrik Dithmar} \\
Die Sprachklasse der 2-Kopf-Automaten entspricht der Klasse der regulären Sprachen.
$$L = L_1 \cup L_2 \Rightarrow L \text{ regulär falls } L_1 \text{ und } L_2 \text{ regulär}$$
(laut Vorlesung \glqq Abschlusseigenschaften der regulären Sprachen\grqq )

\end{document}
