--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hw08.tex	Fri Nov 23 21:21:27 2012 +0000
@@ -0,0 +1,68 @@
+\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 8}
+
+\begin{enumerate}
+\item Suppose the following grammar for the WHILE-language:
+
+\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}
+
+
+\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: