\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{cancel}
\usepackage{eurosym}

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 4}
\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}
Nach längerer Überlegung findet man folgenden regulären Ausdruck:
$$r = ((a+b)^* (ba(aa)^* + ab(bb)^*)) + (a(aa)^*) + (b(bb)^*)$$
Die Überlegungen basieren darauf, dass der Automat nur Worte akzeptiert, die nur auf eine ungerade Anzahl gleicher Zeichen endet. Nimmt man an, das Wort besteht nur aus $a$'s. Dann greift $(a(aa)^*)$ aus dem regulären Ausdruck (vom Startzustand ausgehend kommt man nur nach 1). Nimmt man an, das Wort besteht nur aus $b$'s, dann greift $(b(bb)^*)$ (vom Startzustand ausgehend kommt man nur nach 2).

\section*{Aufgabe 2}
\subsubsection*{(a)}
$L_0 = \{a^{n^2} | n \in \SetN\}$. \\\\
\glqq Spiel\grqq :
\begin{enumerate}
	\item Der Gegner wählt $N \in \SetN$.
	\item Ich wähle $x \in L_0$ mit $|x| \ge \SetN$:
		$$x = a^{N^2}$$
	\item Der Gegner gibt die Unterteilung vor:
		$$\underbrace{aa \ldots}_{u = a^\alpha} \underbrace{|a \ldots}_{v = a^\beta} \underbrace{| \ldots aa}_{w} \quad \beta \ge 1, \alpha + \beta \le N$$
	\item Ich wähle $i=0$:
		\begin{align*}
			uv^0w &= a^\alpha \cdot a^{N - \alpha - \beta} \cdot a^{N^2 - N} \\
			&= a^{N - \beta} a^{N^2-N} \\
			&= a^{N^2-\beta} \notin L
		\end{align*}
		da $a^{(N-1)^2}5 = a^{N^2-2N+1}$, $2N-1 > \beta > 0$, da $\beta \ge 1$ und $\beta \le N-\alpha$. \\
		$\Rightarrow |a^{(N-1)^2}| < |a^{N^2-\beta}| < |a^{N^2}|$.
\end{enumerate}

\subsubsection*{(b)}
$L_1 = \{a^n | n \mbox{ ist eine Primzahl}\}$. \\\\
\glqq Spiel\grqq :
\begin{enumerate}
	\item Der Gegner wählt $N \in \SetN$.
	\item Ich wähle $x \in L_1$ mit $|x| \ge N$:
		$$x=a^p$$
		mit $p$ als die kleinste Primzahl $> N + 2$.
	\item Der Gegner gibt die Unterteilung vor:
		$$\underbrace{aa \ldots}_{u = a^\alpha} \underbrace{| \ldots a \ldots}_{v = a^\beta} \underbrace{| \ldots a}_{w = a^\gamma} \quad \beta \ge 1, \alpha + \beta < N$$
	\item Ich wähle $i=\alpha+\gamma$:
		\begin{align*}
			uv^{\alpha+\gamma}w &= a^\alpha \cdot a^{\beta \cdot (\alpha+\gamma)} \cdot a^\gamma \\
			&= a^{\alpha + \beta(\alpha+\gamma) + \gamma} \\
			&= a^{(\alpha+\gamma) \cdot (\beta+1)}
		\end{align*}
		$(\alpha+\gamma) \cdot (\beta+1)$, $\alpha, \beta, \gamma \in \SetN$ ist aber nicht prim. \\
		Somit ist $a^{(\alpha+\gamma)(\beta+1)} \notin L_1$, die Sprache ist also nicht regulär.
\end{enumerate}

\section*{Aufgabe 3}
Folgender Automat $M$ akzeptiert $Bexp$:
\begin{align*}
	M &= (\Sigma, \Gamma, \mbox{\euro}, Q, s, F, \Delta) \\
	\Sigma &= \{0,1, (, ), +, -, *\} \\
	\Gamma &= \{\mbox{\euro}, A\} \\
	Q &= \{S,Z,O,E\} \\
	s &= S \\
	F &= \{E\}
\end{align*}
$\Delta$ wie folgt (in der Zeichnung wird anstatt \euro\ das Zeichen \$ benutzt und für $\varepsilon$ das Zeichen e):
\bild{12}{a3}{Aufgabe 3}{a3}

\section*{Aufgabe 4}
Man nehme die Sprache $L$ mit
$$L=\{ab(ab)^na^m | n \in \SetN, m \in \SetN \mbox{ ist prim}\}$$
Man wähle ein $n \in \SetN$ sowie $m \in \SetN$ prim und unterteile wie folgt:
$$\underbrace{ab}_{u} \underbrace{|ab|}_{v} \underbrace{(ab)^{n-1}a^m}_{w}$$
und kann beliebiges $i$ wählen, womit immer noch
$$ab(ab)^{n-1+i}a^m \in L$$
$L$ ist aber nicht regulär, da bereits $a^m$, $m \in \SetN$ prim, unregulär ist (vergleiche Aufgabe 2) und eine Konkatenation einer unregulären mit einer regulären Sprache nicht regulär sein kann. \\
Der Form halber sei erwähnt, dass auch das Kriterium der Wortlänge erfüllt ist, so ist $|ab(ab)^na^m|>n,n>0$, daher kann man dieses Wort durchaus allgemein betrachten (feste $n$ stellen nur Spezialisierungen dar).

\end{document}