\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 parsed
by 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: 
