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

\setcounter{page}{5}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 5.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Dienstag, 5. Juni 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{25}

\item (4 Punkte)
Welche der folgenden Sprachen  über $\Sigma=\{0,1\}$ sind regulär? beweisen Sie Ihre Antworten.
\xdef\regul{\arabic{enumi}}  
\begin{enumerate}
\item Die Sprache $L_1=\{\, x\mid x=x^R\,\}$ der Palindrome
\item $L_2 = \{\, 0^{i^2}\mid i\ge 1\,\}$
\item $L_3 = \{\, x \mid \text{$x$ enthält mindestens
so viele Nullen wie Einsen}\,\}$
\item $L_4 = \{\, x \mid \text{jeder}$ Präfix von
$x$ enthält mindestens
so viele Nullen wie Einsen$\,\}$
\item (2 Punkte) 
$L_5 = \{\, x \mid \text{die}$  
Anzahl der Nullen von $x$ unterscheidet sich um
 höchstens um 1 von der
Anzahl der Einsen$\,\}$
\item (2 Punkte)
 $L_6 = \{\, x \mid \text{in}$ jedem Präfix von
$x$ unterscheidet sich die Anzahl der Nullen höchstens um 1 von der
Anzahl der Einsen$\,\}$
\end{enumerate}
Ein \emph{Präfix} ist dabei ein Anfangsstück eines Wortes:
$x$ ist Präfix von $y$, wenn $y=xu$ für ein $u\in \Sigma^*$ ist.

\item (0 Punkte)
Es seien $\Sigma$ und $\Delta$ zwei Alphabete.
Ein \emph{Homomorphismus} $h\colon \Sigma^*\to \Delta^*$ ist durch
eine beliebige Funktion $h\colon \Sigma\to \Delta^*$ gegeben, die
folgendermaßen auf $\Sigma^*$ erweitert wird:
$$h(x_1x_2\ldots x_n) :=
h(x_1)h(x_2)\ldots h(x_n)\hbox{, für $n\ge0, \;x_1,\ldots,x_n\in \Sigma$}
$$
Ein Homomorphismus ist durch folgende Eigenschaften charakterisiert:
$$h(\eps) = \eps, \text{ und }
h(x\cdot y) = h(x)\cdot h(y) \hbox{, für alle $x,y\in \Sigma^*$}$$
Für eine \emph{Sprache} $L\subseteq \Sigma^*$ bezeichnet $h(L)$ die
Sprache
$$h(L) := \{\, h(x)\mid x\in L\,\}.$$

\item (4 Punkte)
Welche der Sprachen $h_j(L_i)$ sind regulär, wenn
$L_i$ eine der Sprachen aus Aufgabe~\regul\ ist und der
Homomorphismus $h_j$ folgendermaßen gegeben ist?
\begin{enumerate}
\item
$h_1(0)=a$, $h_1(1)=b$, $\Delta=\{a,b\}$.
\item
$h_2(0)=1$, $h_2(1)=1$.
\item
$h_3(0)=01$, $h_3(1)=\eps$.
\end{enumerate}
Es gibt je 2 Punkte für die Sprachen
$h_3(L_4)$ und $h_2(L_1)$.



\item (8 Punkte)
Erweitern Sie das in der Vorlesung vorgestellte \texttt{lex}-Programm%
\footnote{\tt
http://www.inf.fu-berlin.de/\char`\~rote/Lere/Grundlagen\%20der\%20theoretischen\%20Informatik/flex/summe.flex}
zur Addition aller in der Eingabe vorkommenden Zahlen
um folgende Funktionen:
\begin{enumerate}
\item
Bei Eingabe des Zeichens
\texttt{*} oder
\texttt{-} wird die nächste Zahl nicht addiert, sondern multipliziert
beziehungsweise subtrahiert.
Bei Eingabe von
\texttt{=} wird das bisherige Ergebnis ausgedruckt.
\item
Es werden zusätzlich auch Kommentare im Stil von Haskell verstanden:
Alles zwischen \texttt{--} und dem Ende der Zeile wird ignoriert.
\end{enumerate}
Die obigen Angaben lassen einige Fragen offen, zum Beispiel den Unterschied
zwischen Subtraktion (\texttt{5 - 3}) und einem
negativen Vorzeichen (\texttt{5 * -3}).
Ergänzen Sie zunächst
die obige Aufgabenspezifikation \emph{in Worten}, sodass das
Verhalten des Programmes eindeutig daraus hervorgeht.
Ihr Programm sollte dann dieser Spezifikation entsprechen.

\end{enumerate}
\end{document}
