--- a/handouts/ho03.tex Thu Mar 23 14:49:26 2017 +0000
+++ b/handouts/ho03.tex Mon Apr 03 01:10:54 2017 +0800
@@ -13,7 +13,7 @@
\begin{document}
\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}
-\section*{Handout 3 (Automata)}
+\section*{Handout 3 (Finite Automata)}
Every formal language and compiler course I know of bombards you first
with automata and then to a much, much smaller extend with regular
@@ -24,70 +24,74 @@
recently. Still let us in this lecture have a closer look at automata
and their relation to regular expressions. This will help us with
understanding why the regular expression matchers in Python, Ruby and
-Java are so slow with certain regular expressions. The central
-definition is:\medskip
+Java are so slow with certain regular expressions.
+
+
+\subsection*{Deterministic Finite Automata}
+
+Their definition is as follows:\medskip
\noindent
A \emph{deterministic finite automaton} (DFA), say $A$, is
-given by a four-tuple written $A(Q, q_0, F, \delta)$ where
+given by a four-tuple written $A(Qs, Q_0, F, \delta)$ where
\begin{itemize}
-\item $Q$ is a finite set of states,
-\item $q_0 \in Q$ is the start state,
-\item $F \subseteq Q$ are the accepting states, and
+\item $Qs$ is a finite set of states,
+\item $Q_0 \in Qs$ is the start state,
+\item $F \subseteq Qs$ are the accepting states, and
\item $\delta$ is the transition function.
\end{itemize}
-\noindent The transition function determines how to
-``transition'' from one state to the next state with respect
-to a character. We have the assumption that these transition
-functions do not need to be defined everywhere: so it can be
-the case that given a character there is no next state, in
-which case we need to raise a kind of ``failure exception''. A
-typical example of a DFA is
+\noindent The transition function determines how to ``transition''
+from one state to the next state with respect to a character. We have
+the assumption that these transition functions do not need to be
+defined everywhere: so it can be the case that given a character there
+is no next state, in which case we need to raise a kind of ``failure
+exception''. That means actually we have partial functions as
+transitions---see our implementation later on. A typical example of a
+DFA is
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,
inner sep=2pt,draw=blue!50,very thick,
fill=blue!20},scale=2]
-\node[state,initial] (q_0) {$q_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
-\path[->] (q_0) edge node [above] {$a$} (q_1);
-\path[->] (q_1) edge node [above] {$a$} (q_4);
-\path[->] (q_4) edge [loop right] node {$a, b$} ();
-\path[->] (q_3) edge node [right] {$a$} (q_4);
-\path[->] (q_2) edge node [above] {$a$} (q_3);
-\path[->] (q_1) edge node [right] {$b$} (q_2);
-\path[->] (q_0) edge node [above] {$b$} (q_2);
-\path[->] (q_2) edge [loop left] node {$b$} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {$b$} (q_0);
+\node[state,initial] (Q_0) {$Q_0$};
+\node[state] (Q_1) [right=of Q_0] {$Q_1$};
+\node[state] (Q_2) [below right=of Q_0] {$Q_2$};
+\node[state] (Q_3) [right=of Q_2] {$Q_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$};
+\path[->] (Q_0) edge node [above] {$a$} (Q_1);
+\path[->] (Q_1) edge node [above] {$a$} (Q_4);
+\path[->] (Q_4) edge [loop right] node {$a, b$} ();
+\path[->] (Q_3) edge node [right] {$a$} (Q_4);
+\path[->] (Q_2) edge node [above] {$a$} (Q_3);
+\path[->] (Q_1) edge node [right] {$b$} (Q_2);
+\path[->] (Q_0) edge node [above] {$b$} (Q_2);
+\path[->] (Q_2) edge [loop left] node {$b$} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {$b$} (Q_0);
\end{tikzpicture}
\end{center}
-\noindent In this graphical notation, the accepting state
-$q_4$ is indicated with double circles. Note that there can be
-more than one accepting state. It is also possible that a DFA
-has no accepting states at all, or that the starting state is
-also an accepting state. In the case above the transition
-function is defined everywhere and can be given as a table as
-follows:
+\noindent In this graphical notation, the accepting state $Q_4$ is
+indicated with double circles. Note that there can be more than one
+accepting state. It is also possible that a DFA has no accepting
+states at all, or that the starting state is also an accepting
+state. In the case above the transition function is defined everywhere
+and can also be given as a table as follows:
\[
\begin{array}{lcl}
-(q_0, a) &\rightarrow& q_1\\
-(q_0, b) &\rightarrow& q_2\\
-(q_1, a) &\rightarrow& q_4\\
-(q_1, b) &\rightarrow& q_2\\
-(q_2, a) &\rightarrow& q_3\\
-(q_2, b) &\rightarrow& q_2\\
-(q_3, a) &\rightarrow& q_4\\
-(q_3, b) &\rightarrow& q_0\\
-(q_4, a) &\rightarrow& q_4\\
-(q_4, b) &\rightarrow& q_4\\
+(Q_0, a) &\rightarrow& Q_1\\
+(Q_0, b) &\rightarrow& Q_2\\
+(Q_1, a) &\rightarrow& Q_4\\
+(Q_1, b) &\rightarrow& Q_2\\
+(Q_2, a) &\rightarrow& Q_3\\
+(Q_2, b) &\rightarrow& Q_2\\
+(Q_3, a) &\rightarrow& Q_4\\
+(Q_3, b) &\rightarrow& Q_0\\
+(Q_4, a) &\rightarrow& Q_4\\
+(Q_4, b) &\rightarrow& Q_4\\
\end{array}
\]
@@ -110,12 +114,12 @@
automaton. Otherwise it is not accepted. This also means that if along
the way we hit the case where the transition function $\delta$ is not
defined, we need to raise an error. In our implementation we will deal
-with this case elegantly by using Scala's \texttt{Try}. So $s$ is in
-the \emph{language accepted by the automaton} $A(Q, q_0, F, \delta)$
-iff
+with this case elegantly by using Scala's \texttt{Try}. So a string
+$s$ is in the \emph{language accepted by the automaton} $A(Q, Q_0, F,
+\delta)$ iff
\[
-\hat{\delta}(q_0, s) \in F
+\hat{\delta}(Q_0, s) \in F
\]
\noindent I let you think about a definition that describes
@@ -126,27 +130,31 @@
\lstinputlisting[numbers=left,linebackgroundcolor=
{\ifodd\value{lstnumber}\color{capri!3}\fi}]
{../progs/dfa.scala}
-\caption{Scala implementation of DFAs using partial functions.
+\caption{A Scala implementation of DFAs using partial functions.
Notice some subtleties: \texttt{deltas} implements the delta-hat
construction by lifting the transition (partial) function to
lists of \texttt{C}haracters. Since \texttt{delta} is given
as partial function, it can obviously go ``wrong'' in which
case the \texttt{Try} in \texttt{accepts} catches the error and
- returns \texttt{false}, that is the string is not accepted.
- The example implements the DFA example shown above.\label{dfa}}
+ returns \texttt{false}---that means the string is not accepted.
+ The example \texttt{delta} implements the DFA example shown
+ earlier in the handout.\label{dfa}}
\end{figure}
-A simple Scala implementation of DFAs is given in Figure~\ref{dfa}. As
-you can see, there many features of the mathematical definition that
-are quite closely reflected in the code. In the DFA-class, there is a
-starting state, called \texttt{start}, with the polymorphic type
-\texttt{A}. There is a partial function \texttt{delta} for specifying
-the transitions. I used partial functions for transitions in Scala;
-alternatives would have been \texttt{Maps} or even \texttt{Lists}. One
-of the main advantages of using partial functions is that transitions
-can be quite nicely defined by a series of \texttt{case} statements
-(see Lines 28 -- 38). If you need to represent an automaton
-with a sink state (catch-all-state), you can write something like
+A simple Scala implementation for DFAs is given in
+Figure~\ref{dfa}. As you can see, there many features of the
+mathematical definition that are quite closely reflected in the
+code. In the DFA-class, there is a starting state, called
+\texttt{start}, with the polymorphic type \texttt{A}. (The reason for
+having a polymorphic types for the states and the input of DFAs will
+become clearer later.) There is a partial function \texttt{delta} for
+specifying the transitions. I used partial functions for representing
+the transitions in Scala; alternatives would have been \texttt{Maps}
+or even \texttt{Lists}. One of the main advantages of using partial
+functions is that transitions can be quite nicely defined by a series
+of \texttt{case} statements (see Lines 28 -- 38). If you need to
+represent an automaton with a sink state (catch-all-state), you can
+write something like
{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
{\ifodd\value{lstnumber}\color{capri!3}\fi}]
@@ -161,80 +169,122 @@
}
\end{lstlisting}}
-\noindent The DFA-class has also an argument for final states. It is a
-function from states to booleans (returns true whenever a state is
-meant to be finbal; false otherwise). While this is a boolean
-function, Scala allows me to use sets of states for such functions
-(see Line 40 where I initialise the DFA).
+\noindent The DFA-class has also an argument for specifying final
+states. In the implementation it is a function from states to booleans
+(returns true whenever a state is meant to be final; false
+otherwise). While this boolean function is different from the sets of
+states used in the mathematical definition, Scala allows me to use
+sets for such functions (see Line 40 where I initialise the DFA).
I let you ponder whether this is a good implementation of DFAs. In
-doing so I hope you notice that the $Q$ component (the set of finite
+doing so I hope you notice that the $Qs$ component (the set of finite
states) is missing from the class definition. This means that the
implementation allows you to do some fishy things you are not meant to
do with DFAs. Which fishy things could that be?
-While with DFAs it will always be clear that given a character what
-the next state is (potentially none), it will be useful to relax this
-restriction. That means we have several potential successor states. We
-even allow more than one starting state. The resulting construction is
-called a \emph{non-deterministic finite automaton} (NFA) given also as
-a four-tuple $A(Q, Q_{0s}, F, \rho)$ where
+
+
+\subsection*{Non-Deterministic Finite Automata}
+
+While with DFAs it will always be clear that given a state and a
+character what the next state is (potentially none), it will be useful
+to relax this restriction. That means we allow to have several
+potential successor states. We even allow more than one starting
+state. The resulting construction is called a \emph{non-deterministic
+ finite automaton} (NFA) given also as a four-tuple $A(Qs, Q_{0s}, F,
+\rho)$ where
\begin{itemize}
-\item $Q$ is a finite set of states
-\item $Q_{0s}$ are the start states ($Q_{0s} \subseteq Q$)
-\item $F$ are some accepting states with $F \subseteq Q$, and
+\item $Qs$ is a finite set of states
+\item $Q_{0s}$ is a set of start states ($Q_{0s} \subseteq Qs$)
+\item $F$ are some accepting states with $F \subseteq Qs$, and
\item $\rho$ is a transition relation.
\end{itemize}
\noindent
-Two typical examples of NFAs are
+A typical example of an NFA is
+
+% A NFA for (ab* + b)*a
\begin{center}
-\begin{tabular}[t]{c@{\hspace{9mm}}c}
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
- every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial] (q_0) {$q_0$};
-\node[state] (q_1) [above=of q_0] {$q_1$};
-\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
-\path[->] (q_0) edge node [left] {$\epsilon$} (q_1);
-\path[->] (q_0) edge node [left] {$\epsilon$} (q_2);
-\path[->] (q_0) edge [loop right] node {$a$} ();
-\path[->] (q_1) edge [loop above] node {$a$} ();
-\path[->] (q_2) edge [loop below] node {$b$} ();
-\end{tikzpicture} &
-
-\raisebox{20mm}{
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
- every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial] (r_1) {$r_1$};
-\node[state] (r_2) [above=of r_1] {$r_2$};
-\node[state, accepting] (r_3) [right=of r_1] {$r_3$};
-\path[->] (r_1) edge node [below] {$b$} (r_3);
-\path[->] (r_2) edge [bend left] node [above] {$a$} (r_3);
-\path[->] (r_1) edge [bend left] node [left] {$\epsilon$} (r_2);
-\path[->] (r_2) edge [bend left] node [right] {$a$} (r_1);
-\end{tikzpicture}}
-\end{tabular}
+\begin{tikzpicture}[scale=0.8,>=stealth',very thick,
+every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial] (Q_0) {$Q_0$};
+\node[state] (Q_1) [right=of Q_0] {$Q_1$};
+\node[state, accepting] (Q_2) [right=of Q_1] {$Q_2$};
+\path[->] (Q_0) edge [loop above] node {$b$} ();
+\path[<-] (Q_0) edge node [below] {$b$} (Q_1);
+\path[->] (Q_0) edge [bend left] node [above] {$a$} (Q_1);
+\path[->] (Q_0) edge [bend right] node [below] {$a$} (Q_2);
+\path[->] (Q_1) edge [loop above] node {$a,b$} ();
+\path[->] (Q_1) edge node [above] {$a$} (Q_2);
+\end{tikzpicture}
\end{center}
-\noindent There are, however, a number of points you should
-note. Every DFA is a NFA, but not vice versa. The $\rho$ in
-NFAs is a transition \emph{relation} (DFAs have a transition
-function). The difference between a function and a relation is
-that a function has always a single output, while a relation
-gives, roughly speaking, several outputs. Look at the NFA on
-the right-hand side above: if you are currently in the state
-$r_2$ and you read a character $a$, then you can transition to
-either $r_1$ \emph{or} $r_3$. Which route you take is not
-determined. This means if we need to decide whether a string
-is accepted by a NFA, we might have to explore all
-possibilities. Also there is the special silent transition in
-NFAs. As mentioned already this transition means you do not
-have to ``consume'' any part of the input string, but
-``silently'' change to a different state. In the left picture,
-for example, if you are in the starting state, you can
-silently move either to $q_1$ or $q_2$. This silent
-transition is also often called \emph{$\epsilon$-transition}.
+\noindent
+This NFA happens to have only one starting state, but in general there
+could be more. Notice that in state $Q_0$ we might go to state $Q_1$
+\emph{or} to state $Q_2$ when receiving an $a$. Similarly in state $Q_1$
+and receiving an $a$, we can stay in state $Q_1$ or go to $Q_2$. This
+kind of choice is not allowed with DFAs. When it comes to deciding
+whether a string is accepted by an NFA we potentially need to explore
+all possibilities. I let you think which kind of strings this NFA
+accepts.
+
+
+There are however a number of additional points you should note. Every
+DFA is a NFA, but not vice versa. The $\rho$ in NFAs is a transition
+\emph{relation} (DFAs have a transition function). The difference
+between a function and a relation is that a function has always a
+single output, while a relation gives, roughly speaking, several
+outputs. Look again at the NFA above: if you are currently in the
+state $Q_1$ and you read a character $b$, then you can transition to
+either $Q_0$ \emph{or} $Q_2$. Which route, or output, you take is not
+determined. This non-determinism can be represented by a relation.
+
+My implementation of NFAs is shown in Figure~\ref{nfa}. Perhaps
+interestingly, I do not use relations for my implementation of NFAs in
+Scala, and I also do not use transition functions which return a set
+of states (another popular choice for implementing NFAs). For reasons
+that become clear in a moment, I use sets of partial functions---see
+Line 7 in Figure~\ref{nfa}. \texttt{Starts} is now a set of states;
+\texttt{fins} is again a function from states to booleans. The
+\texttt{next} function calculates the set of next states reachable
+from a state \texttt{q} by a character \texttt{c}---we go through all
+partial functions in the \texttt{delta}-set, lift it (this transformes
+the partial function into the corresponding \texttt{Option}-function
+and then apply \texttt{q} and \texttt{c}. This gives us a set of
+\texttt{Some}s and \texttt{None}s, where the \texttt{Some}s are
+filtered out by the \texttt{flatMap}. Teh function \texttt{nexts} just
+lifts this to sets of states. \texttt{Deltas} and \texttt{accept} are
+similar to the DFA definitions.
+
+\begin{figure}[t]
+\small
+\lstinputlisting[numbers=left,linebackgroundcolor=
+ {\ifodd\value{lstnumber}\color{capri!3}\fi}]
+ {../progs/nfa.scala}
+\caption{A Scala implementation of NFAs using sets of partial functions.
+ Notice some subtleties: \texttt{deltas} implements the delta-hat
+ construction by lifting the transition (partial) function to
+ lists of \texttt{C}haracters. Since \texttt{delta} is given
+ as partial function, it can obviously go ``wrong'' in which
+ case the \texttt{Try} in \texttt{accepts} catches the error and
+ returns \texttt{false}---that means the string is not accepted.
+ The example \texttt{delta} implements the DFA example shown
+ earlier in the handout.\label{nfa}}
+\end{figure}
+
+
+
+%This means if
+%we need to decide whether a string is accepted by a NFA, we might have
+%to explore all possibilities. Also there is the special silent
+%transition in NFAs. As mentioned already this transition means you do
+%not have to ``consume'' any part of the input string, but ``silently''
+%change to a different state. In the left picture, for example, if you
+%are in the starting state, you can silently move either to $Q_1$ or
+%%$Q_2$. This silent transition is also often called
+%\emph{$\epsilon$-transition}.
\subsubsection*{Thompson Construction}
@@ -248,17 +298,17 @@
\begin{tabular}[t]{l@{\hspace{10mm}}l}
\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{}$};
+\node[state, initial] (Q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
\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{}$};
+\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},]
-\node[state, initial] (q_0) {$\mbox{}$};
-\node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$};
-\path[->] (q_0) edge node [below] {$c$} (q_1);
+\node[state, initial] (Q_0) {$\mbox{}$};
+\node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$};
+\path[->] (Q_0) edge node [below] {$c$} (Q_1);
\end{tikzpicture}\\\\
\end{tabular}
\end{center}
@@ -270,8 +320,8 @@
\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[state, initial] (q_0) {$\mbox{}$};
-\node (r_1) [right=of q_0] {$\ldots$};
+\node[state, initial] (Q_0) {$\mbox{}$};
+\node (r_1) [right=of Q_0] {$\ldots$};
\node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$};
\node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$};
\node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$};
@@ -281,7 +331,7 @@
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
\begin{pgfonlayer}{background}
-\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};
+\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (Q_0) (r_1) (t_1) (t_2) (t_3)] {};
\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};
\node [yshift=2mm] at (1.north) {$r_1$};
\node [yshift=2mm] at (2.north) {$r_2$};
@@ -298,8 +348,8 @@
\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[state, initial] (q_0) {$\mbox{}$};
-\node (r_1) [right=of q_0] {$\ldots$};
+\node[state, initial] (Q_0) {$\mbox{}$};
+\node (r_1) [right=of Q_0] {$\ldots$};
\node[state] (t_1) [right=of r_1] {$\mbox{}$};
\node[state] (t_2) [above=of t_1] {$\mbox{}$};
\node[state] (t_3) [below=of t_1] {$\mbox{}$};
@@ -313,7 +363,7 @@
\path[->] (t_3) edge node [below] {$\epsilon$} (a_0);
\begin{pgfonlayer}{background}
-\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};
+\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (Q_0) (c_1) (c_2) (c_3)] {};
\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
\end{pgfonlayer}
\end{tikzpicture}
@@ -442,14 +492,14 @@
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20},
baseline=0mm]
-\node[state,initial] (q_0) {$0$};
-\node[state] (q_1) [above=of q_0] {$1$};
-\node[state, accepting] (q_2) [below=of q_0] {$2$};
-\path[->] (q_0) edge node [left] {$\epsilon$} (q_1);
-\path[->] (q_0) edge node [left] {$\epsilon$} (q_2);
-\path[->] (q_0) edge [loop right] node {$a$} ();
-\path[->] (q_1) edge [loop above] node {$a$} ();
-\path[->] (q_2) edge [loop below] node {$b$} ();
+\node[state,initial] (Q_0) {$0$};
+\node[state] (Q_1) [above=of Q_0] {$1$};
+\node[state, accepting] (Q_2) [below=of Q_0] {$2$};
+\path[->] (Q_0) edge node [left] {$\epsilon$} (Q_1);
+\path[->] (Q_0) edge node [left] {$\epsilon$} (Q_2);
+\path[->] (Q_0) edge [loop right] node {$a$} ();
+\path[->] (Q_1) edge [loop above] node {$a$} ();
+\path[->] (Q_2) edge [loop below] node {$b$} ();
\end{tikzpicture}
&
\begin{tabular}{r|cl}
@@ -589,9 +639,9 @@
every state/.style={minimum size=0pt,
inner sep=2pt,draw=blue!50,very thick,
fill=blue!20}]
- \node[state, initial] (q0) at ( 0,1) {$q_0$};
- \node[state] (q1) at ( 1,1) {$q_1$};
- \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+ \node[state, initial] (q0) at ( 0,1) {$Q_0$};
+ \node[state] (q1) at ( 1,1) {$Q_1$};
+ \node[state, accepting] (q2) at ( 2,1) {$Q_2$};
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
(q1) edge[bend left] node[above] {$b$} (q0)
(q2) edge[bend left=50] node[below] {$b$} (q0)
@@ -605,25 +655,25 @@
system
\begin{eqnarray}
-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
+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
us have a look how the right-hand sides of the equations are
constructed. First have a look at the second equation: the
-left-hand side is $q_1$ and the right-hand side $q_0\,a$. The
+left-hand side is $Q_1$ and the right-hand side $Q_0\,a$. The
right-hand side is essentially all possible ways how to end up
-in node $q_1$. There is only one incoming edge from $q_0$ consuming
+in node $Q_1$. There is only one incoming edge from $Q_0$ consuming
an $a$. Therefore the right hand side is this
-state followed by character---in this case $q_0\,a$. Now lets
+state followed by character---in this case $Q_0\,a$. Now lets
have a look at the third equation: there are two incoming
-edges for $q_2$. Therefore we have two terms, namely $q_1\,a$ and
-$q_2\,a$. These terms are separated by $+$. The first states
-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
+edges for $Q_2$. Therefore we have two terms, namely $Q_1\,a$ and
+$Q_2\,a$. These terms are separated by $+$. The first states
+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'' $\ONE$ to the
@@ -633,23 +683,23 @@
Having constructed the equational system, the question is
how to solve it? Remarkably the rules are very similar to
solving usual linear equational systems. For example the
-second equation does not contain the variable $q_1$ on the
+second equation does not contain the variable $Q_1$ on the
right-hand side of the equation. We can therefore eliminate
-$q_1$ from the system by just substituting this equation
+$Q_1$ from the system by just substituting this equation
into the other two. This gives
\begin{eqnarray}
-q_0 & = & \ONE + q_0\,b + q_0\,a\,b + q_2\,b\\
-q_2 & = & q_0\,a\,a + q_2\,a
+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
+of $Q_0$. Like the laws about $+$ and $\cdot$, we can simplify
Equation (4) to obtain the following two equations:
\begin{eqnarray}
-q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\
-q_2 & = & q_0\,a\,a + q_2\,a
+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
@@ -660,34 +710,34 @@
It states that if an equation is of the form $q = q\,r + s$
then it can be transformed to $q = s\, r^*$. Since we can
assume $+$ is symmetric, Equation (7) is of that form: $s$ is
-$q_0\,a\,a$ and $r$ is $a$. That means we can transform
+$Q_0\,a\,a$ and $r$ is $a$. That means we can transform
(7) to obtain the two new equations
\begin{eqnarray}
-q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\
-q_2 & = & q_0\,a\,a\,(a^*)
+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$.
+the first in order to eliminate the variable $Q_2$.
\begin{eqnarray}
-q_0 & = & \ONE + 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:
+\noindent Pulling $Q_0$ out as a single factor gives:
\begin{eqnarray}
-q_0 & = & \ONE + 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 $\ONE$). 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 & = & \ONE\,(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
@@ -695,7 +745,7 @@
expression
\begin{eqnarray}
-q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*
+Q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*
\end{eqnarray}
\noindent
@@ -703,14 +753,14 @@
for the other equations. This gives:
\begin{eqnarray}
-q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\\
-q_1 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\\
-q_2 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^*
+Q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\\
+Q_1 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\\
+Q_2 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^*
\end{eqnarray}
\noindent Finally, we only need to ``add'' up the equations
which correspond to a terminal state. In our running example,
-this is just $q_2$. Consequently, a regular expression
+this is just $Q_2$. Consequently, a regular expression
that recognises the same language as the automaton is
\[
@@ -757,21 +807,21 @@
every state/.style={minimum size=0pt,
inner sep=2pt,draw=blue!50,very thick,
fill=blue!20}]
-\node[state,initial] (q_0) {$q_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
-\path[->] (q_0) edge node [above] {$a$} (q_1);
-\path[->] (q_1) edge node [above] {$a$} (q_4);
-\path[->] (q_4) edge [loop right] node {$a, b$} ();
-\path[->] (q_3) edge node [right] {$a$} (q_4);
-\path[->] (q_2) edge node [above] {$a$} (q_3);
-\path[->] (q_1) edge node [right] {$b$} (q_2);
-\path[->] (q_0) edge node [above] {$b$} (q_2);
-\path[->] (q_2) edge [loop left] node {$b$} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node
- [below] {$b$} (q_0);
+\node[state,initial] (Q_0) {$Q_0$};
+\node[state] (Q_1) [right=of Q_0] {$Q_1$};
+\node[state] (Q_2) [below right=of Q_0] {$Q_2$};
+\node[state] (Q_3) [right=of Q_2] {$Q_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$};
+\path[->] (Q_0) edge node [above] {$a$} (Q_1);
+\path[->] (Q_1) edge node [above] {$a$} (Q_4);
+\path[->] (Q_4) edge [loop right] node {$a, b$} ();
+\path[->] (Q_3) edge node [right] {$a$} (Q_4);
+\path[->] (Q_2) edge node [above] {$a$} (Q_3);
+\path[->] (Q_1) edge node [right] {$b$} (Q_2);
+\path[->] (Q_0) edge node [above] {$b$} (Q_2);
+\path[->] (Q_2) edge [loop left] node {$b$} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node
+ [below] {$b$} (Q_0);
\end{tikzpicture}
\end{center}
@@ -792,15 +842,15 @@
\draw (3,0) -- (3, 2);
\draw (4,0) -- (4, 1);
-\draw (0.5,-0.5) node {$q_0$};
-\draw (1.5,-0.5) node {$q_1$};
-\draw (2.5,-0.5) node {$q_2$};
-\draw (3.5,-0.5) node {$q_3$};
+\draw (0.5,-0.5) node {$Q_0$};
+\draw (1.5,-0.5) node {$Q_1$};
+\draw (2.5,-0.5) node {$Q_2$};
+\draw (3.5,-0.5) node {$Q_3$};
-\draw (-0.5, 3.5) node {$q_1$};
-\draw (-0.5, 2.5) node {$q_2$};
-\draw (-0.5, 1.5) node {$q_3$};
-\draw (-0.5, 0.5) node {$q_4$};
+\draw (-0.5, 3.5) node {$Q_1$};
+\draw (-0.5, 2.5) node {$Q_2$};
+\draw (-0.5, 1.5) node {$Q_3$};
+\draw (-0.5, 0.5) node {$Q_4$};
\draw (0.5,0.5) node {\large$\star$};
\draw (1.5,0.5) node {\large$\star$};
@@ -811,7 +861,7 @@
\noindent where the lower row is filled with stars, because in
the corresponding pairs there is always one state that is
-accepting ($q_4$) and a state that is non-accepting (the other
+accepting ($Q_4$) and a state that is non-accepting (the other
states).
Now in Step 3 we need to fill in more stars according whether
@@ -833,15 +883,15 @@
\draw (3,0) -- (3, 2);
\draw (4,0) -- (4, 1);
-\draw (0.5,-0.5) node {$q_0$};
-\draw (1.5,-0.5) node {$q_1$};
-\draw (2.5,-0.5) node {$q_2$};
-\draw (3.5,-0.5) node {$q_3$};
+\draw (0.5,-0.5) node {$Q_0$};
+\draw (1.5,-0.5) node {$Q_1$};
+\draw (2.5,-0.5) node {$Q_2$};
+\draw (3.5,-0.5) node {$Q_3$};
-\draw (-0.5, 3.5) node {$q_1$};
-\draw (-0.5, 2.5) node {$q_2$};
-\draw (-0.5, 1.5) node {$q_3$};
-\draw (-0.5, 0.5) node {$q_4$};
+\draw (-0.5, 3.5) node {$Q_1$};
+\draw (-0.5, 2.5) node {$Q_2$};
+\draw (-0.5, 1.5) node {$Q_3$};
+\draw (-0.5, 0.5) node {$Q_4$};
\draw (0.5,0.5) node {\large$\star$};
\draw (1.5,0.5) node {\large$\star$};
@@ -854,23 +904,23 @@
\end{tikzpicture}
\end{center}
-\noindent which means states $q_0$ and $q_2$, as well as $q_1$
-and $q_3$ can be merged. This gives the following minimal DFA
+\noindent which means states $Q_0$ and $Q_2$, as well as $Q_1$
+and $Q_3$ can be merged. This gives the following minimal DFA
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,
inner sep=2pt,draw=blue!50,very thick,
fill=blue!20}]
-\node[state,initial] (q_02) {$q_{0, 2}$};
-\node[state] (q_13) [right=of q_02] {$q_{1, 3}$};
-\node[state, accepting] (q_4) [right=of q_13]
- {$q_{4\phantom{,0}}$};
-\path[->] (q_02) edge [bend left] node [above] {$a$} (q_13);
-\path[->] (q_13) edge [bend left] node [below] {$b$} (q_02);
-\path[->] (q_02) edge [loop below] node {$b$} ();
-\path[->] (q_13) edge node [above] {$a$} (q_4);
-\path[->] (q_4) edge [loop above] node {$a, b$} ();
+\node[state,initial] (Q_02) {$Q_{0, 2}$};
+\node[state] (Q_13) [right=of Q_02] {$Q_{1, 3}$};
+\node[state, accepting] (Q_4) [right=of Q_13]
+ {$Q_{4\phantom{,0}}$};
+\path[->] (Q_02) edge [bend left] node [above] {$a$} (Q_13);
+\path[->] (Q_13) edge [bend left] node [below] {$b$} (Q_02);
+\path[->] (Q_02) edge [loop below] node {$b$} ();
+\path[->] (Q_13) edge node [above] {$a$} (Q_4);
+\path[->] (Q_4) edge [loop above] node {$a, b$} ();
\end{tikzpicture}
\end{center}
@@ -991,3 +1041,34 @@
%%% mode: latex
%%% TeX-master: t
%%% End:
+
+
+\noindent
+Two typical examples of NFAs are
+\begin{center}
+\begin{tabular}[t]{c@{\hspace{9mm}}c}
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+ every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial] (Q_0) {$Q_0$};
+\node[state] (Q_1) [above=of Q_0] {$Q_1$};
+\node[state, accepting] (Q_2) [below=of Q_0] {$Q_2$};
+\path[->] (Q_0) edge node [left] {$\epsilon$} (Q_1);
+\path[->] (Q_0) edge node [left] {$\epsilon$} (Q_2);
+\path[->] (Q_0) edge [loop right] node {$a$} ();
+\path[->] (Q_1) edge [loop above] node {$a$} ();
+\path[->] (Q_2) edge [loop below] node {$b$} ();
+\end{tikzpicture} &
+
+\raisebox{20mm}{
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+ every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial] (r_1) {$r_1$};
+\node[state] (r_2) [above=of r_1] {$r_2$};
+\node[state, accepting] (r_3) [right=of r_1] {$r_3$};
+\path[->] (r_1) edge node [below] {$b$} (r_3);
+\path[->] (r_2) edge [bend left] node [above] {$a$} (r_3);
+\path[->] (r_1) edge [bend left] node [left] {$\epsilon$} (r_2);
+\path[->] (r_2) edge [bend left] node [right] {$a$} (r_1);
+\end{tikzpicture}}
+\end{tabular}
+\end{center}
--- a/progs/nfa.scala Thu Mar 23 14:49:26 2017 +0000
+++ b/progs/nfa.scala Mon Apr 03 01:10:54 2017 +0800
@@ -1,242 +1,26 @@
-// NFAs and Thompson's construction
+// NFAs in Scala based on sets of partial functions
-// helper function for recording time
-def time_needed[T](i: Int, code: => T) = {
- val start = System.nanoTime()
- for (j <- 1 to i) code
- val end = System.nanoTime()
- (end - start)/(i * 1.0e9)
-}
+// type abbreviation for partial functions
+type :=>[A, B] = PartialFunction[A, B]
-
-// state nodes
-abstract class State
-type States = Set[State]
-
-case class IntState(i: Int) extends State
+case class NFA[A, C](starts: Set[A], // starting states
+ delta: Set[(A, C) :=> A], // transitions
+ fins: A => Boolean) { // final states
-object NewState {
- var counter = 0
-
- def apply() : IntState = {
- counter += 1;
- new IntState(counter - 1)
- }
-}
-
+ // given a state and a character, what is the set of next states?
+ // if there is none => empty set
+ def next(q: A, c: C) : Set[A] =
+ delta.flatMap(_.lift.apply(q, c))
-case class NFA(states: States,
- start: State,
- delta: (State, Char) => States,
- eps: State => States,
- fins: States) {
-
- def epsclosure(qs: States) : States = {
- val ps = qs ++ qs.flatMap(eps(_))
- if (qs == ps) ps else epsclosure(ps)
- }
+ def nexts(qs: Set[A], c: C) : Set[A] =
+ qs.flatMap(next(_, c))
- def deltas(qs: States, s: List[Char]) : States = s match {
- case Nil => epsclosure(qs)
- case c::cs => deltas(epsclosure(epsclosure(qs).flatMap (delta (_, c))), cs)
+ def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {
+ case Nil => qs
+ case c::cs => deltas(nexts(qs, c), cs)
}
- def accepts(s: String) : Boolean =
- deltas(Set(start), s.toList) exists (fins contains (_))
-}
-
-// A small example NFA from the lectures
-val Q0 = NewState()
-val Q1 = NewState()
-val Q2 = NewState()
-
-val delta : (State, Char) => States = {
- case (Q0, 'a') => Set(Q0)
- case (Q1, 'a') => Set(Q1)
- case (Q2, 'b') => Set(Q2)
- case (_, _) => Set ()
-}
-
-val eps : State => States = {
- case Q0 => Set(Q1, Q2)
- case _ => Set()
-}
-
-val NFA1 = NFA(Set(Q0, Q1, Q2), Q0, delta, eps, Set(Q2))
-
-NFA1.accepts("aa")
-NFA1.accepts("aaaaa")
-NFA1.accepts("aaaaabbb")
-NFA1.accepts("aaaaabbbaaa")
-NFA1.accepts("ac")
-
-
-// explicit construction of some NFAs; used in
-// Thompson's construction
-
-// NFA that does not accept any string
-def NFA_NULL() : NFA = {
- val Q = NewState()
- NFA(Set(Q), Q, { case (_, _) => Set() }, { case _ => Set() }, Set())
-}
-
-// NFA that accepts the empty string
-def NFA_EMPTY() : NFA = {
- val Q = NewState()
- NFA(Set(Q), Q, { case (_, _) => Set() }, { case _ => Set() }, Set(Q))
-}
-
-// NFA that accepts the string "c"
-def NFA_CHAR(c: Char) : NFA = {
- val Q1 = NewState()
- val Q2 = NewState()
- NFA(Set(Q1, Q2),
- Q1,
- { case (Q1, d) if (c == d) => Set(Q2)
- case (_, _) => Set() },
- { case _ => Set() },
- Set(Q2))
-}
-
-// alternative of two NFAs
-def NFA_ALT(nfa1: NFA, nfa2: NFA) : NFA = {
- val Q = NewState()
- NFA(Set(Q) ++ nfa1.states ++ nfa2.states,
- Q,
- { case (q, c) if (nfa1.states contains q) => nfa1.delta(q, c)
- case (q, c) if (nfa2.states contains q) => nfa2.delta(q, c)
- case (_, _) => Set() },
- { case Q => Set(nfa1.start, nfa2.start)
- case q if (nfa1.states contains q) => nfa1.eps(q)
- case q if (nfa2.states contains q) => nfa2.eps(q)
- case _ => Set() },
- nfa1.fins ++ nfa2.fins)
+ def accepts(s: List[C]) : Boolean =
+ deltas(starts, s).exists(fins)
}
-// sequence of two NFAs
-def NFA_SEQ(nfa1: NFA, nfa2: NFA) : NFA = {
- NFA(nfa1.states ++ nfa2.states,
- nfa1.start,
- { case (q, c) if (nfa1.states contains q) => nfa1.delta(q, c)
- case (q, c) if (nfa2.states contains q) => nfa2.delta(q, c)
- case (_, _) => Set() },
- { case q if (nfa1.fins contains q) => nfa1.eps(q) ++ Set(nfa2.start)
- case q if (nfa1.states contains q) => nfa1.eps(q)
- case q if (nfa2.states contains q) => nfa2.eps(q)
- case _ => Set() },
- nfa2.fins)
-}
-
-// star of an NFA
-def NFA_STAR(nfa: NFA) : NFA = {
- val Q = NewState()
- NFA(Set(Q) ++ nfa.states,
- Q,
- nfa.delta,
- { case Q => Set(nfa.start)
- case q if (nfa.fins contains q) => nfa.eps(q) ++ Set(Q)
- case q if (nfa.states contains q) => nfa.eps(q)
- case _ => Set() },
- Set(Q))
-}
-
-
-// regular expressions used for Thompson's construction
-abstract class Rexp
-
-case object NULL extends Rexp
-case object EMPTY extends Rexp
-case class CHAR(c: Char) extends Rexp
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
-case class STAR(r: Rexp) extends Rexp
-
-// some convenience for typing in regular expressions
-def charlist2rexp(s : List[Char]) : Rexp = s match {
- case Nil => EMPTY
- case c::Nil => CHAR(c)
- case c::s => SEQ(CHAR(c), charlist2rexp(s))
-}
-implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
-
-
-
-def thompson (r: Rexp) : NFA = r match {
- case NULL => NFA_NULL()
- case EMPTY => NFA_EMPTY()
- case CHAR(c) => NFA_CHAR(c)
- case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2))
- case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2))
- case STAR(r1) => NFA_STAR(thompson(r1))
-}
-
-// some examples for Thompson's
-val A = thompson(CHAR('a'))
-
-println(A.accepts("a"))
-println(A.accepts("c"))
-println(A.accepts("aa"))
-
-val B = thompson(ALT("ab","ac"))
-
-println(B.accepts("ab"))
-println(B.accepts("ac"))
-println(B.accepts("bb"))
-println(B.accepts("aa"))
-
-val C = thompson(STAR("ab"))
-
-println(C.accepts(""))
-println(C.accepts("a"))
-println(C.accepts("ababab"))
-println(C.accepts("ab"))
-println(C.accepts("ac"))
-println(C.accepts("bb"))
-println(C.accepts("aa"))
-
-// regular expression matcher using Thompson's
-def matcher(r: Rexp, s: String) : Boolean = thompson(r).accepts(s)
-
-
-//optional
-def OPT(r: Rexp) = ALT(r, EMPTY)
-
-//n-times
-def NTIMES(r: Rexp, n: Int) : Rexp = n match {
- case 0 => EMPTY
- case 1 => r
- case n => SEQ(r, NTIMES(r, n - 1))
-}
-
-// evil regular exproession
-def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))
-
-// test harness for the matcher
-for (i <- 0 to 100 by 5) {
- println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i))))
-}
-
-
-// regular expression matching via search and backtracking
-def accepts2(nfa: NFA, s: String) : Boolean = {
-
- def search(q: State, s: List[Char]) : Boolean = s match {
- case Nil => nfa.fins contains (q)
- case c::cs =>
- (nfa.delta(q, c) exists (search(_, cs))) ||
- (nfa.eps(q) exists (search(_, c::cs)))
- }
-
- search(nfa.start, s.toList)
-}
-
-def matcher2(r: Rexp, s: String) : Boolean = accepts2(thompson(r), s)
-
-// test harness for the backtracking matcher
-for (i <- 0 to 20 by 1) {
- println(i + ": " + "%.5f".format(time_needed(1, matcher2(EVIL(i), "a" * i))))
-}
-
-
-
-