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

\setcounter{page}{1}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 1.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 30. April 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{0}

\item (0 Punkte)
Sei $\Sigma$ ein Alphabet mit $k$ Elementen und $n \in \mathbb{N}$.
\begin{enumerate}
\item[(a)] Wieviele Worte in $\Sigma^*$ haben die L\"ange $n$? 
\item[(b)]Wieviele Palindrome in $\Sigma^*$ haben die L\"ange $n$?
(Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen
gleich ist.) 
\item[(c)]Wieviele Worte  $w \in \{ 0,1 \}^*$, die
Bin"ardarstellung einer durch
5 teilbaren Zahl sind (f"uhrende Nullen sind erlaubt),
haben die L\"ange $n$? 
\item[(d)]Wie ist es, wenn führende Nullen verboten sind?
\end{enumerate}
Jede Behauptung ist zu beweisen! 

\item (0 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 (6 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)] (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 (6 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 (4 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 (Zusatzfrage, 2 Punkte)
Geben sie einen regulären Ausdruck an, der alle Wörter über $\Sigma=\{0,1\}$
beschreibt, die $0110$ nicht als Teilwort enthalten.

\end{enumerate}
\end{document}

