11 \begin{enumerate} |
11 \begin{enumerate} |
12 \item Suppose the context-sensitive grammar |
12 \item Suppose the context-sensitive grammar |
13 |
13 |
14 \begin{center} |
14 \begin{center} |
15 \begin{tabular}{lcl} |
15 \begin{tabular}{lcl} |
16 $S$ & $\rightarrow$ & $bSAA\;|\; \epsilon$\\ |
16 $S$ & $::=$ & $bSAA\;|\; \epsilon$\\ |
17 $A$ & $\rightarrow$ & $a$\\ |
17 $A$ & $::=$ & $a$\\ |
18 $bA$ & $\rightarrow$ & $Ab$\\ |
18 $bA$ & $::=$ & $Ab$\\ |
19 \end{tabular} |
19 \end{tabular} |
20 \end{center} |
20 \end{center} |
21 |
21 |
22 where $S$ is the starting symbol of the grammar. |
22 where $S$ is the starting symbol of the grammar. |
23 Give a derivation of the string $"\!aaabaaabb"$. |
23 Give a derivation of the string $"\!aaabaaabb"$. |
48 |
48 |
49 \item Transform the grammar |
49 \item Transform the grammar |
50 |
50 |
51 \begin{center} |
51 \begin{center} |
52 \begin{tabular}{lcl} |
52 \begin{tabular}{lcl} |
53 $A$ & $\rightarrow$ & $0A1 \;|\; BB$\\ |
53 $A$ & $::=$ & $0A1 \;|\; BB$\\ |
54 $B$ & $\rightarrow$ & $\epsilon \;|\; 2B$ |
54 $B$ & $::=$ & $\epsilon \;|\; 2B$ |
55 \end{tabular} |
55 \end{tabular} |
56 \end{center} |
56 \end{center} |
57 |
57 |
58 \noindent |
58 \noindent |
59 into Chomsky normal form. |
59 into Chomsky normal form. |
60 |
60 |
61 \item Consider the following grammar $G$ |
61 \item Consider the following grammar $G$ |
62 |
62 |
63 \begin{center} |
63 \begin{center} |
64 \begin{tabular}{l} |
64 \begin{tabular}{l} |
65 $S \rightarrow \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\ |
65 $S ::= \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\ |
66 $S \rightarrow \texttt{print} \cdot S$\\ |
66 $S ::= \texttt{print} \cdot S$\\ |
67 $S \rightarrow \texttt{begin} \cdot B\cdot \texttt{end}$\\ |
67 $S ::= \texttt{begin} \cdot B\cdot \texttt{end}$\\ |
68 $B \rightarrow S\cdot \texttt{;}$\\ |
68 $B ::= S\cdot \texttt{;}$\\ |
69 $B \rightarrow S\cdot \texttt{;} \cdot B$\\ |
69 $B ::= S\cdot \texttt{;} \cdot B$\\ |
70 $S \rightarrow num$\\ |
70 $S ::= num$\\ |
71 $E \rightarrow num$\\ |
71 $E ::= num$\\ |
72 $B \rightarrow num$ |
72 $B ::= num$ |
73 \end{tabular} |
73 \end{tabular} |
74 \end{center} |
74 \end{center} |
75 |
75 |
76 where $S$ is the start symbol and $S$, $E$ and $B$ are |
76 where $S$ is the start symbol and $S$, $E$ and $B$ are |
77 non-terminals. |
77 non-terminals. |
80 the combined grammar is ambiguous. If yes, give a string that |
80 the combined grammar is ambiguous. If yes, give a string that |
81 has more than one parse tree. |
81 has more than one parse tree. |
82 |
82 |
83 \begin{center} |
83 \begin{center} |
84 \begin{tabular}{rl} |
84 \begin{tabular}{rl} |
85 (i) & $S \rightarrow \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\ |
85 (i) & $S ::= \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\ |
86 (ii) & $B \rightarrow B \cdot B$\\ |
86 (ii) & $B ::= B \cdot B$\\ |
87 (iii) & $E \rightarrow ( \cdot E \cdot )$\\ |
87 (iii) & $E ::= ( \cdot E \cdot )$\\ |
88 (iv) & $E \rightarrow E \cdot + \cdot E$ |
88 (iv) & $E ::= E \cdot + \cdot E$ |
89 \end{tabular} |
89 \end{tabular} |
90 \end{center} |
90 \end{center} |
91 |
91 |
92 |
92 |
|
93 \item Suppose the string $``9-5+2''$. Give all ASTs that |
|
94 the following two grammars generate for this string. |
|
95 |
|
96 Grammar 1, where List is the starting symbol: |
|
97 |
|
98 \begin{center} |
|
99 \begin{tabular}{lcl} |
|
100 $List$ & $::=$ & $List + Digit \mid List - Digit \mid Digit$\\ |
|
101 $Digit$ & $::=$ & $0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$ |
|
102 \end{tabular} |
|
103 \end{center} |
|
104 |
|
105 Grammar 2, where String is the starting symbol: |
|
106 |
|
107 \begin{center} |
|
108 \begin{tabular}{@{}lcl@{}} |
|
109 $String$ & $::=$ & $String + String \mid String - String \mid$\\ |
|
110 & & $0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$ |
|
111 \end{tabular} |
|
112 \end{center} |
|
113 |
|
114 |
|
115 |
93 %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
116 %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
94 %\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
117 %\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
95 %\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
118 %\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
96 %See: |
119 %See: |
97 |
120 |