# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1444339630 -3600
# Node ID 31e89128ccd27687f13d1769c8098bbff17f0e62
# Parent  22b5294daa2a7a6d1369ca51e8b6db46819f0cbc
updated

diff -r 22b5294daa2a -r 31e89128ccd2 slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r 22b5294daa2a -r 31e89128ccd2 slides/slides03.tex
--- a/slides/slides03.tex	Thu Oct 08 14:06:18 2015 +0100
+++ b/slides/slides03.tex	Thu Oct 08 22:27:10 2015 +0100
@@ -99,48 +99,6 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 
-To see what is going on, define
-
-\begin{center}
-\bl{$Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
-\end{center}\bigskip\bigskip
-
-For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then
-
-\begin{center}
-\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
-$Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\  
-$Der\,a\,A$ & $=$ & $\varnothing$\\
-\end{tabular}}
-\end{center}
- 
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Idea of the Algorithm}
-
-If we want to recognise the string \bl{$abc$} with regular
-expression \bl{$r$} then\medskip
-
-\begin{enumerate}
-\item \bl{$Der\,a\,(L(r))$}\pause
-\item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause
-\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\bigskip\pause
-\item finally we test whether the empty string is in this set\pause\medskip
-\end{enumerate}
-
-The matching algorithm works similarly, just over regular expressions instead of sets.
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
 Input: string \bl{$abc$} and regular expression \bl{$r$} 
 
 \begin{enumerate}
@@ -445,7 +403,9 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}}
+\frametitle{\begin{tabular}{c}
+              Non-Deterministic\\[-1mm] 
+              Finite Automata\end{tabular}}
 
 A non-deterministic finite automaton consists again of:
 
@@ -726,21 +686,21 @@
 \node[state,accepting] (q2) [right=1.5cm of q12] {$\{2\}$};
 \node[state] (qn) [right=of q1] {$\{\}$};
 
-\path[->] (q012) edge [loop below] node  {$a$} ();
-\path[->] (q012) edge node [above]  {$b$} (q2);
-\path[->] (q12) edge [bend left] node [below,pos=0.4]  {$a$} (q1);
-\path[->] (q12) edge node [below]  {$b$} (q2);
-\path[->] (q02) edge node [above]  {$a$} (q012);
-\path[->] (q02) edge [bend left] node [above, pos=0.8]  {$b$} (q2);
-\path[->] (q01) edge node [below]  {$a$} (q012);
-\path[->] (q01) edge [bend left] node [above]  {$b$} (q2);
-\path[->] (q0) edge node [below]  {$a$} (q012);
-\path[->] (q0) edge node [right, pos=0.2]  {$b$} (q2);
-\path[->] (q1) edge [loop above] node  {$a$} ();
-\path[->] (q1) edge node [above]  {$b$} (qn);
-\path[->] (q2) edge [loop right] node  {$b$} ();
-\path[->] (q2) edge node [below]  {$a$} (qn);
-\path[->] (qn) edge [loop above] node  {$a,b$} ();
+\path[->] (q012) edge [loop below] node  {\alert{$a$}} ();
+\path[->] (q012) edge node [above]  {\alert{$b$}} (q2);
+\path[->] (q12) edge [bend left] node [below,pos=0.4]  {\alert{$a$}} (q1);
+\path[->] (q12) edge node [below]  {\alert{$b$}} (q2);
+\path[->] (q02) edge node [above]  {\alert{$a$}} (q012);
+\path[->] (q02) edge [bend left] node [above, pos=0.8]  {\alert{$b$}} (q2);
+\path[->] (q01) edge node [below]  {\alert{$a$}} (q012);
+\path[->] (q01) edge [bend left] node [above]  {\alert{$b$}} (q2);
+\path[->] (q0) edge node [below]  {\alert{$a$}} (q012);
+\path[->] (q0) edge node [right, pos=0.2]  {\alert{$b$}} (q2);
+\path[->] (q1) edge [loop above] node  {\alert{$a$}} ();
+\path[->] (q1) edge node [above]  {\alert{$b$}} (qn);
+\path[->] (q2) edge [loop right] node  {\alert{$b$}} ();
+\path[->] (q2) edge node [below]  {\alert{$a$}} (qn);
+\path[->] (qn) edge [loop above] node  {$\alert{a},\alert{b}$} ();
 \end{tikzpicture}
 \end{center}
 
@@ -822,7 +782,7 @@
 \begin{center}
 \bl{$(\delta(q, c), \delta(p,c))$}
 \end{center} 
-are marked. If yes, then also mark \bl{$(q, p)$}.
+are marked. If yes in at least one case, then also mark \bl{$(q, p)$}.
 \item Repeat last step until no change.
 \item All unmarked pairs can be merged.
 \end{enumerate}