\documentclass{article}\usepackage{charter}\usepackage{hyperref}\usepackage{amssymb}\usepackage{amsmath}\usepackage{tikz}\usetikzlibrary{automata}\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions\begin{document}\section*{Homework 7}\begin{enumerate}\item Suppose the following grammar for positive numbers\begin{center}\end{center}\item Consider the following grammar \begin{center}\begin{tabular}{l}$S \rightarrow N\cdot P$\\$P \rightarrow V\cdot N$\\$N \rightarrow N\cdot N$\\$N \rightarrow A \cdot N$\\$N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\$V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\$A \rightarrow \texttt{The} \;|\; \texttt{the}$\\\end{tabular}\end{center}where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals.Using the CYK-algorithm, check whether or not the following string can be parsedby the grammar:\begin{center}\texttt{The trainer trains the student team}\end{center}\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, \texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!See:\begin{center}\url{http://callumacrae.github.com/regex-tuesday/challenge11.html}\end{center}\end{enumerate}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: