\documentclass{article}
\usepackage{../style}
\usepackage{../grammar}

\begin{document}

\section*{Homework 7}

\HEADER

\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 the
strings recognised by this grammar.


\item Consider the following grammar 

\begin{plstx}[margin=1cm]
  : \meta{S\/} ::= \meta{N\/}\cdot \meta{P\/}\\
  : \meta{P\/} ::= \meta{V\/}\cdot \meta{N\/}\\
  : \meta{N\/} ::= \meta{N\/}\cdot \meta{N\/}\\
  : \meta{N\/} ::= \meta{A\/}\cdot \meta{N\/}\\
  : \meta{N\/} ::= \texttt{student} \mid \texttt{trainer} \mid \texttt{team} \mid \texttt{trains}\\
  : \meta{V\/} ::= \texttt{trains} \mid \texttt{team}\\
  : \meta{A\/} ::= \texttt{The} \mid \texttt{the}\\
\end{plstx}


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 Transform the grammar

\begin{center}
\begin{tabular}{lcl}
$A$ & $\rightarrow$ & $0A1 \;|\; BB$\\
$B$ & $\rightarrow$ & $\epsilon \;|\; 2B$
\end{tabular}
\end{center}

\noindent
into Chomsky normal form.

\item Consider the following grammar $G$

\begin{center}
\begin{tabular}{l}
$S \rightarrow \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\
$S \rightarrow \texttt{print} \cdot S$\\
$S \rightarrow \texttt{begin} \cdot B\cdot \texttt{end}$\\
$B \rightarrow S\cdot \texttt{;}$\\
$B \rightarrow S\cdot \texttt{;} \cdot B$\\
$S \rightarrow num$\\
$E \rightarrow num$\\
$B \rightarrow num$
\end{tabular}
\end{center}

where $S$ is the start symbol and $S$, $E$ and $B$ are
non-terminals.

Check each rule below and decide whether, when added to $G$,
the combined grammar is ambiguous. If yes, give a string that
has more than one parse tree.

\begin{center}
\begin{tabular}{rl}
(i)   & $S \rightarrow \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\
(ii)  & $B \rightarrow B \cdot B$\\
(iii) & $E \rightarrow ( \cdot E \cdot )$\\
(iv)  & $E \rightarrow E \cdot + \cdot E$
\end{tabular}
\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: