\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{ngerman}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 16. Mai 2014 bis 10 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}


\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Grundlagen der theoretischen Informatik}\hfill SoSe 2014 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE{Endliche Automaten}{10 Punkte}

\begin{enumerate}
\item Welche Sprache erkennt der folgende Automat?
 Begr\"unden Sie Ihre Antwort. 
%[width=0.55\textwidth]
\begin{center}
\includegraphics[scale=0.9]{u04automat1}
\end{center}

\item
Sei $\Sigma = \{a,b\}$. Konstruieren Sie einen endlichen Automaten f\"ur die Sprache,
die durch den regul\"aren Ausdruck
\[
 (a \cup ba)(a \cup ba)^*(b \cup ab)^* 
\]
erzeugt wird. 

\end{enumerate}
\AUFGABE{Algorithmus von Kleene}{10 Punkte}

\begin{enumerate}
\item
Konstruieren Sie mit dem Algorithmus von Kleene einen regul\"aren Ausdruck
 zu folgendem endlichen Automaten. 
 \begin{center}
 \includegraphics[scale=0.7]{u04automat2}
 \end{center}
 Dabei d\"urfen Sie Zwischenausdr\"ucke f\"ur $R_{ij}^{k}$ vereinfachen.  
 Beschreiben Sie die akzeptierte Sprache in einem Satz. 
\item 
Der Algorithmus von Kleene zur Umwandlung eines endlichen Automaten in
einen regul\"aren Ausdruck kann auch auf NEAs angewendet werden.
\"Uberlegen Sie, an welchen Stellen man den Algorithmus modifizieren
muss, so dass er f\"ur NEAs statt f\"ur DEAs funktioniert.
\end{enumerate}



\AUFGABE{Schnitt von regul\"aren Sprachen}{10 Punkte}
 
Aus der Vorlesung wissen Sie: Wenn $L_1$ und $L_2$ regul\"are
Sprachen sind, so ist auch $L_1 \cap L_2$ regul\"ar.
Hier wollen wir diese Tatsache mit Hilfe einer
direkten Konstruktion beweisen. 

Seien  $M^1 = (\Sigma, Q^1, q_0^1, F^1, \delta^1)$ und
$M^2 = (\Sigma, Q^2, q_0^2, F^2, \delta^2)$ deterministische
endliche Automaten mit $L(M^1) = L_1$ und $L(M^2) = L_2$.
Geben Sie einen DEA mit Zustandsmenge
$Q_1 \times Q_2$ an, der die Sprache $L_1 \cap L_2$ erkennt.
Beweisen Sie die Korrektheit Ihres Automaten.

\emph{Hinweis}: Der neue Automat simuliert die Automaten
$M^1$ und $M^2$ gleichzeitig.

\AUFGABE{Halbe Sprache}{freiwillig, 10 Zusatzpunkte}

Sei $L \subseteq \{0,1\}^*$. Wir definieren $L_{\frac{1}{2}^-}$ als die
Sprache, die aus den ersten H\"alften der W\"orter aus $L$ besteht, d.h.,
\[
L_{\frac{1}{2}^-} :=  \{x \mid \exists y, \text{so dass } |x| = |y| \text{ und }
  xy \in L\}.
\]
Zeigen Sie: Wenn $L$ regul\"ar ist, so ist auch
$L_{\frac{1}{2}^-}$ regul\"ar.
\end{description}
\end{document}
