# HG changeset patch
# User cu
# Date 1507657930 -3600
# Node ID 3566c8175e63d51bd6d8ad0e7d5ab29e95b2617c
# Parent  676e6484f29bc65779667376fc00707ac83d15aa
updated

diff -r 676e6484f29b -r 3566c8175e63 slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r 676e6484f29b -r 3566c8175e63 slides/slides03.tex
--- a/slides/slides03.tex	Tue Oct 03 23:35:16 2017 +0100
+++ b/slides/slides03.tex	Tue Oct 10 18:52:10 2017 +0100
@@ -29,7 +29,7 @@
   \begin{tabular}{lp{8cm}}
   Email:  & christian.urban at kcl.ac.uk\\
   Office: & N7.07 (North Wing, Bush House)\\
-  Slides: & KEATS (also home work and coursework is there)\\
+  Slides: & KEATS (also homework and coursework is there)\\
   \end{tabular}
   \end{center}
 
@@ -41,9 +41,10 @@
 \frametitle{Scala Book, Exams}
 
 \begin{itemize}
-\item www.inf.kcl.ac.uk/~urbanc/ProgInScala2ed.pdf
-\item homeworks (exam 80\%)
-\item coursework (20\%)
+\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
+\item homeworks (written exam 80\%)
+\item coursework (20\%)\bigskip
+\item short survey at KEATS; to be answered until Sunday    
 \end{itemize}
 
 \end{frame}
@@ -111,6 +112,30 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{Example}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+
+\begin{center}
+\def\arraystretch{1.5}  
+\begin{tabular}{@{}lcl}
+  \bl{$\der\,a\,((a \cdot b) + b)^*$}
+    & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
+    & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
+    & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
+    & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
+    & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
+    & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
 
 Input: string \bl{$abc$} and regular expression \bl{$r$} 
 
@@ -122,12 +147,33 @@
 \end{enumerate}
 
 \end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+
+\begin{center}
+\def\arraystretch{2}  
+\begin{tabular}{@{}lcl}
+  \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
+    & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
+    & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
+    & \bl{$=$} & \bl{$b \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 
-We proved already
+We proved partially
 
 \begin{center}
 \bl{$nullable(r)$} \;if and only if\;  \bl{$[] \in L(r)$}
@@ -197,7 +243,7 @@
 
 \begin{center}
    \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & null\\
+  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
          & \bl{$\mid$} & \bl{$\ONE$}        & empty string / "" / $[]$\\
          & \bl{$\mid$} & \bl{$c$}                         & character\\
          & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
@@ -243,25 +289,6 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\mode<presentation>{
-%\begin{frame}[c]
-%\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}
-%
-%Lexing separates strings into ``words'' / components.
-%
-%\begin{itemize}
-%\item Identifiers (non-empty strings of letters or digits, starting with a letter)
-%\item Numbers (non-empty sequences of digits omitting leading zeros)
-%\item Keywords (else, if, while, \ldots)
-%\item White space (a non-empty sequence of blanks, newlines and tabs)
-%\item Comments
-%\end{itemize}
-%
-%\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Automata}
@@ -269,18 +296,19 @@
 A \alert{\bf deterministic finite automaton}, DFA, consists of:
 
 \begin{itemize}
+\item an alphabet \bl{$\varSigma$}  
 \item a set of states \bl{$Q$}
-\item one of these states is the start state \bl{$q_0$}
+\item one of these states is the start state \bl{$\mbox{Q}_0$}
 \item some states are accepting states \bl{$F$}, and
 \item there is transition function \bl{$\delta$}\bigskip 
 
 \small
 which takes a state as argument and a character and produces a 
-new state; this function might not be everywhere defined
+new state; this function might not be everywhere defined $\Rightarrow$ partial function
 \end{itemize}
 
 \begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
+\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}
 \end{center}
 
 \end{frame}
@@ -293,20 +321,20 @@
 \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_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]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
+\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);
+\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 \end{center}
 
@@ -326,20 +354,20 @@
 \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_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]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
+\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);
+\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 \end{center}
 
@@ -347,8 +375,10 @@
 
 \begin{center}
 \begin{tabular}{lll}
-\bl{$(q_0, a) \rightarrow q_1$} & \bl{$(q_1, a) \rightarrow q_4$} & \bl{$(q_4, a) \rightarrow q_4$}\\
-\bl{$(q_0, b) \rightarrow q_2$} & \bl{$(q_1, b) \rightarrow q_2$} & \bl{$(q_4, b) \rightarrow q_4$}\\
+  \bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$}
+  & \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\
+  \bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} &
+  \bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\
 \end{tabular}\ldots
 \end{center}
 
@@ -362,22 +392,22 @@
 Given
 
 \begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
+\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}
 \end{center}
 
 you can define
 
 \begin{center}
 \begin{tabular}{l}
-\bl{$\hat{\delta}(q, []) \dn q$}\\
-\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\
+\bl{$\widehat{\delta}(q, []) \dn q$}\\
+\bl{$\widehat{\delta}(q, c::s) \dn \widehat{\delta}(\delta(q, c), s)$}\\
 \end{tabular}
 \end{center}\pause
 
 Whether a string \bl{$s$} is accepted by \bl{$A$}?
 
 \begin{center}
-\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}
+\hspace{5mm}\bl{$\hat{\delta}(\mbox{Q}_0, s) \in F$}
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -420,11 +450,11 @@
               Non-Deterministic\\[-1mm] 
               Finite Automata\end{tabular}}
 
-A non-deterministic finite automaton consists again of:
+A non-deterministic finite automaton (NFA) consists again of:
 
 \begin{itemize}
 \item a finite set of states
-\item one of these states is the start state
+\item \underline{some} these states are the start states
 \item some states are accepting states, and
 \item there is transition \alert{relation}\medskip 
 \end{itemize}
@@ -432,13 +462,12 @@
 
 \begin{center}
 \begin{tabular}{c}
-\bl{$(q_1, a) \rightarrow q_2$}\\
-\bl{$(q_1, a) \rightarrow q_3$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_2$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_3$}\\
 \end{tabular}
-\hspace{10mm}
-\begin{tabular}{c}
-\bl{$(q_1, \epsilon) \rightarrow q_2$}\\
-\end{tabular}
+\bl{\ldots}
+\hspace{10mm}\pause
+\bl{$(\mbox{Q}_1, a) \rightarrow \{\mbox{Q}_2, \mbox{Q}_3\}$}
 \end{center}
 
 \end{frame}
@@ -446,7 +475,31 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Two NFA Examples}
+\frametitle{An NFA Example}
+
+% A NFA for (ab* + b)*a
+\begin{center}
+\begin{tikzpicture}[>=stealth',very thick, auto,
+    every state/.style={minimum size=0pt,inner sep=3pt,
+      draw=blue!50,very thick,fill=blue!20},scale=2]
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};
+\path[->] (Q_0) edge [loop above] node  {\alert{$b$}} ();
+\path[<-] (Q_0) edge node [below]  {\alert{$b$}} (Q_1);
+\path[->] (Q_0) edge [bend left] node [above]  {\alert{$a$}} (Q_1);
+\path[->] (Q_0) edge [bend right] node [below]  {\alert{$a$}} (Q_2);
+\path[->] (Q_1) edge [loop above] node  {\alert{$a,b$}} ();
+\path[->] (Q_1) edge node  [above] {\alert{$a$}} (Q_2);
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Two Epsilon NFA Examples}
 
 \small
 \begin{center}
@@ -480,6 +533,7 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Rexp to NFA}
@@ -488,17 +542,17 @@
 \begin{tabular}[t]{l@{\hspace{10mm}}l}
 \raisebox{1mm}{\bl{$\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}{\bl{$\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}{\bl{$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]  {\alert{$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]  {\alert{$c$}} (Q_1);
 \end{tikzpicture}\\\\
 \end{tabular}
 \end{center}
@@ -511,40 +565,73 @@
 \frametitle{Case $r_1\cdot r_2$}
 
 \mbox{}\bigskip
-\onslide<1>{By recursion we are given two automata:\bigskip}
+\onslide<1->{By recursion we are given two automata:\bigskip}
 
-{\centering\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$};
-\only<1>{
-\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{}$};}
-\only<2>{
-\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{}$};}
-\only<1>{\node[state, initial]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};}
-\only<2>{\node[state]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};}
-\node (b_1)  [right=of a_0] {$\ldots$};
+{\centering%
+\only<1>{%
+\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[state, initial]  (Q_01) [below=1mm of Q_0] {$\mbox{}$};  
+\node[state, initial]  (Q_02) [above=1mm of 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{}$};
+
+\node (A_0)  [right=2.5cm of T_1] {$\mbox{}$};
+\node[state, initial]  (A_01)  [above=1mm of A_0] {$\mbox{}$};
+\node[state, initial]  (A_02)  [below=1mm of A_0] {$\mbox{}$};
+
+\node (b_1)  [right=of A_0] {$\ldots$};
 \node[state, accepting]  (c_1)  [right=of b_1] {$\mbox{}$};
 \node[state, accepting]  (c_2)  [above=of c_1] {$\mbox{}$};
 \node[state, accepting]  (c_3)  [below=of c_1] {$\mbox{}$};
-\only<2>{
-\path[->] (t_1) edge node [above, pos=0.3]  {\alert{$\epsilon$}} (a_0);
-\path[->] (t_2) edge node [above]  {\alert{$\epsilon$}} (a_0);
-\path[->] (t_3) edge node [below]  {\alert{$\epsilon$}} (a_0);
-}
 \begin{pgfonlayer}{background}
-\only<1>{\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)] {};}
-\only<1>{\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)] {};}
-\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};}
-\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}
-\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}
-\only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}
+  \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$};
 \end{pgfonlayer}
-\end{tikzpicture}}\bigskip\bigskip
+\end{tikzpicture}}
+\only<2>{%
+\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[state, initial]  (Q_01) [below=1mm of Q_0] {$\mbox{}$};  
+\node[state, initial]  (Q_02) [above=1mm of 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{}$};
+
+\node  (A_0)  [right=2.5cm of t_1] {$\mbox{}$};
+\node[state]  (A_01)  [above=1mm of A_0] {$\mbox{}$};
+\node[state]  (A_02)  [below=1mm of A_0] {$\mbox{}$};
+
+\node (b_1)  [right=of A_0] {$\ldots$};
+\node[state, accepting]  (c_1)  [right=of b_1] {$\mbox{}$};
+\node[state, accepting]  (c_2)  [above=of c_1] {$\mbox{}$};
+\node[state, accepting]  (c_3)  [below=of c_1] {$\mbox{}$};
+\path[->] (t_1) edge (A_01);
+\path[->] (t_2) edge node [above]  {$\epsilon$s} (A_01);
+\path[->] (t_3) edge (A_01);
+\path[->] (t_1) edge (A_02);
+\path[->] (t_2) edge (A_02);
+\path[->] (t_3) edge node [below]  {$\epsilon$s} (A_02);
+ 
+\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 [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+%
+}\bigskip\bigskip
 
 \small
 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them
@@ -556,23 +643,24 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Case $r_1+ r_2$}
-\mbox{}\\[-10mm]
+\mbox{}\\[-8mm]
 
-\onslide<1>{By recursion we are given two automata:\smallskip}
+\onslide<1->{By recursion we are given two automata:\smallskip}
 
-\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
-                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
-\onslide<1>{\node at (0,0)  (1)  {$\mbox{}$};}
-\onslide<2>{\node at (0,0) [state, initial]  (1)  {$\mbox{}$};}
-\only<1>{
-\node[state, initial]  (2)  [above right=16mm of 1] {$\mbox{}$};
-\node[state, initial]  (3)  [below right=16mm of 1] {$\mbox{}$};}
-\only<2>{
-\node[state]  (2)  [above right=16mm of 1] {$\mbox{}$};
-\node[state]  (3)  [below right=16mm of 1] {$\mbox{}$};}
+\hspace{2cm}
+\only<1>{%
+  \begin{tikzpicture}[node distance=3mm,
+    >=stealth',very thick,
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.center)]
+\node at (0,0)  (1)  {$\mbox{}$};
+\node  (2)  [above=14mm of 1] {};
+\node[state, initial]  (4)  [above=1mm of 2] {$\mbox{}$};
+\node[state, initial]  (5)  [below=1mm of 2] {$\mbox{}$};
+\node[state, initial]  (3)  [below=10mm of 1] {$\mbox{}$};
 
-\node (a)  [right=of 2] {$\ldots$};
-\node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};
+\node (a)  [right=of 2] {$\ldots\,$};
+\node  (a1)  [right=of a] {$$};
 \node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};
 \node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};
 
@@ -580,21 +668,46 @@
 \node[state, accepting]  (b1)  [right=of b] {$\mbox{}$};
 \node[state, accepting]  (b2)  [above=of b1] {$\mbox{}$};
 \node[state, accepting]  (b3)  [below=of b1] {$\mbox{}$};
-\only<2>{
-\path[->] (1) edge node [above]  {\alert{$\epsilon$}} (2);
-\path[->] (1) edge node [below]  {\alert{$\epsilon$}} (3);
-}
 \begin{pgfonlayer}{background}
-\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
-\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}
-\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}
-\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}
-\only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}
-\only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}
+\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
+\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};
+\node [yshift=3mm] at (1.north) {$r_1$};
+\node [yshift=3mm] at (2.north) {$r_2$};
 \end{pgfonlayer}
-\end{tikzpicture}
+\end{tikzpicture}}
+\only<2>{%
+\begin{tikzpicture}[node distance=3mm,
+    >=stealth',very thick,
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.center)]
+\node at (0,0) (1)  {$\mbox{}$};
+\node (2)  [above=14mm of 1] {$$};
+\node[state, initial]  (4)  [above=1mm of 2] {$\mbox{}$};
+\node[state, initial]  (5)  [below=1mm of 2] {$\mbox{}$};
+\node[state, initial]  (3)  [below=10mm of 1] {$\mbox{}$};
+
+\node (a)  [right=of 2] {$\ldots\,$};
+\node (a1)  [right=of a] {$$};
+\node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};
+\node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};
+
+\node (b)  [right=of 3] {$\ldots$};
+\node[state, accepting]  (b1)  [right=of b] {$\mbox{}$};
+\node[state, accepting]  (b2)  [above=of b1] {$\mbox{}$};
+\node[state, accepting]  (b3)  [below=of b1] {$\mbox{}$};
+
+%\path[->] (1) edge node [above]  {$\epsilon$} (2);
+%\path[->] (1) edge node [below]  {$\epsilon$} (3);
+
+\begin{pgfonlayer}{background}
+\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};
+\node [yshift=3mm] at (3.north) {$r_1+ r_2$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+%
 
 \small
+\mbox{}\\\medskip
 We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -603,37 +716,48 @@
 \begin{frame}[c]
 \frametitle{Case $r^*$}
 
-\onslide<1>{By recursion we are given an automaton for $r$:\smallskip}
+\onslide<1->{By recursion we are given an automaton for $r$:\smallskip}
 
-\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
-                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
-\onslide<1>{\node at (0,0)  (1)  {$\mbox{}$};}
-\onslide<2->{\node at (0,0) [state, initial,accepting]  (1)  {$\mbox{}$};}
-\only<1>{\node[state, initial]  (2)  [right=16mm of 1] {$\mbox{}$};}
-\only<2->{\node[state]  (2)  [right=16mm of 1] {$\mbox{}$};}
+\hspace{2cm}
+\only<1>{\begin{tikzpicture}[node distance=3mm,
+    >=stealth',very thick,
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.north)]
+\node (2)  {$\mbox{}$};
+\node[state, initial]  (4)  [above=1mm of 2] {$\mbox{}$};
+\node[state, initial]  (5)  [below=1mm of 2] {$\mbox{}$};  
 \node (a)  [right=of 2] {$\ldots$};
-\only<1>{
 \node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};
 \node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};
-\node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};}
-\only<2->{
+\node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};
+\begin{pgfonlayer}{background}
+\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
+\node [yshift=3mm] at (1.north) {$r$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+\only<2->{\begin{tikzpicture}[node distance=3mm,
+    >=stealth',very thick,
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.north)]
+\node at (0,0) [state, initial,accepting]  (1)  {$\mbox{}$};
+\node (2)  [right=16mm of 1] {$\mbox{}$};
+\node[state]  (4)  [above=1mm of 2] {$\mbox{}$};
+\node[state]  (5)  [below=1mm of 2] {$\mbox{}$};  
+\node (a)  [right=of 2] {$\ldots$};
 \node[state]  (a1)  [right=of a] {$\mbox{}$};
 \node[state]  (a2)  [above=of a1] {$\mbox{}$};
-\node[state]  (a3)  [below=of a1] {$\mbox{}$};}
-\only<2->{
-\path[->] (1) edge node [above]  {\alert{$\epsilon$}} (2);
-\path[->] (a1) edge [bend left=45] node [above]  {\alert{$\epsilon$}} (1);
-\path[->] (a2) edge [bend right] node [below]  {\alert{$\epsilon$}} (1);
-\path[->] (a3) edge [bend left=45] node [below]  {\alert{$\epsilon$}} (1);
-
-}
+\node[state]  (a3)  [below=of a1] {$\mbox{}$};
+\path[->] (1) edge node [below]  {$\epsilon$} (4);
+\path[->] (1) edge node [below]  {$\epsilon$} (5);
+\path[->] (a1) edge [bend left=45] node [below]  {$\epsilon$} (1);
+\path[->] (a2) edge [bend right] node [below]  {$\epsilon$} (1);
+\path[->] (a3) edge [bend left=45] node [below]  {$\epsilon$} (1);
 \begin{pgfonlayer}{background}
-\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
-\only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}
-\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
-\only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}
+\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
+\node [yshift=3mm] at (2.north) {$r^*$};
 \end{pgfonlayer}
-\end{tikzpicture}\bigskip
+\end{tikzpicture}}
+\bigskip
 
 \onslide<3->{
 Why can't we just have an epsilon transition from the accepting states to the starting state?}
@@ -648,16 +772,16 @@
 
 \begin{textblock}{5}(1,1)
 \begin{center}
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+\begin{tikzpicture}[node distance=6mm,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$}} ();
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [below=of Q_0] {$\mbox{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}
@@ -748,14 +872,14 @@
 \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$}} ();
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [below=of Q_0] {$\mbox{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{tabular}
 \end{center}
@@ -809,20 +933,20 @@
 \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_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]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
+\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);
+\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 \end{center}
 
@@ -842,15 +966,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 {$\mbox{Q}_0$}; 
+\draw (1.5,-0.5) node {$\mbox{Q}_1$}; 
+\draw (2.5,-0.5) node {$\mbox{Q}_2$}; 
+\draw (3.5,-0.5) node {$\mbox{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 {$\mbox{Q}_1$}; 
+\draw (-0.5, 2.5) node {$\mbox{Q}_2$}; 
+\draw (-0.5, 1.5) node {$\mbox{Q}_3$}; 
+\draw (-0.5, 0.5) node {$\mbox{Q}_4$}; 
 
 \draw (0.5,0.5) node {\large$\star$}; 
 \draw (1.5,0.5) node {\large$\star$}; 
@@ -869,20 +993,20 @@
 \begin{tabular}{@{\hspace{-8mm}}cc@{}}
 \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_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]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
+\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);
+\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 &
 \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]
@@ -898,15 +1022,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 {$\mbox{Q}_0$}; 
+\draw (1.5,-0.5) node {$\mbox{Q}_1$}; 
+\draw (2.5,-0.5) node {$\mbox{Q}_2$}; 
+\draw (3.5,-0.5) node {$\mbox{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 {$\mbox{Q}_1$}; 
+\draw (-0.5, 2.5) node {$\mbox{Q}_2$}; 
+\draw (-0.5, 1.5) node {$\mbox{Q}_3$}; 
+\draw (-0.5, 0.5) node {$\mbox{Q}_4$}; 
 
 \draw (0.5,0.5) node {\large$\star$}; 
 \draw (1.5,0.5) node {\large$\star$}; 
@@ -926,14 +1050,14 @@
 \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]  {\alert{$a$}} (q_13);
-\path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);
-\path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();
-\path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
+\node[state,initial]  (Q_02)  {$\mbox{Q}_{0, 2}$};
+\node[state] (Q_13) [right=of Q_02] {$\mbox{Q}_{1, 3}$};
+\node[state, accepting] (Q_4) [right=of Q_13] {$\mbox{Q}_{4\phantom{,0}}$};
+\path[->] (Q_02) edge [bend left] node [above]  {\alert{$a$}} (Q_13);
+\path[->] (Q_13) edge [bend left] node [below]  {\alert{$b$}} (Q_02);
+\path[->] (Q_02) edge [loop below] node  {\alert{$b$}} ();
+\path[->] (Q_13) edge node [above]  {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop above] node  {\alert{$a, b$}} ();
 \end{tikzpicture}\\
 minimal automaton
 \end{center}
@@ -951,33 +1075,33 @@
 \begin{tikzpicture}[>=stealth',very thick,auto,
                     every state/.style={minimum size=0pt,
                     inner sep=2pt,draw=blue!50,very thick,fill=blue!20}]
-\only<1>{\node[state,initial]  (q_0)  {$q_0$};}
-\only<2->{\node[state,accepting]  (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$};
-\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}
-\only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};}
+\only<1>{\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};}
+\only<2->{\node[state,accepting]  (Q_0)  {$\mbox{Q}_0$};}
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\only<1>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
+\only<2->{\node[state, initial right] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
 \only<1-2>{
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop above] node  {\alert{$a, b$}} ();
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
+\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);
+\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);}
 \only<3->{
-\path[<-] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[<-] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[<-] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[<-] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[<-] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[<-] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[<-] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[<-] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}
+\path[<-] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
+\path[<-] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
+\path[<-] (Q_4) edge [loop above] node  {\alert{$a, b$}} ();
+\path[<-] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
+\path[<-] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
+\path[<-] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
+\path[<-] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);
+\path[<-] (Q_2) edge [loop left] node  {\alert{$b$}} ();
+\path[<-] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);}
 \end{tikzpicture}
 \end{center}
 \mbox{}\\[-18mm]
@@ -1025,12 +1149,12 @@
 \begin{center}
 \begin{tikzpicture}[scale=2,>=stealth',very thick,
                              every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
-  \only<1>{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<2->{\node[state, initial,accepting]        (q0) at ( 0,1) {$q_0$};}
-  \only<1>{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<2->{\node[state,accepting]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
-  \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};}
+  \only<1>{\node[state, initial]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
+  \only<2->{\node[state, initial,accepting]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
+  \only<1>{\node[state]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \only<2->{\node[state,accepting]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \only<1>{\node[state, accepting] (q2) at ( 2,1) {$\mbox{Q}_2$};}
+  \only<2->{\node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};}
   \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
                   (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
                   (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
@@ -1052,9 +1176,9 @@
 \begin{center}
 \begin{tikzpicture}[scale=2,>=stealth',very thick,
                              every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
-  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
+  \only<1->{\node[state]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \only<1->{\node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};}
   \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
                   (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
                   (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
@@ -1069,9 +1193,9 @@
 You know how to solve since school days, no?
 \begin{center}
 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 +  4\, q_2$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$2\, \mbox{Q}_0 + 3 \,\mbox{Q}_1 +  4\, \mbox{Q}_2$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$2 \,\mbox{Q}_0 + 3\, \mbox{Q}_1 + 1\, \mbox{Q}_2$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$1\, \mbox{Q}_0 + 5\, \mbox{Q}_1 + 2\, \mbox{Q}_2$}\\
 
 \end{tabular}
 \end{center}
@@ -1086,9 +1210,9 @@
 \begin{center}
 \begin{tikzpicture}[scale=2,>=stealth',very thick,
                              every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
-  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
+  \only<1->{\node[state]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \only<1->{\node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};}
   \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
                   (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
                   (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
@@ -1102,9 +1226,9 @@
 \onslide<2->{
 \begin{center}
 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b +  q_2\,b$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b +  \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
 
 \end{tabular}
 \end{center}