4 \usepackage{../graphics}

    27 

    28 \solution{

    29   S -> bSAA ->  bbSAAAA ->

    30   bbbSAAAAAA ->

    31   bbbAAAAAA ->

    32   bbAbAAAAA -> .. ->

    33   bbAAAAAAb -> .. -> AAAbAAAbb -> .. -> aaabaaabb

    34   }

    58 \solution{

    59 \begin{center}

    60   \begin{tikzpicture}[scale=0.7,line width=0.8mm]

    61   \draw (-2,0) -- (4,0);

    62   \draw (-2,1) -- (4,1);

    63   \draw (-2,2) -- (3,2);

    64   \draw (-2,3) -- (2,3);

    65   \draw (-2,4) -- (1,4);

    66   \draw (-2,5) -- (0,5);

    67   \draw (-2,6) -- (-1,6);

    68   

    69   \draw (0,0) -- (0, 5);

    70   \draw (1,0) -- (1, 4);

    71   \draw (2,0) -- (2, 3);

    72   \draw (3,0) -- (3, 2);

    73   \draw (4,0) -- (4, 1);

    74   \draw (-1,0) -- (-1, 6);

    75   \draw (-2,0) -- (-2, 6);

    76   

    77   \draw (-1.5,-0.5) node {\footnotesize{}\texttt{The}}; 

    78   \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trainer}}; 

    79   \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{trains}}; 

    80   \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{the}}; 

    81   \draw ( 2.5,-0.5) node {\footnotesize{}\texttt{student}}; 

    82   \draw ( 3.5,-1.0) node {\footnotesize{}\texttt{team}};

    83   

    84   \draw (-1.5,0.5) node {$A$}; 

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

    86   \draw ( 0.5,0.5) node {$N,\!V$}; 

    87   \draw ( 1.5,0.5) node {$A$}; 

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

    89   \draw ( 3.5,0.5) node {$N,\!V$};

    90 

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

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

    93   \draw ( 0.5,1.5) node {$$}; 

    94   \draw ( 1.5,1.5) node {$N$}; 

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

    96 

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

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

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

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

   101 

   102   \draw (-1.5,3.5) node {$$}; 

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

   104   \draw ( 0.5,3.5) node {$N,\!P$};

   105 

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

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

   108 

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

   110 

   111   \draw (-2.4, 5.5) node {$1$}; 

   112   \draw (-2.4, 4.5) node {$2$}; 

   113   \draw (-2.4, 3.5) node {$3$}; 

   114   \draw (-2.4, 2.5) node {$4$}; 

   115   \draw (-2.4, 1.5) node {$5$}; 

   116   \draw (-2.4, 0.5) node {$6$}; 

   117   \end{tikzpicture}

   118   \end{center}

   119   }

   120 

   132 

   133 \solution{

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

   135 

   136   \begin{center}

   137     \begin{tabular}{lcl}

   138       $A$ & $::=$ & $0A1 \;|\; 01 \;|\; BB \;|\; B$\\

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

   140     \end{tabular}

   141   \end{center}

   142 

   143   Now we have to bring the rules into CNF form by adding additional

   144   non-terminals, like $Z$, $O$, $T$,  and splitting up the rules into ``twos'':

   145 

   146   \begin{center}

   147     \begin{tabular}{lcl}

   148       $A$ & $::=$ & $ZC \;|\; ZO \;|\; BB \;|\; 2$\\

   149       $B$ & $::=$ & $2 \;|\; TB$\\

   150       $C$ & $::=$ & $AO$\\

   151       $Z$ & $::=$ & $0$\\

   152       $O$ & $::=$ & $1$\\

   153       $T$ & $::=$ & $2$\\                           

   154     \end{tabular}

   155   \end{center}   

   156 }

   189 \solution{

   190   (i) this is ambiguous -> it's an instance of the dangling else;

   191   (ii) rules of the form $B ::= B \cdot B$ are always ambiguous $B \cdot B\cdot B$

   192   (iii) this is fine

   193   (iv) same as (ii) $E\cdot + \cdot E \cdot + \cdot E$

   194   }

   217 \solution{

   218   The point is that Grammar 1 is un-ambiguous, while the second is ambiguous.

   219   Grammar 1 parses the strings as (9 - 5) + 2. Grammar 2 is ambiguous and

   220   there are two possibilities (9 - 5) + 2 and 9 - (5 + 2).

   221   

   222 }

   241 

   242 

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

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

   245 The trainer trains |the student N N => N 

   246 The trainer trains the |student 

   247 

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

   249 trainer trains| the student team N o N => N

   250 trainer trains the |student team 

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

   252 

   253 

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

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

   256 The trainer trains| the student team N o N => N

   257 The trainer trains the| student team 

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