% 9. 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}{11}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{63}

\item %(10 Punkte)
  \begin{enumerate}
  \item 
$L_1$ sei eine kontextfreie Sprache über dem Alphabet $\{0,1\}$, und
$$ L_2= \{\, w_10w_20\ldots w_n0\mid w_1w_2\ldots w_n\in L_1,\ n\ge0
\,\}$$
sei die
Sprache, wo nach jedem Buchstaben jedes Wortes eine Null eingefügt
ist.
Beweisen Sie, dass $L_2$ ebenfalls kontextfrei ist.

\item % (mit den bisherigen Kenntnissen schwierig)
Lösen Sie die gleiche Aufgabe für die Sprache
$$
L_3= \{\, w_10w_21w_30w_41w_50\ldots \mid w_1w_2\ldots w_n\in L_1,\ 
n\ge0 \,\},$$
wo nach jedem Buchstaben abwechselnd eine Null und eine
Eins eingefügt wird.
  \end{enumerate}

\item Wenn man beim Beweis des Pumpinglemmas den \emph{längsten} Pfad
  im Ableitungsbaum betrachtet, kann man die stärkere Aussage
  herleiten, dass es eine Zerlegung $w=xyzuv$ mit der
  \emph{Längenbeschränkung} $|yzu|\le n_0$ gibt, sodass all Wörter $xy^izu^iv\in L$ sind.

\item (10 Punkte)
Beweisen Sie, dass die folgenden Sprachen \emph{über dem
Alphabet
$\{a,b,c\}$}
nicht
kontextfrei sind.
\begin{enumerate}
\item 
%$L_1 = \{\,w %\in \{a,b,c\}^* 
%\mid \hbox{$w$ enthält
%doppelt so viele $a$'s wie $b$'s}\,\}$
$L_1' = \{\,w %\in \{a,b,c\}^* 
\mid \hbox{$w$ enthält
doppelt so viele $a$'s wie $b$'s
und doppelt so viele $b$'s wie $c$'s
}\,\}$
\item 
$L_2 = \{\,a^ib^jc^k\mid i>j\ge k\ge 1\,\}$
\end{enumerate}

\item % (0 Punkte)
 Schreiben Sie eine kontextfreie Grammatik für
die regulären Ausdrücke über dem Alphabet $\{0,1\}$.
Sie können annehmen, dass die Ausdrücke voll geklammert sind,
entsprechend der ursprünglichen Definition regulärer Ausdrücke,
zum Beispiel $$(((0+(1)^*))\cdot((0+(0\cdot1))+\eps))$$

\item % (0 Punkte)
Kontextfreie Sprachen sind unter Umkehrung (Spiegelung) abgeschlossen.

\item %(4 Punkte)
Entfernen Sie überflüssige Variablen und Regeln aus dieser Grammatik:
$$
\begin{array}{lll}
S\to AB \ \bigm| \ CA
 \qquad & B\to BC \ \bigm| \ AB  \ \bigm| \ BDE
 \qquad & D\to ADEba \ \bigm| \ ACA \\
A \to a & C\to aB \ \bigm| \ c
&E \to DD \ \bigm| \ BA
\end{array}
$$
% \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 (0 Punkte)
%  \begin{enumerate}
%  \item 
Übersetzen Sie den folgenden vereinfachten Ausschnitt aus der Syntax
der Programmiersprache Java aus der EBNF (extended Backus-Naur-Form)
in entsprechende kontextfreie Regeln:
\vskip -3pt
\hrule height 0pt
\begin{tabbing}
  \qquad\=\+
TryBlock \qquad \= $::=$   \textbf{try} Block Catches $\ \bigm|\ $
          \textbf{try} Block [ Catches ] \textbf{finally} Block
\\
Catches \>$::=$ CatchClause $\{$ CatchClause $\}$\\ 
CatchClause \>$::=$ \textbf{catch (} Exception Identifier \textbf{)} Block
\\
Exception \>$::=$ Identifier
\end{tabbing}
\vskip -3pt%\hrule height 0pt
Die Terminalsymbole sind hier fett gedruckt. Sie können die
Variablen durch passende einbuchstabige Namen abkürzen.
%
% \item
(Wozu dient eigentlich die Variable "`Exception"',
 die
man doch genausogut zusammen mit der Regel "`Exception $::=$ Identifier"'
eliminieren könnte?)
%  \end{enumerate}

% \item %(0 Punkte)
%  Kann man für eine gegebene kontextfreie Grammatik $G$ und
% eine gegebene reguläre Sprache $L_1$ entscheiden, ob
% $L(G)=L_1$ ist?



\item
  \begin{enumerate}
\item %(5 Punkte)
Bleibt eine eindeutige Grammatik bei der
Transformation in Chomsky-Normal\-form eindeutig?
% Beweisen Sie Ihre Antwort.

\item %(0 Punkte)
$G$ sei eine
Grammatik
in Chomsky-Normalform, die eine endliche Sprache erzeugt.
Finden Sie eine Schranke für das längste Wort in $L(G)$.

\item %(0 Punkte)
Wie lang kann die Ableitung eines Wortes $w$ bei einer
Grammatik in Chomsky-Normalform höchstens sein?

  \end{enumerate}

% \item (0 Punkte)
% Wie kann man zu einem regulären Ausdruck einen regulären Ausdruck für
% die
% komplementäre Sprache finden?



\end{enumerate}
\end{document}
