\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 context-sensitive grammar\begin{center}\begin{tabular}{lcl}$S$ & $\rightarrow$ & $bSAA\;|\; \epsilon$\\$A$ & $\rightarrow$ & $a$\\$bA$ & $\rightarrow$ & $Ab$\\\end{tabular}\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 thestrings recognised by this grammar.\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 Transform the grammar\begin{center}\begin{tabular}{lcl}$A$ & $\rightarrow$ & $0A1 \;|\; BB$\\$B$ & $\rightarrow$ & $\epsilon \;|\; 2B$\end{tabular}\end{center}\noindentinto 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}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: