
diff -r de5fd5e2ab0a -r 8074a1abb928 hws/hw07.tex
--- a/hws/hw07.tex	Thu Nov 10 23:49:29 2022 +0000
+++ b/hws/hw07.tex	Tue Nov 15 11:34:33 2022 +0000
@@ -13,9 +13,9 @@
 
 \begin{center}
 \begin{tabular}{lcl}
-$S$ & $\rightarrow$ &  $bSAA\;|\; \epsilon$\\
-$A$ & $\rightarrow$ & $a$\\
-$bA$ & $\rightarrow$ & $Ab$\\
+$S$ & $::=$ &  $bSAA\;|\; \epsilon$\\
+$A$ & $::=$ & $a$\\
+$bA$ & $::=$ & $Ab$\\
 \end{tabular}
 \end{center}
 
@@ -50,8 +50,8 @@
 
 \begin{center}
 \begin{tabular}{lcl}
-$A$ & $\rightarrow$ & $0A1 \;|\; BB$\\
-$B$ & $\rightarrow$ & $\epsilon \;|\; 2B$
+$A$ & $::=$ & $0A1 \;|\; BB$\\
+$B$ & $::=$ & $\epsilon \;|\; 2B$
 \end{tabular}
 \end{center}
 
@@ -62,14 +62,14 @@
 
 \begin{center}
 \begin{tabular}{l}
-$S \rightarrow \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\
-$S \rightarrow \texttt{print} \cdot S$\\
-$S \rightarrow \texttt{begin} \cdot B\cdot \texttt{end}$\\
-$B \rightarrow S\cdot \texttt{;}$\\
-$B \rightarrow S\cdot \texttt{;} \cdot B$\\
-$S \rightarrow num$\\
-$E \rightarrow num$\\
-$B \rightarrow num$
+$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}
 
@@ -82,14 +82,37 @@
 
 \begin{center}
 \begin{tabular}{rl}
-(i)   & $S \rightarrow \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\
-(ii)  & $B \rightarrow B \cdot B$\\
-(iii) & $E \rightarrow ( \cdot E \cdot )$\\
-(iv)  & $E \rightarrow E \cdot + \cdot E$
+(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}
 
 
+\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}
+
+
+                   
 %\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!




