\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$ & $::=$ &  $bSAA\;|\; \epsilon$\\

$A$ & $::=$ & $a$\\

$bA$ & $::=$ & $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$ & $::=$ & $0A1 \;|\; BB$\\

$B$ & $::=$ & $\epsilon \;|\; 2B$

\end{tabular}

\end{center}

\noindent

into Chomsky normal form.

\item Consider the following grammar $G$

\begin{center}

\begin{tabular}{l}

$S ::= \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\

$S ::= \texttt{print} \cdot S$\\

$S ::= \texttt{begin} \cdot B\cdot \texttt{end}$\\

$B ::= S\cdot \texttt{;}$\\

$B ::= S\cdot \texttt{;} \cdot B$\\

$S ::= num$\\

$E ::= num$\\

$B ::= 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 ::= \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\

(ii)  & $B ::= B \cdot B$\\

(iii) & $E ::= ( \cdot E \cdot )$\\

(iv)  & $E ::= E \cdot + \cdot E$

\end{tabular}

\end{center}

\item Suppose the string $``9-5+2''$. Give all ASTs that

  the following two grammars generate for this string.

Grammar 1, where List is the starting symbol:

\begin{center}

\begin{tabular}{lcl}

$List$ & $::=$ &  $List + Digit \mid List - Digit \mid Digit$\\

$Digit$ & $::=$ & $0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$

\end{tabular}

\end{center}

Grammar 2, where String is the starting symbol:

\begin{center}

\begin{tabular}{@{}lcl@{}}

  $String$ & $::=$ & $String + String \mid String - String \mid$\\

  & & $0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$

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