kontextfrei.tex 1.53 KB
Newer Older
1
2
\section{Kontextfreie Sprache \hfill {\small 5 Punkte}}

3
\begin{enumerate}[a)]
4
\item Geben Sie die rekursive Definition des CYK-Algorithmus formal an:
5
6
7
8
9
  \begin{enumerate}
  \item[$i = j$] \[ V(i, i) := \]
  \item[$i < j$] \[ V(i, j) := \]
  \end{enumerate}
  
10
\item Gegeben Sei die folgende Grammatik
11
12
  $G = (V, \Sigma, \mathcal{P}, \mathcal{S})$,
  \begin{align*}
13
14
15
16
17
    \mathcal{S} &\rightarrow AB | DB \\
    A &\rightarrow a  \\
    B &\rightarrow b\\
    C &\rightarrow AB | DB \\
    B &\rightarrow AC
18
19
20
21
22
23
  \end{align*}

  Vervollständigen Sie die Tabelle für die Eingabe $w = $
  \texttt{aaabbb} an den Stellen $V(i, j)$. Ist das Wort $w$ in der
  Sprache $L(G)$ enthalten? Wie wissen sie dies?

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
  \vspace{1cm}
  
  \begin{center}
    \begin{tikzpicture}
      \matrix(M)[
      matrix of nodes,
      row sep=-\pgflinewidth,
      column sep=-\pgflinewidth,
      nodes={draw,minimum width=1.5cm,minimum height=1.5cm}
      ]{
        \{A\}&\{A\}&\{A\}&\{B\}&\{B\}&\{B\}\\
        \{\}&\{\}&\{S,C\}&\{\}&\{\}\\
        \{\}&\{D\}&\{\}&\{\}\\
        \{\}&\{S,C\}&\{\}\\
        $V(1, 5)$&$V(2, 6)$\\
        $V(1, 6)$\\
      };
      
      \begin{scope}[font=\ttfamily{}]
        \node[above=4pt of M-1-1] {a};
        \node[above=4pt of M-1-2] {a};
        \node[above=4pt of M-1-3] {a};
        \node[above=4pt of M-1-4] {b};
        \node[above=4pt of M-1-5] {b};
        \node[above=4pt of M-1-6] {b};
      \end{scope}         
    \end{tikzpicture}
  \end{center}
52
53
54
55
56
57
\end{enumerate}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "master"
%%% End: