# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1381348492 -3600
# Node ID cc19e6cbcb6884ce8eeadeae4884e64ba21ba29e
# Parent  72b686e1c974081079f9ae18342060cfe05a10ba
added

diff -r 72b686e1c974 -r cc19e6cbcb68 slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r 72b686e1c974 -r cc19e6cbcb68 slides/slides03.tex
--- a/slides/slides03.tex	Tue Oct 08 21:59:31 2013 +0100
+++ b/slides/slides03.tex	Wed Oct 09 20:54:52 2013 +0100
@@ -165,7 +165,7 @@
   \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\
   & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ 
   & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
-  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause
+  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\
 
   \bl{$der\!s\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
   \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
@@ -360,11 +360,11 @@
 \begin{itemize}
 \item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip
 \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip
-\item \bl{$nullable (r) \dn not (nullable(r))$}\medskip
+\item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip
 \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}
 \end{itemize}\bigskip\pause
 
-Used often for comments:
+Used often for recognising comments:
 
 \[
 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}
@@ -380,7 +380,7 @@
 \frametitle{\begin{tabular}{c}Negation\end{tabular}}
 
 Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only.
-Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}.
+Find a regular expression that matches all strings \emph{except} \bl{ab} and \bl{ac}.
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -410,7 +410,7 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Automata\end{tabular}}
 
-A deterministic finite automaton consists of:
+A \alert{deterministic finite automaton} consists of:
 
 \begin{itemize}
 \item a set of states
@@ -420,27 +420,7 @@
 
 \small
 which takes a state as argument and a character and produces a new state\smallskip\\
-this function might not always be defined
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Automata\end{tabular}}
-
-A deterministic finite automaton consists of:
-
-\begin{itemize}
-\item a set of states
-\item one of these states is the start state
-\item some states are accepting states, and
-\item there is transition function\medskip 
-
-\small
-which takes a state as argument and a character and produces a new state\smallskip\\
-this function might not always be defined
+this function might not be everywhere defined
 \end{itemize}
 
 \begin{center}
@@ -550,9 +530,16 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{An NFA}
 
 \begin{center}
-\includegraphics[scale=0.7]{pics/ch5.jpg}
+\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]  {\alert{$\epsilon$}} (q_1);
\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);
+\path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();
\path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();
+\path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();
+\end{tikzpicture}
 \end{center}
 
 
@@ -622,8 +609,16 @@
 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}
 
 
-\begin{textblock}{5}(1,2.5)
-\includegraphics[scale=0.5]{pics/ch5.jpg}
+\begin{textblock}{5}(1,1)
+\begin{center}
+\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]  {\alert{$\epsilon$}} (q_1);
\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);
+\path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();
\path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();
+\path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();
+\end{tikzpicture}
+\end{center}
 \end{textblock}
 
 \begin{textblock}{11}(6.5,4.5)
@@ -688,7 +683,7 @@
 
 \begin{enumerate}
 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}
-\item Mark all pairs that accepting and non-accepting states
+\item Mark all pairs that are accepting and non-accepting states
 \item For  all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether
 \begin{center}
 \bl{($\delta$(q,c), $\delta$(p,c))}