--- a/handouts/ho03.tex Sun May 07 00:20:58 2017 +0100
+++ b/handouts/ho03.tex Sun May 07 03:01:29 2017 +0100
@@ -570,7 +570,7 @@
\end{figure}
The case for the sequence regular expression $r_1 \cdot r_2$ is a bit more
-complicated: We are given by recursion two NFAs representing the regular
+complicated: Say, we are given by recursion two NFAs representing the regular
expressions $r_1$ and $r_2$ respectively.
\begin{center}
@@ -605,10 +605,11 @@
\end{center}
\noindent The first NFA has some accepting states and the second some
-starting states. We obtain $\epsilon$NFA for $r_1\cdot r_2$ by
-connecting these accepting states with $\epsilon$-transitions to the
-starting states of the second automaton. By doing so we make them
-non-accepting like so:
+starting states. We obtain an $\epsilon$NFA for $r_1\cdot r_2$ by
+connecting the accepting states of the first NFA with
+$\epsilon$-transitions to the starting states of the second
+automaton. By doing so we make the accepting states of the first NFA
+to be non-accepting like so:
\begin{center}
\begin{tikzpicture}[node distance=3mm,
@@ -645,20 +646,37 @@
\end{tikzpicture}
\end{center}
-\noindent The case for the choice regular expression $r_1 +
-r_2$ is slightly different: We are given by recursion two
-automata representing $r_1$ and $r_2$ respectively.
+\noindent The idea behind this construction is that the start of any
+string is first recognised by the first NFA, then we silently change
+to the second NFA; the ending of the string is recognised by the
+second NFA...just like matching of a string by the regular expression
+$r_1\cdot r_2$. The Scala code for this constrction is given in
+Figure~\ref{thompson2} in Lines 16--23. The starting states of the
+$\epsilon$NFA are the starting states of the first NFA (corresponding
+to $r_1$); the accepting function is the accepting function of the
+second NFA (corresponding to $r_2$). The new transition function is
+all the ``old'' transitions plus the $\epsilon$-transitions connecting
+the accepting states of the first NFA to the starting states of the
+first NFA (Lines 18 and 19). The $\epsilon$NFA is then immedately
+translated in a NFA.
+
+
+The case for the choice regular expression $r_1 + r_2$ is slightly
+different: We are given by recursion two NFAs representing $r_1$ and
+$r_2$ respectively.
\begin{center}
\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node at (0,0) (1) {$\mbox{}$};
-\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$};
-\node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};
+\node (2) [above=10mm of 1] {};
+\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
+\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
-\node (a) [right=of 2] {$\ldots$};
-\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
+\node (a) [right=of 2] {$\ldots\,$};
+\node (a1) [right=of a] {$$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
@@ -675,21 +693,24 @@
\end{tikzpicture}
\end{center}
-\noindent Each automaton has a single start state and
-potentially several accepting states. We obtain a NFA for the
-regular expression $r_1 + r_2$ by introducing a new starting
-state and connecting it with an $\epsilon$-transition to the
-two starting states above, like so
+\noindent Each NFA has some starting states and some accepting
+states. We obtain a NFA for the regular expression $r_1 + r_2$
+by composing the transition functions (this crucially depends
+on knowing that the states of each component NFA are distinct);
+and also combine the starting states and accepting functions:
\begin{center}
-\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
- >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
-\node at (0,0) [state, initial] (1) {$\mbox{}$};
-\node[state] (2) [above right=16mm of 1] {$\mbox{}$};
-\node[state] (3) [below right=16mm of 1] {$\mbox{}$};
+\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\node at (0,0) (1) {$\mbox{}$};
+\node (2) [above=10mm of 1] {$$};
+\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
+\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
-\node (a) [right=of 2] {$\ldots$};
-\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
+\node (a) [right=of 2] {$\ldots\,$};
+\node (a1) [right=of a] {$$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
@@ -698,8 +719,8 @@
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
-\path[->] (1) edge node [above] {$\epsilon$} (2);
-\path[->] (1) edge node [below] {$\epsilon$} (3);
+%\path[->] (1) edge node [above] {$\epsilon$} (2);
+%\path[->] (1) edge node [below] {$\epsilon$} (3);
\begin{pgfonlayer}{background}
\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};
@@ -708,8 +729,8 @@
\end{tikzpicture}
\end{center}
-\noindent
-Finally for the $*$-case we have an automaton for $r$
+\noindent The code for this construction is in Figure~\ref{thompson2}
+in Lines 25--33. Finally for the $*$-case we have a NFA for $r$
\begin{center}
\begin{tikzpicture}[node distance=3mm,
@@ -727,14 +748,16 @@
\end{tikzpicture}
\end{center}
-\noindent and connect its accepting states to a new starting
-state via $\epsilon$-transitions. This new starting state is
-also an accepting state, because $r^*$ can recognise the
-empty string. This gives the following automaton for $r^*$:
+\noindent and connect its accepting states to a new starting state via
+$\epsilon$-transitions. This new starting state is also an accepting
+state, because $r^*$ can recognise the empty string. This gives the
+following $\epsilon$NFA for $r^*$ (the corresponding code is in
+Figure~\ref{thompson2} in Lines 35--43:
\begin{center}
\begin{tikzpicture}[node distance=3mm,
- >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};
\node[state] (2) [right=16mm of 1] {$\mbox{}$};
\node (a) [right=of 2] {$\ldots$};
@@ -752,6 +775,15 @@
\end{tikzpicture}
\end{center}
+
+To sum ap, you can see in the sequence and star cases the need of
+having silent $\epsilon$-transitions. Similarly the alternative case
+shows the need of the NFA-nondeterminsim. It seems awkward to form the
+`alternative' composition of two DFAs, because DFA do not allow
+several starting and successor states. All these constructions can now
+be put together in the following recursive function:
+
+
{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
{\ifodd\value{lstnumber}\color{capri!3}\fi}]
def thompson (r: Rexp) : NFAt = r match {
@@ -764,11 +796,55 @@
}
\end{lstlisting}}
+\noindent
+It calculates a NFA from a regular expressions. At last we can run a
+NFA for the our evil regular expression examples.
+
\begin{center}
\begin{tabular}{@{\hspace{-1mm}}c@{\hspace{1mm}}c@{}}
\begin{tikzpicture}
\begin{axis}[
+ title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
+ $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4.5cm,
+ legend entries={Python,Ruby},
+ legend pos=south east,
+ legend cell align=left]
+ \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+ \addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
+ % breath-first search in NFAs
+ \addplot[red,mark=*, mark options={fill=white}] table {
+ 1 0.00586
+ 2 0.01209
+ 3 0.03076
+ 4 0.08269
+ 5 0.12881
+ 6 0.25146
+ 7 0.51377
+ 8 0.89079
+ 9 1.62802
+ 10 3.05326
+ 11 5.92437
+ 12 11.67863
+ 13 24.00568
+ };
+\end{axis}
+\end{tikzpicture}
+&
+\begin{tikzpicture}
+\begin{axis}[
title={Graph: $\texttt{(a*)*\,b}$ and strings
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
xlabel={$n$},
@@ -800,50 +876,10 @@
};
\end{axis}
\end{tikzpicture}
-&
-\begin{tikzpicture}
-\begin{axis}[
- title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
- $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
- xlabel={$n$},
- x label style={at={(1.05,0.0)}},
- ylabel={time in secs},
- enlargelimits=false,
- xtick={0,5,...,30},
- xmax=33,
- ymax=35,
- ytick={0,5,...,30},
- scaled ticks=false,
- axis lines=left,
- width=5.5cm,
- height=4.5cm,
- legend entries={Python,Ruby},
- legend pos=south east,
- legend cell align=left]
- \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
- \addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
- % breath-first search in NFAs
- \addplot[red,mark=*, mark options={fill=white}] table {
- 1 0.00741
- 2 0.02657
- 3 0.08317
- 4 0.22133
- 5 0.54463
- 6 1.42062
- 7 4.04926
- 8 12.70395
- 9 39.21555
- 10 112.05466
- };
-\end{axis}
-\end{tikzpicture}
\end{tabular}
\end{center}
-\noindent This construction of a NFA from a regular expression
-was invented by Ken Thompson in 1968.
-
\subsubsection*{Subset Construction}