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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 02. 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}}



\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{Regul\"are Ausdr\"ucke I}{10 Punkte}
  \begin{enumerate}
    \item Geben Sie regul\"are Ausdr\"ucke f\"ur die folgenden Sprachen an.
        Erkl\"aren Sie Ihren Ausdruck in einem Satz, und geben Sie das zu Grunde
	liegende Alphabet an. Erkl\"aren Sie ggf.~auch alle Annahmen, die Sie
	gemacht haben.
      \begin{enumerate}
        \item Summen von positiven dezimalen Festkommazahlen. 
         In der Sprache sollen also z.B.~die Zeichenketten $3.14$ oder auch 
         $3+4.2+7+1$ vorkommen. 
        \item KFZ-Nummernschilder, bestehend aus ein bis drei Gro\ss{}buchstaben 
           gefolgt von einem Bindestrich, dann ein bis 
	   zwei Gro\ss{}buchstaben und zum Schluss ein bis vier Ziffern. 
            Die L\"ange der Nummernschilder insgesamt betr\"agt nicht mehr als 
            acht Zeichen.
	\item Die Menge aller Bin\"arzahlen, die durch vier teilbar sind.
	  Dabei sind keine \"uberfl\"ussigen f\"uhrenden Nullen erlaubt.
      \end{enumerate}
    \item
       Beschreiben Sie in deutscher Sprache die durch die folgenden regul\"aren
       Ausdr\"ucke charakterisierten Mengen. 
       Ihre Beschreibungen sollen die Form haben:
       \begin{center}
          \emph{Die Menge aller W\"orter \"uber dem 
	  Alphabet $\{0,1\}$ \dots .``}  %''
        \end{center}
        Dabei soll \dots durch maximal acht W\"orter ersetzt werden. 
 
        \begin{enumerate}
           \item $(0^* 1 0^* 1 0^*)^*$; und
           \item $(00 \cup 11 \cup (01 \cup 10) (00 \cup 11)^* (01 \cup 10))^*$.
        \end{enumerate}
  \end{enumerate}

\AUFGABE{Regul\"are Ausdr\"ucke II}{10 Punkte}

  Zwei regul\"are Ausdr\"ucke $\alpha, \beta$ hei\ss{}en \emph{\"aquivalent},
  geschrieben $\alpha \sim \beta$, genau dann, wenn sie die gleiche
  Sprache repr\"asentieren, also $L(\alpha)=L(\beta)$ ist.
  Zeigen Sie:
  \begin{enumerate}
    \item $(\alpha \cup \beta)\gamma \sim \alpha\gamma \cup \beta\gamma$;
    \item $(\alpha^*)^* \sim \alpha^*$; 
    \item $(\alpha \cup \beta)^* \sim (\alpha^*\beta^*)^*$;
    \item $\alpha\emptyset \sim \emptyset$; und
    \item $\alpha\emptyset^* \sim \alpha$.
  \end{enumerate}
\newpage

\AUFGABE{Regul\"are Sprachen}{10 Punkte}

Eine Sprache hei\ss{}t \emph{regul\"ar}, falls sie sich durch einen
regul\"aren Ausdruck darstellen l\"asst.

\begin{enumerate}
\item Zeigen Sie: Jede endliche Sprache ist regul\"ar.
\item
Sei $\Sigma$ ein Alphabet und $w = \sigma_1\sigma_2\dots\sigma_n$ ein Wort \"uber
$\Sigma$. Die \emph{Umkehrung} von $w$, $w^R$, ist definiert als 
$w^R = \sigma_{n}\sigma_{n-1}\dots\sigma_1$.
So ist zum Beispiel $\text{haus}^{R}=\text{suah}$, 
$\text{blatt}^{R}=\text{ttalb}$, 
$\text{a}^{R}=\text{a}$ und
$\varepsilon^{R}=\varepsilon$. 
Die Umkehrung einer Sprache $L \subseteq \Sigma^*$ 
ist definiert als
$L^R = \{w^R \mid w \in L\}$.

Zeigen Sie: Ist $L$ eine regul\"are Sprache, so ist auch
$L^R$ regul\"ar. Geben Sie dazu einen detaillierten Beweis,
der strukturelle Induktion \"uber den regul\"aren Ausdruck
f\"ur $L$ verwendet.
\end{enumerate}
\end{description}
\end{document}
