--- a/hws/hw07.tex	Fri Nov 17 20:06:43 2023 +0000
+++ b/hws/hw07.tex	Tue Nov 28 11:42:31 2023 +0000
@@ -1,6 +1,7 @@
 \documentclass{article}
 \usepackage{../style}
 \usepackage{../grammar}
+\usepackage{../graphics}
 
 \begin{document}
 
@@ -24,6 +25,14 @@
 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 
 
@@ -46,6 +55,69 @@
 \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}
@@ -58,6 +130,31 @@
 \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}
@@ -89,6 +186,12 @@
 \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.
@@ -111,6 +214,12 @@
 \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, 
@@ -129,3 +238,21 @@
 %%% 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