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

\newcommand{\ABGABEDATUM}{keine Abgabe}

\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]
Sonderaufgabenblatt 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{Pumping-Lemma}{}

\begin{enumerate} 
\item
Zeigen Sie mit dem Pumping-Lemma, dass die folgenden Sprachen nicht
regul\"ar sind.
\begin{enumerate}
\item $\Sigma= \{0,1\}$ und $L = \{0^n1^m0^{n+m} \mid n,m \in \N\}$.
\item $\Sigma = \{\text{(}, \text{)}\}$ und $L$ die Menge aller g\"ultigen
  Klammerausdr\"ucke.
\item $\Sigma = \{0,1,\#\}$ und $L = \{w\#w \mid w \in \{0,1\}^*\}$.
\item $\Sigma = \{0,1\}$ und $L$ die Menge aller W\"orter, in denen sich
  die Anzahl der Nullen und die Anzahl der Einsen um h\"ochstens 12 unterscheiden.
\item $\Sigma = \{0,1,+,=\}$ und 
  \begin{multline*}
    L = \{\text{$w_1$+$w_2$=$w_3$} \mid
      w_1,w_2, w_3 \in \{0,1\}^+,\\
  \text{$w_1+w_2 = w_3$ ist eine g\"ultige Formel in Bin\"ararithmetik.}\}.
  \end{multline*}
\item $\Sigma = \{0, 1\}$ und
  $L = \{w\overline{w} \mid w \in \Sigma^*\}$, wobei
    $\overline{w}$ aus $w$ hervor geht, indem man
    jede $0$ durch eine $1$ und jede $1$ durch eine $0$ ersetzt.
\item $\Sigma = \{0,1\}$ und $L = \{ w1^{|w|} \mid w \in \Sigma^*\}$.
\item $\Sigma = \{0,1\}$ und $L = \{ 0^i1^j \mid i,j \in \N, i > j \geq 1\}$.
\end{enumerate}
\item Sei $\Sigma = \{0,1\}$ und sei $L = 
L((\text{000} \cup \text{111})(\text{000} \cup \text{111})^*)$.
Definiere 
\[
L_{\frac{1}{3}-\frac{1}{3}} := \{ uw \mid \exists v \in \Sigma^* \text{ so dass }
uvw \in L \text{ und } |u|=|v|=|w|\}.
\]
Dann ist $L_{\frac{1}{3}-\frac{1}{3}}$ nicht regul\"ar.
\item Sei $\Sigma = \{a,b,c\}$ und $L = \{a^ib^jc^k \mid i,j,k \geq 0 \text{ und }
j = k \text{ falls } i = 1\}$. Zeigen Sie, dass $L$ die Folgerung des
Pumping-Lemmas erf\"ullt. Verwenden Sie dann die Nerode-Relation, um zu zeigen,
dass $L$ nicht regul\"ar ist.
\end{enumerate}

\end{description}
\end{document}
