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

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

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 10.~\"Ubungsblatt\par
% ENTWURF
}
\medskip
Letztes Pflichtübungsblatt --- Abgabe bis Montag, 9. Juli 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{59}

\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 die überflüssigen 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 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 (5 Punkte)
Betrachten Sie die deterministischen Zweiweg-Kellerautomaten
mit dem Eingabealphabet $\Sigma=\{a\}$, dem Kelleralphabet
$\Gamma=\{0,1,Z_0\}$
und der Übergangsfunktion $\delta\colon 
Q
\times \Gamma 
\times(\Sigma\cup\{\Diamond,\$\}) \to
 Q\times\Gamma^*\times \{L,N,R\}$.
 \begin{tabbing}
\qquad \=\+   
$\delta(q_0,\gamma,a)=(q_0,0\gamma,R)$, für $\gamma\in\Gamma$.\\
$\delta(q_0,\gamma,\$)=(q_1,\gamma,N)$, für $\gamma\in\Gamma$.\\
$\delta(q_1,1,x)=(q_1,\eps,L)$, für $x=0$ oder $x=\$$.\\
$\delta(q_1,0,x)=(q_0,1,N)$, für $x=0$ oder $x=\$$.\\
$\delta(q_1,Z_0,x)=(q_1,\eps,N)$, für $x=0$ oder $x=\$$.
 \end{tabbing}
Die übrigen Werte von $\delta$ (für $x=\Diamond$) sind beliebig.
\begin{enumerate}
\item (0 Punkte)
Beschreiben Sie das Verhalten des Automaten
 bei Eingabe des Wortes $a^n$,
für $n=0,1,2,3$ und für allgemeines $n$.
\item (5 Punkte)
Bestimmen Sie die Entladefunktion $E\colon
Q\times \{0,\ldots,n+1\}\times \Gamma \to
Q\times \{0,\ldots,n+1\}$ bei Eingabe des Wortes $a^n$.
\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}
\eject
\end{document}