\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 thestrings 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 parsedby 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}\noindentinto 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$ arenon-terminals.Check each rule below and decide whether, when added to $G$,the combined grammar is ambiguous. If yes, give a string thathas 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 parse trees 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 SThe trainer trains |the student N N => N The trainer trains the |student trainer |trains the student team N o {N, P} => N, Strainer trains| the student team N o N => Ntrainer trains the |student team trainer trains the student |team {N, P} o {N, V} => NThe| trainer trains the student team A o (N,S) => NThe trainer| trains the student team N o (N,P) => N, SThe trainer trains| the student team N o N => NThe trainer trains the| student team The trainer trains the student| team (N,S) o (N,V) => N