hws/hw07.tex
changeset 681 9efdee02c95e
parent 393 494b44b439bf
child 897 8074a1abb928
equal deleted inserted replaced
680:242c1f0e60df 681:9efdee02c95e
     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