
diff -r 6518475020fc -r 90796ee3c17a hws/hw07.tex
--- a/hws/hw07.tex	Fri Nov 15 10:29:04 2013 +0000
+++ b/hws/hw07.tex	Sun Nov 17 18:16:20 2013 +0000
@@ -13,11 +13,21 @@
 \section*{Homework 7}
 
 \begin{enumerate}
-\item Suppose the following grammar for positive numbers
+\item Suppose the context-sensitive grammar
 
 \begin{center}
+\begin{tabular}{lcl}
+$S$ & $\rightarrow$ &  $bSAA\;|\; \epsilon$\\
+$A$ & $\rightarrow$ & $a$\\
+$bA$ & $\rightarrow$ & $Ab$\\
+\end{tabular}
+\end{center}
 
-\end{center}
+where $S$ is the starting symbol of the grammar. 
+Give a derivation  of the string $"\!aaabaaabb"$. 
+What can you say about the number of as and bs in the
+strings recognised by this grammar.
+
 
 \item Consider the following grammar 
 
@@ -41,14 +51,27 @@
 \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:
+\item Transform the grammar
 
 \begin{center}
-\url{http://callumacrae.github.com/regex-tuesday/challenge11.html}
+\begin{tabular}{lcl}
+$A$ & $\rightarrow$ & $0A1 \;|\; BB$\\
+$B$ & $\rightarrow$ & $\epsilon \;|\; 2B$
+\end{tabular}
 \end{center}
+
+\noindent
+into Chomsky normal form.
+
+
+%\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}




