afl-material: comparison handouts/ho03.tex

equal deleted inserted replaced

-:cd43d8c6eb84
+:3056a4c071b0
 \subsubsection*{Thompson Construction}
 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$,
+NFAs. Consider the simple regular expressions $\ZERO$,
-$\epsilon$ and $c$. They can be translated as follows:
+$\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}\\\\
 \raisebox{2mm}{$c$} &
 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
 \noindent for which we can set up the following equational
 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}
 \noindent There is an equation for each node in the DFA. Let
 that if in state $q_1$ consuming an $a$ will bring you to
 $q_2$, and the secont that being in $q_2$ and consuming an $a$
 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.
 Having constructed the equational system, the question is
 how to solve it? Remarkably the rules are very similar to
 right-hand side of the equation. We can therefore eliminate
 $q_1$ from the system by just substituting this equation
 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}
 \noindent where in Equation (4) we have two occurences
 of $q_0$. Like the laws about $+$ and $\cdot$, we can simplify
 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}
 \noindent Unfortunately we cannot make any more progress with
 substituting equations, because both (6) and (7) contain the
 assume $+$ is symmetric, Equation (7) is of that form: $s$ is
 $q_0\,a\,a$ and $r$ is $a$. That means we can transform
 (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}
 \noindent Now again we can substitute the second equation into
 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}
 q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*
 \end{eqnarray}

changeset 444	3056a4c071b0
parent 349	434891622131
child 459	780486571e38