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

\setcounter{page}{12}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{71}

\item
\begin{enumerate}
\item Zeigen Sie, dass die Sprache
$$L_1 = \{\,w \in \{a,b\}^* 
\mid \hbox{$w$ enthält gleich viele $a$'s wie $b$'s}\,\}$$
deterministisch kontextfrei ist.
\item Geben Sie eine kontextfreie Grammatik für die Sprache $L_1$ an.
\item 
Geben Sie eine kontextfreie Grammatik für die Sprache
$$L_2 = \{\,w %\in \{a,b,c\}^* 
\mid \hbox{$w$ enthält
doppelt so viele $a$'s wie $b$'s}\,\}$$
über dem
Alphabet
$\Sigma=\{a,b\}$ an.
\item Lösen Sie dieselbe Aufgabe
über dem
Alphabet
$\{a,b,c\}$.
\end{enumerate}

\item % (0 Punkte)
  \begin{enumerate}
  \item 
 Schreiben Sie eine kontextfreie Grammatik für
die durch den regulären Ausdruck
 $$(((0+(1)^*))\cdot((0+(0\cdot1))+\eps))$$
% über dem Alphabet $\{0,1\}$ 
definierte Sprache.
\item Wie kann man allgemein für einen regulären Ausdruck eine
entsprechende kontextfreie Grammatik erzeugen?
  \end{enumerate}

\item % (0 Punkte)
  \begin{enumerate}
  \item (6 Punkte) Wie kann man entscheiden, ob eine kontextfreie
    Grammatik eine endliche Sprache erzeugt?
  \item (4 Punkte) Kann man für eine gegebene kontextfreie Grammatik
    $G$ und eine durch einen endlichen Automaten gegebene reguläre
    Sprache $L_1$ entscheiden, ob $L(G)=L_1$ ist?
  \item (0 Punkte) Wie kann man für eine gegebene kontextfreie
    Grammatik $G$ und eine durch einen endlichen Automaten gegebene
    reguläre Sprache $L_1$ entscheiden, ob $L(G)\subseteq L_1$ ist?
    (Hier müssen Sie mehrere bekannte Ergebnisse kombinieren.)
  \end{enumerate}

\item Das Post'sche Korrespondenzproblem und kontextfreie Sprachen.
  \begin{enumerate}
  \item Für gegebene $x_1,\ldots,x_k \in \Sigma^*$ ist die Sprache
    $\{\,a_{i_n}a_{i_{n-1}}\ldots a_{i_1} x_{i_1}x_{i_{2}}\ldots
    x_{i_n} \mid n\ge 1,\ 1\le i_j \le k \,\}$ kontextfrei, wobei
    $a_1,a_2,\ldots,a_k$ neue Buchstaben sind, die nicht zu $\Sigma$
    gehören. (Versuchen Sie, mit möglichst wenigen Regeln auszukommen.)

  \item Zu jedem Post'schen Korrespondenzproblem kann man zwei
    kontextfreie Grammatiken $G_1$ und $G_2$ konstruieren, sodass das
    Post'schen Korrespondenzproblem genau dann eine Lösung hat, wenn
    $L(G_1)\cap L(G_2) \ne \emptyset$.

Was folgt daraus für das entsprechende Entscheidungsproblem für
kontextfreie Grammatiken?
  \end{enumerate}

\item % (7 Punkte)
Überprüfen Sie mit dem
CYK-Algorithmus,
ob das Wort $w=cdccd$ von der folgenden Grammatik erzeugt wird,
und geben Sie gegebenfalls eine Ableitung für $w$ an.
$$
\begin{array}{lll}
S\to AB \ \bigm| \  CD\ \bigm| \  AS
\qquad
&
B\to SB \ \bigm| \ d
\qquad
&
D\to CD \ \bigm| \ d
\\
A\to AS \ \bigm| \ DC
&
C\to CA \ \bigm| \ c
\end{array}
$$

\item Zeigen Sie, dass die Chomsky-Hierarchie echt ist:
Geben Sie eine Typ-0-Sprache an, die keine Typ-1-Sprache ist.
Geben Sie eine Typ-1-Sprache an, die keine Typ-2-Sprache ist.
Geben Sie eine Typ-2-Sprache an, die keine Typ-3-Sprache ist.
(Und geben Sie eine Sprache an, die keine Typ-0-Sprache ist.)

\item %(0 Punkte)
  Beschrieben Sie, wie man zu einem regulären Ausdruck einen regulären
  Ausdruck für die komplementäre Sprache findet.

\end{enumerate}
\end{document}
