\documentclass[11pt]{article}
\usepackage{A4,amsmath,amssymb,german}
\pagestyle{empty}
\parindent0em
\begin{document}
Prof. Dr. Volker Strehl \hfill 15.7.1999
\\
IMMD-8
\begin{center}
\Large
\"Ubungen zur\\
Einf\"uhrung in die Theoretische Informatik III\\
SS 1999
\end{center}

\begin{itemize}
\item[26.]
Diese Aufgabe geh\"ort zusammen mit der vorigen in den 
Bereich der Automatentheorie und ist als Erg\"anzung zum Stoff
von ``Theoretische Informatik I'' gedacht. Sie sollte Anregung bieten,
sich wieder einmal mit diesem Bereich auseinanderzusetzen. \\
\begin{enumerate}
\item
Es sei $\Sigma$ ein endliches Alphabet
und es seien $A, B \subset \Sigma^*$ Sprachen \"uber $\Sigma$.
Beweisen Sie die als ``\textsc{Arden}s Lemma'' bekannte Aussage:
\begin{enumerate}
\item
Die Sprache $A^* \cdot B$ ist die (bez\"uglich Inklusion) kleinste
L\"osung des linearen Gleichungssystems f\"ur formale Sprachen:
\[
X = A \cdot X + B
\]
\item
Geh\"ort $\lambda$ (= leeres Wort) nicht zu $A$, so ist
$A^*\cdot B$ auch die \textit{einzige} L\"osung dieser Gleichung.
\end{enumerate}
Beachten Sie: sind $A,B$ selbst regul\"are (= rationale) Sprachen, so
ist auch die L\"osung des Gleichungssystems regul\"ar.
\item
Bevor Sie verallgemeinern,
\begin{enumerate}
\item
versuchen Sie das folgende lineare Gleichungssystem zu l\"osen:
\[
X = a \cdot X + b \cdot Y + a~~,~~
Y = a \cdot X + a \cdot Y + b
\]
\item
Ein endlicher Automat $\mathcal{A}$ \"uber dem Alphabet
$\Sigma = \{a,b\}$ habe drei Zusta\"ande $A,B,C$, dabei sei
$B$ Anfangszustand und $A,B$ seien akzeptierende Zust\"ande.
Die \"Ubergangsfunktion 
$\delta : \{A,B,C\}\times \{a,b\} \rightarrow \{A,B,C\}$
sei gegeben durch 
\[
\delta(A,a) = B, \delta(A,b) = \delta(B,a) = A,
\delta(B,b) = C, \delta(C,a) = \delta(C,b) = C
\]
Beschreiben Sie die von dem endlichen Automaten akzeptierte Sprache 
mit Hilfe eines linearen Gleichungssystems und l\"osen Sie dieses.
\end{enumerate}
\item
Formulieren und beweisen Sie eine allgemeine Aussage
\"uber die L\"osungen von linearen Gleichungssystemen,
deren Koeffizienten und L\"osungen (regul\"are) formale Sprachen sind.
\"Ubertragen Sie diese Aussage auf endliche Automaten (Theorem von
\textsc{Kleene}).
\end{enumerate} 
\end{itemize}
\end{document}