1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 \usepackage{tikz}

     7 \usetikzlibrary{automata}

     8 

     9 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    10 

    11 \begin{document}

    12 

    13 \section*{Homework 8}

    14 

    15 \begin{enumerate}

    16 \item Suppose the following grammar for the WHILE-language:

    17 

    18 \begin{center}

    19 \begin{tabular}{l}

    20 $S \rightarrow N\cdot P$\\

    21 $P \rightarrow V\cdot N$\\

    22 $N \rightarrow N\cdot N$\\

    23 $N \rightarrow A \cdot N$\\

    24 $N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\

    25 $V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\

    26 $A \rightarrow \texttt{The} \;|\; \texttt{the}$\\

    27 \end{tabular}

    28 \end{center}

    29 

    30 

    31 \item Consider the following grammar 

    32 

    33 \begin{center}

    34 \begin{tabular}{l}

    35 $S \rightarrow N\cdot P$\\

    36 $P \rightarrow V\cdot N$\\

    37 $N \rightarrow N\cdot N$\\

    38 $N \rightarrow A \cdot N$\\

    39 $N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\

    40 $V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\

    41 $A \rightarrow \texttt{The} \;|\; \texttt{the}$\\

    42 \end{tabular}

    43 \end{center}

    44 

    45 where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals.

    46 Using the CYK-algorithm, check whether or not the following string can be parsed

    47 by the grammar:

    48 

    49 \begin{center}

    50 \texttt{The trainer trains the student team}

    51 \end{center}

    52 

    53 \item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, 

    54 \texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example

    55 \texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!

    56 See:

    57 

    58 \begin{center}

    59 \url{http://callumacrae.github.com/regex-tuesday/challenge11.html}

    60 \end{center}

    61 \end{enumerate}

    62 

    63 \end{document}

    64 

    65 %%% Local Variables: 

    66 %%% mode: latex

    67 %%% TeX-master: t

    68 %%% End: