handouts/ho03.tex
changeset 444 3056a4c071b0
parent 349 434891622131
child 459 780486571e38
--- 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}