--- a/handouts/ho03.tex Fri Oct 10 16:59:22 2014 +0100
+++ b/handouts/ho03.tex Sat Oct 11 01:13:13 2014 +0100
@@ -1,33 +1,32 @@
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
-
-\usepackage{xcolor}
-\usepackage{tikz}
-\usetikzlibrary{arrows}
-\usetikzlibrary{automata}
-\usetikzlibrary{shapes}
-\usetikzlibrary{shadows}
-\usetikzlibrary{positioning}
-\usetikzlibrary{calc}
-\usetikzlibrary{fit}
-\usetikzlibrary{backgrounds}
+\usepackage{../graphics}
\begin{document}
-\section*{Handout 3}
+\section*{Handout 3 (Automata)}
-Let us have a closer look at automata and their relation to
-regular expressions. This will help us to understand why the
+Every formal language course I know of bombards you first with
+automata and then to a much, much smaller extend with regular
+expressions. As you can see, this course is turned upside
+down: regular expressions come first. The reason is that
+regular expressions are easier to reason about and the notion
+of derivatives, although already quite old, only became more
+widely known rather 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 and Ruby are so slow
-with certain regular expressions.
+with certain regular expressions. The central definition
+is:\medskip
+\noindent
A \emph{deterministic finite automaton} (DFA), say $A$, is
defined by a four-tuple written $A(Q, q_0, F, \delta)$ where
\begin{itemize}
-\item $Q$ is a set of states,
+\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 $\delta$ is the transition function.
@@ -35,15 +34,17 @@
\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 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 ``raise an exception''. A typical
-example of a DFA is
+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
\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},]
+ 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$};
@@ -61,11 +62,13 @@
\end{tikzpicture}
\end{center}
-\noindent The accepting state $q_4$ is indicated with double
-circles. It is 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 be given as a table as
+follows:
\[
\begin{array}{lcl}
@@ -82,35 +85,44 @@
\end{array}
\]
-\noindent We need to define the notion of what language is
-accepted by an automaton. For this we lift the transition
-function $\delta$ from characters to strings as follows:
+We need to define the notion of what language is accepted by
+an automaton. For this we lift the transition function
+$\delta$ from characters to strings as follows:
\[
\begin{array}{lcl}
-\hat{\delta}(q, "") & \dn & q\\
+\hat{\delta}(q, []) & \dn & q\\
\hat{\delta}(q, c\!::\!s) & \dn & \hat{\delta}(\delta(q, c), s)\\
\end{array}
\]
-\noindent Given a string this means we start in the starting
-state and take the first character of the string, follow to
-the next sate, then take the second character and so on. Once
-the string is exhausted and we end up in an accepting state,
-then this string is accepted. Otherwise it is not accepted. So
-$s$ in the \emph{language accepted by the automaton} $A(Q,
-q_0, F, \delta)$ iff
+\noindent This lifted transition function is often called
+``delta-hat''. Given a string, we start in the starting state
+and take the first character of the string, follow to the next
+sate, then take the second character and so on. Once the
+string is exhausted and we end up in an accepting state, then
+this string is accepted by the automaton. Otherwise it is not
+accepted. So $s$ is in the \emph{language accepted by the
+automaton} $A(Q, q_0, F, \delta)$ iff
\[
\hat{\delta}(q_0, s) \in F
\]
+
+\noindent I let you think about a definition that describes
+the set of strings accepted by an automaton.
-While with DFA it will always clear that given a character
-what the next state is, it will be useful to relax this
-restriction. The resulting construction is called a
-\emph{non-deterministic finite automaton} (NFA) given as a
-four-tuple $A(Q, q_0, F, \rho)$ where
+While with DFAs it will always 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 ``silent
+transitions'', also called epsilon-transitions. They allow us
+to go from one state to the next without having a character
+consumed. We label such silent transition with the letter
+$\epsilon$. The resulting construction is called a
+\emph{non-deterministic finite automaton} (NFA) given also as
+a four-tuple $A(Q, q_0, F, \rho)$ where
\begin{itemize}
\item $Q$ is a finite set of states
@@ -149,21 +161,26 @@
\end{tabular}
\end{center}
-\noindent There are 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 $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
-a special transition in NFAs which is called
-\emph{epsilon-transition} or \emph{silent transition}. This
-transition means you do not have to ``consume'' no part of the
-input string, but ``silently'' change to a different state.
+\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$.
+
+
+\subsection*{Thompson Construction}
The reason for introducing NFAs is that there is a relatively
simple (recursive) translation of regular expressions into
@@ -328,7 +345,7 @@
\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 also recognise the
+also an accepting state, because $r^*$ can recognise the
empty string. This gives the following automaton for $r^*$:
\begin{center}
@@ -354,6 +371,99 @@
\noindent This construction of a NFA from a regular expression
was invented by Ken Thompson in 1968.
+
+\subsection*{Subset Construction}
+
+What is interesting that for every NFA we can find a DFA which
+recognises the same language. This can be done by the
+\emph{subset construction}. Consider again the NFA on the
+left, consisting of nodes labeled $0$, $1$ and $2$.
+
+\begin{center}
+\begin{tabular}{c@{\hspace{10mm}}c}
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+ 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$} ();
+\end{tikzpicture}
+&
+\begin{tabular}{r|cl}
+nodes & $a$ & $b$\\
+\hline
+$\varnothing\phantom{\star}$ & $\varnothing$ & $\varnothing$\\
+$\{0\}\phantom{\star}$ & $\{0,1,2\}$ & $\{2\}$\\
+$\{1\}\phantom{\star}$ & $\{1\}$ & $\varnothing$\\
+$\{2\}\star$ & $\varnothing$ & $\{2\}$\\
+$\{0,1\}\phantom{\star}$ & $\{0,1,2\}$ & $\{2\}$\\
+$\{0,2\}\star$ & $\{0,1,2\}$ & $\{2\}$\\
+$\{1,2\}\star$ & $\{1\}$ & $\{2\}$\\
+s: $\{0,1,2\}\star$ & $\{0,1,2\}$ & $\{2\}$\\
+\end{tabular}
+\end{tabular}
+\end{center}
+
+\noindent The nodes of the DFA are given by calculating all
+subsets of the set of nodes of the NFA (seen in the nodes
+column on the right). The table shows the transition function
+for the DFA. The first row states that $\varnothing$ is the
+sink node which has transitions for $a$ and $b$ to itself.
+The next three lines are calculated as follows:
+
+\begin{itemize}
+\item suppose you calculate the entry for the transition for
+ $a$ and the node $\{0\}$
+\item start from the node $0$ in the NFA
+\item do as many $\epsilon$-transition as you can obtaining a
+ set of nodes, in this case $\{0,1,2\}$
+\item filter out all notes that do not allow an $a$-transition
+ from this set, this excludes $2$ which does not permit a
+ $a$-transition
+\item from the remaining set, do as many $\epsilon$-transition
+ as you can, this yields $\{0,1,2\}$
+\item the resulting set specifies the transition from $\{0\}$
+ when given an $a$
+\end{itemize}
+
+\noindent Similarly for the other entries in the rows for
+$\{0\}$, $\{1\}$ and $\{2\}$. The other rows are calculated by
+just taking the union of the single node entries. For example
+for $a$ and $\{0,1\}$ we need to take the union of $\{0,1,2\}$
+(for $0$) and $\{1\}$ (for $1$). The starting state of the DFA
+can be calculated from the starting state of the NFA, that is
+$0$, and then do as many $\epsilon$-transitions as possible.
+This gives $\{0,1,2\}$ which is the starting state of the DFA.
+One terminal states in the DFA are given by all sets that
+contain a $2$, which is the terminal state of the NFA. This
+completes the subset construction.
+
+There are two points to note: One is that the resulting DFA
+contains a number of ``dead'' nodes that are never reachable
+from the starting state (that is that the calculated DFA in
+this example is not a minimal DFA). Such dead nodes can be
+safely removed without changing the language that is
+recognised by the DFA. Another point is that in some cases the
+subset construction produces a DFA that does \emph{not}
+contain any dead nodes\ldots{}that means it calculates a
+minimal DFA. Which in turn means that in some cases the number
+of nodes by going from NFAs to DFAs exponentially increases,
+namely by $2^n$ (which is the number of subsets you can form
+for $n$ nodes).
+
+
+\subsection*{Brzozowski's Method}
+
+\subsection*{Automata Minimization}
+
+\subsection*{Regular Languages and Automata}
+
\end{document}
%%% Local Variables: