updated
authorChristian Urban <christian.urban@kcl.ac.uk>
Mon, 29 Jun 2020 21:13:49 +0100
changeset 726 fba480bbc9f7
parent 725 f345e89895f5
child 727 eb9343126625
updated
hws/hw01.tex
hws/hw04.tex
hws/hw06.tex
hws/hw08.tex
--- a/hws/hw01.tex	Mon Jun 29 21:05:34 2020 +0100
+++ b/hws/hw01.tex	Mon Jun 29 21:13:49 2020 +0100
@@ -79,7 +79,19 @@
       $[b]$.
 
 \item What is meant by the notions \emph{evil regular expressions}
-      and by \emph{catastrophic backtracking}? 
+  and by \emph{catastrophic backtracking}?
+
+\item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$,
+  which of the following regular expressions are equyivalent
+
+\begin{center}
+\begin{tabular}{ll}    
+  1) & $(ab + bb)^* \cdot (a + b)^*$\\                     % no
+  2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\   % yes
+  3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$           % no
+\end{tabular}
+\end{center}
+  
 
 \item \POSTSCRIPT  
 \end{enumerate}
--- a/hws/hw04.tex	Mon Jun 29 21:05:34 2020 +0100
+++ b/hws/hw04.tex	Mon Jun 29 21:13:49 2020 +0100
@@ -10,6 +10,20 @@
 
 \begin{enumerate}
 
+\item Given the regular expressions
+
+\begin{center}
+\begin{tabular}{ll}    
+  1) & $(ab + a)\cdot (\ONE + b)$\\
+  2) & $(aa + a)^*$\\
+\end{tabular}
+\end{center}
+
+there are several values for how these regular expressions can
+recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case
+\emph{all} the values and indicate which one is the POSIX value.
+  
+
 \item If a regular expression $r$ does not contain any occurrence of $\ZERO$,  
 is it possible for $L(r)$ to be empty? Explain why, or give a proof.
 
--- a/hws/hw06.tex	Mon Jun 29 21:05:34 2020 +0100
+++ b/hws/hw06.tex	Mon Jun 29 21:13:49 2020 +0100
@@ -57,34 +57,19 @@
 and (ii) give a sample string involving all rules given in 1.-4.~that 
 can be parsed by this grammar.
 
-\item Given the regular expressions
 
-\begin{center}
-\begin{tabular}{ll}    
-  1) & $(ab + a)\cdot (\ONE + b)$\\
-  2) & $(aa + a)^*$\\
-\end{tabular}
-\end{center}
-
-there are several values for how these regular expressions can
-recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case
-\emph{all} the values and indicate which one is the POSIX value.
-
-\item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$,
-  which of the following regular expressions are equyivalent
-
-\begin{center}
-\begin{tabular}{ll}    
-  1) & $(ab + bb)^* \cdot (a + b)^*$\\                     % no
-  2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\   % yes
-  3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$           % no
-\end{tabular}
-\end{center}
 
 \item Parsing combinators consist of atomic parsers, alternative
   parsers, sequence parsers and semantic actions.  What is the purpose
   of (1) atomic parsers and of (2) semantic actions?
 
+\item Parser combinators can directly be given a string as
+      input, without the need of a lexer. What are the
+      advantages to first lex a string and then feed a
+      sequence of tokens as input to the parser?
+
+
+  
 \item \POSTSCRIPT        
 \end{enumerate}
 
--- a/hws/hw08.tex	Mon Jun 29 21:05:34 2020 +0100
+++ b/hws/hw08.tex	Mon Jun 29 21:13:49 2020 +0100
@@ -18,10 +18,6 @@
 \item What is the main difference between the Java assembler
       (as processed by Jasmin) and Java Byte Code?
 
-\item Parser combinators can directly be given a string as
-      input, without the need of a lexer. What are the
-      advantages to first lex a string and then feed a
-      sequence of tokens as input to the parser?
 
 \item Explain what is meant by the terms lazy evaluation and eager
   evaluation.