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

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

\solution{
  S -> bSAA ->  bbSAAAA ->
  bbbSAAAAAA ->
  bbbAAAAAA ->
  bbAbAAAAA -> .. ->
  bbAAAAAAb -> .. -> AAAbAAAbb -> .. -> aaabaaabb
  }


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

\solution{
\begin{center}
  \begin{tikzpicture}[scale=0.7,line width=0.8mm]
  \draw (-2,0) -- (4,0);
  \draw (-2,1) -- (4,1);
  \draw (-2,2) -- (3,2);
  \draw (-2,3) -- (2,3);
  \draw (-2,4) -- (1,4);
  \draw (-2,5) -- (0,5);
  \draw (-2,6) -- (-1,6);
  
  \draw (0,0) -- (0, 5);
  \draw (1,0) -- (1, 4);
  \draw (2,0) -- (2, 3);
  \draw (3,0) -- (3, 2);
  \draw (4,0) -- (4, 1);
  \draw (-1,0) -- (-1, 6);
  \draw (-2,0) -- (-2, 6);
  
  \draw (-1.5,-0.5) node {\footnotesize{}\texttt{The}}; 
  \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trainer}}; 
  \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{trains}}; 
  \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{the}}; 
  \draw ( 2.5,-0.5) node {\footnotesize{}\texttt{student}}; 
  \draw ( 3.5,-1.0) node {\footnotesize{}\texttt{team}};
  
  \draw (-1.5,0.5) node {$A$}; 
  \draw (-0.5,0.5) node {$N$}; 
  \draw ( 0.5,0.5) node {$N,\!V$}; 
  \draw ( 1.5,0.5) node {$A$}; 
  \draw ( 2.5,0.5) node {$N$}; 
  \draw ( 3.5,0.5) node {$N,\!V$};

  \draw (-1.5,1.5) node {$N$}; 
  \draw (-0.5,1.5) node {$N$}; 
  \draw ( 0.5,1.5) node {$$}; 
  \draw ( 1.5,1.5) node {$N$}; 
  \draw ( 2.5,1.5) node {$N$};

  \draw (-1.5,2.5) node {$N$}; 
  \draw (-0.5,2.5) node {$ $}; 
  \draw ( 0.5,2.5) node {$N,\!P$}; 
  \draw ( 1.5,2.5) node {$N$};

  \draw (-1.5,3.5) node {$$}; 
  \draw (-0.5,3.5) node {$N,\!S$}; 
  \draw ( 0.5,3.5) node {$N,\!P$};

  \draw (-1.5,4.5) node {$N,\!S$}; 
  \draw (-0.5,4.5) node {$N,\!S$};

  \draw (-1.5,5.5) node {$N,\!S$}; 

  \draw (-2.4, 5.5) node {$1$}; 
  \draw (-2.4, 4.5) node {$2$}; 
  \draw (-2.4, 3.5) node {$3$}; 
  \draw (-2.4, 2.5) node {$4$}; 
  \draw (-2.4, 1.5) node {$5$}; 
  \draw (-2.4, 0.5) node {$6$}; 
  \end{tikzpicture}
  \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.

\solution{
  First one has to eliminate $\epsilon$. This means we obtain the rules:

  \begin{center}
    \begin{tabular}{lcl}
      $A$ & $::=$ & $0A1 \;|\; 01 \;|\; BB \;|\; B$\\
      $B$ & $::=$ & $2 \;|\; 2B$
    \end{tabular}
  \end{center}

  Now we have to bring the rules into CNF form by adding additional
  non-terminals, like $Z$, $O$, $T$,  and splitting up the rules into ``twos'':

  \begin{center}
    \begin{tabular}{lcl}
      $A$ & $::=$ & $ZC \;|\; ZO \;|\; BB \;|\; 2$\\
      $B$ & $::=$ & $2 \;|\; TB$\\
      $C$ & $::=$ & $AO$\\
      $Z$ & $::=$ & $0$\\
      $O$ & $::=$ & $1$\\
      $T$ & $::=$ & $2$\\                           
    \end{tabular}
  \end{center}   
}

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

\solution{
  (i) this is ambiguous -> it's an instance of the dangling else;
  (ii) rules of the form $B ::= B \cdot B$ are always ambiguous $B \cdot B\cdot B$
  (iii) this is fine
  (iv) same as (ii) $E\cdot + \cdot E \cdot + \cdot E$
  }

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

\solution{
  The point is that Grammar 1 is un-ambiguous, while the second is ambiguous.
  Grammar 1 parses the strings as (9 - 5) + 2. Grammar 2 is ambiguous and
  there are two possibilities (9 - 5) + 2 and 9 - (5 + 2).
  
}

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


The| trainer trains the student A {N,S} => N 
The trainer |trains the student N {N, P} => N S
The trainer trains |the student N N => N 
The trainer trains the |student 

trainer |trains the student team N o {N, P} => N, S
trainer trains| the student team N o N => N
trainer trains the |student team 
trainer trains the student |team {N, P} o {N, V} => N


The| trainer trains the student team A o (N,S) => N
The trainer| trains the student team N o (N,P) => N, S
The trainer trains| the student team N o N => N
The trainer trains the| student team 
The trainer trains the student| team (N,S) o (N,V) => N