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

\setcounter{page}{5}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{18}

\item (10 Punkte)
$L_1$ sei eine reguläre Sprache über dem Alphabet $\{0,1\}$, und
$$ L_2= \{\, w_10w_20\ldots 0w_n\mid w=w_1w_2\ldots w_n\in L_1,\ n\ge1
,\ w_i\in\{0,1\}
\,\}$$
sei die
Sprache, wo zwischen je zwei Buchstaben eine Null eingefügt
ist. (Am Ende wird \emph{keine} Null angehängt!)
Beweisen Sie, dass $L_2$ ebenfalls regulär ist.

\item   
\begin{enumerate}
\item  % (10 Punkte) 
Das Produkt von Automaten.\\
 Konstruieren Sie zu zwei gegebenen
DEAs
 $M^1=(Q^1,\Sigma,\delta^1,q_0^1,F^1)$
und
 $M^2=(Q^2,\Sigma,\delta^2,q_0^2,F^2)$
einen DEA für die Sprache $L(M^1) \cap L(M^2)$.
\item % (0 Punkte) 
Konstruieren Sie einen DEA für die Sprache $L(M^1) \cup L(M^2)$.

\end{enumerate}

\item % (10 Punkte)  
  \begin{enumerate}
  \item 
Konstruieren Sie einen  deterministischen endlichen Automaten, der die durch 5
teilbaren
Binärzahlen akzeptiert. Diesmal soll das niederwertigste Bit als erstes
gelesen werden.
\item 
Konstruieren Sie endliche Automaten für die durch 6
teilbaren
Dezimalzahlen, die (1) von der höchsten zur niedrigsten Stelle
 (2) von der niedrigsten zur höchsten Stelle
gelesen werden.
\end{enumerate}


\item Ist die Nerode-Relation einer Sprache $L$ immer eine
  Kongruenzrelation?
Ist die Nerode-Relation einer regulären Sprache $L$ immer eine Kongruenzrelation?

\item 
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 \hbox{$x$ enthält mindestens
so viele Nullen wie Einsen}\,\}$
% \item $L_4 = \{\, x \mid \hbox{jeder}$ Präfix von
% $x$ enthält mindestens
% so viele Nullen wie Einsen$\,\}$
\item % (2 Punkte) 
$L_4 = \{\, x \mid \hbox{die}$  
Anzahl der Nullen von $x$ unterscheidet sich um
 höchstens um 1 von der
Anzahl der Einsen$\,\}$
\item % (2 Punkte)
 $L_5 = \{\, x \mid \hbox{in}$ jedem Präfix von
$x$ unterscheidet sich die Anzahl der Nullen höchstens um 1 von der
Anzahl der Einsen$\,\}$
\item % (2 Punkte)
 $L_6 = \{\, x \mid \hbox{in}$ jedem Präfix von
$x$ unterscheidet sich die Anzahl der Nullen höchstens um 2 von der
Anzahl der Einsen$\,\}$
\end{enumerate}

\item (Zusatzaufgabe, 0 Punkte)
Für einen {Homomorphismus} $h\colon \Sigma^*\to \Delta^*$
und eine {Sprache} $L\subseteq \Sigma^*$ bezeichnet $h(L)$ die
Sprache
$$h(L) := \{\, h(x)\mid x\in L\,\}.$$
Beweisen Sie, dass das Bild $h(L)$ einer regulären Sprache $L$
unter einem Homomorphismus $h$ regulär ist.


\item (*)
Beweisen Sie: Wenn $L\in \Delta^*$ regulär ist
und $h\colon \Sigma^*\to \Delta^*$ ein Homomorphismus ist, ist
auch die folgende Sprache regulär:
$$ h^{-1}(L) := 
\{\, x\in \Sigma^* \mid h(x)\in L\,\}$$

\item 
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}


\item Konstruieren Sie den Minimalautomaten für den Automaten aus
  Aufgabe 15.

\end{enumerate}
\pagebreak
\end{document}
