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