24 strings recognised by this grammar. |
25 strings recognised by this grammar. |
25 |
26 |
26 |
27 |
27 \item Consider the following grammar |
28 \item Consider the following grammar |
28 |
29 |
29 \begin{center} |
30 \begin{plstx}[margin=1cm] |
30 \begin{tabular}{l} |
31 : \meta{S\/} ::= \meta{N\/}\cdot \meta{P\/}\\ |
31 $S \rightarrow N\cdot P$\\ |
32 : \meta{P\/} ::= \meta{V\/}\cdot \meta{N\/}\\ |
32 $P \rightarrow V\cdot N$\\ |
33 : \meta{N\/} ::= \meta{N\/}\cdot \meta{N\/}\\ |
33 $N \rightarrow N\cdot N$\\ |
34 : \meta{N\/} ::= \meta{A\/}\cdot \meta{N\/}\\ |
34 $N \rightarrow A \cdot N$\\ |
35 : \meta{N\/} ::= \texttt{student} \mid \texttt{trainer} \mid \texttt{team} \mid \texttt{trains}\\ |
35 $N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\ |
36 : \meta{V\/} ::= \texttt{trains} \mid \texttt{team}\\ |
36 $V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\ |
37 : \meta{A\/} ::= \texttt{The} \mid \texttt{the}\\ |
37 $A \rightarrow \texttt{The} \;|\; \texttt{the}$\\ |
38 \end{plstx} |
38 \end{tabular} |
39 |
39 \end{center} |
|
40 |
40 |
41 where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals. |
41 where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals. |
42 Using the CYK-algorithm, check whether or not the following string can be parsed |
42 Using the CYK-algorithm, check whether or not the following string can be parsed |
43 by the grammar: |
43 by the grammar: |
44 |
44 |