Binary file handouts/ho03.pdf has changed
--- a/handouts/ho03.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/handouts/ho03.tex Fri Oct 07 22:08:03 2016 +0100
@@ -184,16 +184,16 @@
The reason for introducing NFAs is that there is a relatively
simple (recursive) translation of regular expressions into
-NFAs. Consider the simple regular expressions $\varnothing$,
-$\epsilon$ and $c$. They can be translated as follows:
+NFAs. Consider the simple regular expressions $\ZERO$,
+$\ONE$ and $c$. They can be translated as follows:
\begin{center}
\begin{tabular}[t]{l@{\hspace{10mm}}l}
-\raisebox{1mm}{$\varnothing$} &
+\raisebox{1mm}{$\ZERO$} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial] (q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
-\raisebox{1mm}{$\epsilon$} &
+\raisebox{1mm}{$\ONE$} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial, accepting] (q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
@@ -548,7 +548,7 @@
system
\begin{eqnarray}
-q_0 & = & \epsilon + q_0\,b + q_1\,b + q_2\,b\\
+q_0 & = & \ONE + q_0\,b + q_1\,b + q_2\,b\\
q_1 & = & q_0\,a\\
q_2 & = & q_1\,a + q_2\,a
\end{eqnarray}
@@ -569,7 +569,7 @@
will make you stay in $q_2$. The right-hand side of the
first equation is constructed similarly: there are three
incoming edges, therefore there are three terms. There is
-one exception in that we also ``add'' $\epsilon$ to the
+one exception in that we also ``add'' $\ONE$ to the
first equation, because it corresponds to the starting state
in the DFA.
@@ -582,7 +582,7 @@
into the other two. This gives
\begin{eqnarray}
-q_0 & = & \epsilon + q_0\,b + q_0\,a\,b + q_2\,b\\
+q_0 & = & \ONE + q_0\,b + q_0\,a\,b + q_2\,b\\
q_2 & = & q_0\,a\,a + q_2\,a
\end{eqnarray}
@@ -591,7 +591,7 @@
Equation (4) to obtain the following two equations:
\begin{eqnarray}
-q_0 & = & \epsilon + q_0\,(b + a\,b) + q_2\,b\\
+q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\
q_2 & = & q_0\,a\,a + q_2\,a
\end{eqnarray}
@@ -607,7 +607,7 @@
(7) to obtain the two new equations
\begin{eqnarray}
-q_0 & = & \epsilon + q_0\,(b + a\,b) + q_2\,b\\
+q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\
q_2 & = & q_0\,a\,a\,(a^*)
\end{eqnarray}
@@ -615,26 +615,26 @@
the first in order to eliminate the variable $q_2$.
\begin{eqnarray}
-q_0 & = & \epsilon + q_0\,(b + a\,b) + q_0\,a\,a\,(a^*)\,b
+q_0 & = & \ONE + q_0\,(b + a\,b) + q_0\,a\,a\,(a^*)\,b
\end{eqnarray}
\noindent Pulling $q_0$ out as a single factor gives:
\begin{eqnarray}
-q_0 & = & \epsilon + q_0\,(b + a\,b + a\,a\,(a^*)\,b)
+q_0 & = & \ONE + q_0\,(b + a\,b + a\,a\,(a^*)\,b)
\end{eqnarray}
\noindent This equation is again of the form so that we can
apply Arden's rule ($r$ is $b + a\,b + a\,a\,(a^*)\,b$ and $s$
-is $\epsilon$). This gives as solution for $q_0$ the following
+is $\ONE$). This gives as solution for $q_0$ the following
regular expression:
\begin{eqnarray}
-q_0 & = & \epsilon\,(b + a\,b + a\,a\,(a^*)\,b)^*
+q_0 & = & \ONE\,(b + a\,b + a\,a\,(a^*)\,b)^*
\end{eqnarray}
\noindent Since this is a regular expression, we can simplify
-away the $\epsilon$ to obtain the slightly simpler regular
+away the $\ONE$ to obtain the slightly simpler regular
expression
\begin{eqnarray}
Binary file handouts/ho04.pdf has changed
--- a/handouts/ho04.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/handouts/ho04.tex Fri Oct 07 22:08:03 2016 +0100
@@ -537,7 +537,7 @@
\noindent This completes the high-level version of the simplification
function, which is shown again in Figure~\ref{simp}. The Scala code
-for the simplifaction function is in Figure~\ref{simprect}.
+for the simplification function is in Figure~\ref{simprect}.
\begin{figure}[t]
\begin{center}
Binary file hws/hw01.pdf has changed
--- a/hws/hw01.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/hws/hw01.tex Fri Oct 07 22:08:03 2016 +0100
@@ -54,10 +54,10 @@
the strings in $A$ is the empty string, for example $A =
\{[a], [b], [c], []\}$.
-\item How many basic regular expressions are there to match
- the string $abcd$? (ii) How many if they cannot include
- $\ONE$ and $\ZERO$? (iii) How many if they are also not
- allowed to contain stars? (iv) How many if they are also
+\item (1)How many basic regular expressions are there to match
+ the string $abcd$? (2) How many if they cannot include
+ $\ONE$ and $\ZERO$? (3) How many if they are also not
+ allowed to contain stars? (4) How many if they are also
not allowed to contain $\_ + \_$?
\item When are two regular expressions equivalent? Can you
@@ -68,7 +68,7 @@
$[b]$.
\item What is meant by the notions \emph{evil regular expressions}
- and \emph{catastrophic backtracking}?
+ and by \emph{catastrophic backtracking}?
\item \POSTSCRIPT
\end{enumerate}
Binary file hws/hw02.pdf has changed
--- a/hws/hw02.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/hws/hw02.tex Fri Oct 07 22:08:03 2016 +0100
@@ -104,7 +104,8 @@
\item Give a regular expression that can recognise an odd
number of $a$s or an even number of $b$s.
-
+
+\item \POSTSCRIPT
\end{enumerate}
\end{document}
Binary file hws/hw03.pdf has changed
--- a/hws/hw03.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/hws/hw03.tex Fri Oct 07 22:08:03 2016 +0100
@@ -172,6 +172,7 @@
automaton (DFA) that can recognise the same language
as the NFA maximal need?
+\item \POSTSCRIPT
\end{enumerate}
\end{document}
Binary file hws/hw04.pdf has changed
--- a/hws/hw04.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/hws/hw04.tex Fri Oct 07 22:08:03 2016 +0100
@@ -10,7 +10,7 @@
\begin{enumerate}
-\item If a regular expression $r$ does not contain any occurrence of $\varnothing$,
+\item If a regular expression $r$ does not contain any occurrence of $\ZERO$,
is it possible for $L(r)$ to be empty?
\item Define the tokens and regular expressions for a language
@@ -106,7 +106,9 @@
%\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it
%implements the \texttt{findAll} function. This function takes a regular
%expressions and a string, and returns all substrings in this string that
-%match the regular expression.
+ %match the regular expression.
+
+\item \POSTSCRIPT
\end{enumerate}
Binary file hws/hw05.pdf has changed
--- a/hws/hw05.tex Tue Oct 04 15:09:08 2016 +0100
+++ b/hws/hw05.tex Fri Oct 07 22:08:03 2016 +0100
@@ -88,7 +88,7 @@
Observe the maximal munch rule and the priorities of your regular
expressions that make the process of lexing unambiguous.)
-\item (Optional) Recall the definitions for $Der$ and $der$
+\item {\bf(Optional)} Recall the definitions for $Der$ and $der$
from the lectures. Prove by induction on $r$ the
property that
@@ -98,6 +98,7 @@
holds.
+\item \POSTSCRIPT
\end{enumerate}
\end{document}