% 1. Uebungsblatt GTI SS 2005
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,1cm
\textheight=25cm
%\textheight=26cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{3}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005 ---
 1.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 25. April 2005, 10:15 Uhr
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{4}

\item (10 Punkte)
% \item[(a)] 
Beschreiben Sie die Sprache $L$, die durch den regul\"aren Ausdruck 
$$0^*(0+10^*1)^*( \varepsilon +0 +00)$$
gegeben ist. (Alle Worte in $L$ haben eine sehr charakteristische 
Eigenschaft. Welche?) Beweisen Sie Ihre Behauptung!
Gibt es einen einfacheren regulären Ausdruck für diese Sprache?
\item (0 Punkte)
\begin{enumerate}
\item[(a)] % (0 Punkte) 
Geben Sie einen regul\"aren Ausdruck an,
der genau die Worte $w$ \"uber 
$\Sigma$ % = \{0,1\}$
mit der folgenden Eigenschaft beschreibt: "`$w$ enth\"alt keine 
zwei unmittelbar aufeinanderfolgenden gleichen Symbole,"'
und zwar für
$\Sigma_2 = \{a,b\}$,
$\Sigma_3 = \{a,b,c\}$, und für
$\Sigma_4 = \{a,b,c,d\}$.
Beweisen Sie, dass Ihr  
Ausdruck wirklich diese Sprache beschreibt!
\item[(b)]% (6 Punkte)
Lösen Sie dieselbe Aufgabe
für die folgende Eigenschaft: "`Jedes Symbol in $w$ steht neben
einem gleichen Symbol."'
(Zum Beispiel hat das Wort $aaabbcccaa$ diese Eigenschaft.)
\item[(c)] (schwierig) %(Zusatzaufgabe) %, 2 Punkte)
Wieviele Wörter der Länge $n$ enthält die Sprache aus Aufgabe~(b),
für $\Sigma_2$
und $\Sigma_3$?
\end{enumerate}

\item (0 Punkte)
\begin{enumerate}
\item[(a)] Codieren Sie das Alphabet $\{a, b, \ldots, z\}$ durch Bin\"arworte, so dass 
jedes codierte Wort wieder eindeutig decodierbar ist! (Eine ungeeignete Codierung 
w\"are z.B.~ $a \mapsto 0, b \mapsto 01, c \mapsto 100$, etc. In diesem Fall k\"onnte 
n\"amlich 0100 von $ac$ oder von $baa$ herstammen.) Zeigen Sie, dass Ihre 
Codierung die gew\"unschte Eigenschaft hat.
\item[(b)]Das Alphabet $\Sigma = \{a,b\}$ sei durch $a \mapsto 0$ und $b \mapsto 010$ 
codiert. 
Zeigen Sie, dass diese Codierung eindeutig decodierbar ist! 
\end{enumerate}


\item (Zusatzfrage, 10 Punkte) 
Welche der folgenden Gleichungen gelten für alle regulären
Ausdrücke?
\begin{enumerate}
\item $(AB)C=A(BC)$
\item $(A^*)^*=A^*$
\item $(A+B)^*=A^* + B^*$
\item $(A^*B^*)^* = (A+B)^*$
\end{enumerate}
Beweisen Sie Ihre Antworten.%\\ % Zusatzfrage (2 Punkte): 
Wenn eine Beziehung nicht als Gleichung
gilt, in welchen Fällen gilt dann eine Inklusionsbeziehung ($\subseteq$ oder
$\supseteq$)?

\item (0 Punkte) % (Zusatzfrage, 2 Punkte)
Geben sie einen regulären Ausdruck an, der alle Wörter über $\Sigma=\{0,1\}$
beschreibt, die $0101$ nicht als Teilwort enthalten.

\item (0 Punkte)
Konstruieren Sie einen regulären Ausdruck für die Sprache $L_1$
% $L_1$ ist die Sprache 
der Wörter über $\{0,1\}$, bei
denen auf jedes Vorkommen der Teilfolge 0011 unmittelbar
die Teilfolge 1100 anschließt.

Zum Beispiel ist $w_1=0001111100 \notin L_1$, 
$w_2= 01011001111001111000 \in L_1$,
$w_3= 0010 \in L_1$,
und
$w_4= 00111100011 \notin L_1$.
Erklären Sie Ihren Ausdruck. (Ein formaler
Korrektheitsbeweis ist nicht erforderlich.)

\end{enumerate}
\end{document}

