Binary file handouts/ho01.pdf has changed

--- a/handouts/ho01.tex	Fri Oct 10 16:59:22 2014 +0100
+++ b/handouts/ho01.tex	Sat Oct 11 01:13:13 2014 +0100
@@ -17,14 +17,14 @@
 \emph{not} just look for a particular string, but for string
 patterns. For example in programming code we need to identify
 what are the keywords, what are the identifiers etc. A pattern
-for identifiers could be that they start with a letter,
+for identifiers could be stated as: they start with a letter,
 followed by zero or more letters, numbers and the underscore.
 Also often we face the problem that we are given a string (for
 example some user input) and want to know whether it matches a
 particular pattern. In this way we can exclude user input that
 would otherwise have nasty effects on our program (crashing it
 or going into an infinite loop, if not worse). \defn{Regular
-expressions} help with conveniently specifying such patterns. 
+expressions} help with conveniently specifying such patterns.
 The idea behind regular expressions is that they are a simple
 method for describing languages (or sets of strings)\ldots at
 least languages we are interested in in computer science. For

Binary file handouts/ho02.pdf has changed

--- a/handouts/ho02.tex	Fri Oct 10 16:59:22 2014 +0100
+++ b/handouts/ho02.tex	Sat Oct 11 01:13:13 2014 +0100
@@ -4,7 +4,7 @@
 \usepackage{../graphics}
 \usepackage{../data}
 
-\pgfplotsset{compat=1.11}
+\pgfplotsset{compat=1.11}
 \begin{document}
 
 \section*{Handout 2}
@@ -19,25 +19,29 @@
 
 \begin{center}
 \begin{tabular}{@{}cc@{}}
-\begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
+\begin{tikzpicture}
+\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
     enlargelimits=false,
     xtick={0,5,...,30},
     xmax=30,
-    ymax=35,
    ytick={0,5,...,30},
+    ymax=35,
+    ytick={0,5,...,30},
     scaled ticks=false,
     axis lines=left,
     width=5cm,
     height=5cm, 
     legend entries={Python,Ruby},  
     legend pos=north west,
-    legend cell align=left  
]
+    legend cell align=left]
 \addplot[blue,mark=*, mark options={fill=white}] 
   table {re-python.data};
 \addplot[brown,mark=pentagon*, mark options={fill=white}] 
   table {re-ruby.data};  
-\end{axis}
\end{tikzpicture}
+\end{axis}
+\end{tikzpicture}
 &
-\begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
+\begin{tikzpicture}
+  \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
     enlargelimits=false,
     xtick={0,3000,...,12000},
     xmax=12000,
@@ -45,8 +49,11 @@
     scaled ticks=false,
     axis lines=left,
     width=6.5cm,
-    height=5cm
]
\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
-\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
\end{axis}
\end{tikzpicture}
+    height=5cm]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
 \end{tabular}
 \end{center}\medskip
 
@@ -532,20 +539,25 @@
 \begin{figure}[p]
 \lstinputlisting{../progs/app6.scala}
 \caption{The simplification function and modified 
-\pcode{ders}-function.\label{scala2}}
+\texttt{ders}-function.\label{scala2}}
 \end{figure}
 
 \begin{center}
-\begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
+\begin{tikzpicture}
+\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
     enlargelimits=false,
     xtick={0,2000,...,12000},
-    xmax=12000,
    ytick={0,5,...,30},
+    xmax=12000,
+    ytick={0,5,...,30},
     scaled ticks=false,
     axis lines=left,
     width=9cm,
     height=4cm, 
-    legend entries={Scala V2,Scala V3},    
]
\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
-\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
\end{axis}
\end{tikzpicture}
+    legend entries={Scala V2,Scala V3}]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
 \end{center}
 
 \end{document}

Binary file handouts/ho03.pdf has changed

--- 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: 

Binary file slides/slides01.pdf has changed

Binary file slides/slides02.pdf has changed

Binary file slides/slides03.pdf has changed