hws/hw07.tex
changeset 681 7b7736bea3ca
parent 393 494b44b439bf
child 897 904de68a27a4
equal deleted inserted replaced
680:eecc4d5a2172 681:7b7736bea3ca
     1 \documentclass{article}
     1 \documentclass{article}
     2 \usepackage{../style}
     2 \usepackage{../style}
       
     3 \usepackage{../grammar}
     3 
     4 
     4 \begin{document}
     5 \begin{document}
     5 
     6 
     6 \section*{Homework 7}
     7 \section*{Homework 7}
     7 
     8 
    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