afl-material: comparison slides/slides03.tex

equal deleted inserted replaced

-:676e6484f29b
+:3566c8175e63
 \normalsize
 \begin{center}
 \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}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Scala Book, Exams}
 \begin{itemize}
-\item www.inf.kcl.ac.uk/~urbanc/ProgInScala2ed.pdf
+\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
-\item homeworks (exam 80\%)
+\item homeworks (written exam 80\%)
-\item coursework (20\%)
+\item coursework (20\%)\bigskip
+\item short survey at KEATS; to be answered until Sunday
 \end{itemize}
 \end{frame}
 %%%%%%%%%%%
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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$}
 \begin{enumerate}
 \item \bl{$der\,a\,r$}
 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
 \item finally check whether the last regular expression can match the empty string
 \end{enumerate}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{Simplification}
-We proved already
+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 partially
 \begin{center}
 \bl{$nullable(r)$} \;if and only if\;  \bl{$[] \in L(r)$}
 \end{center}
 \begin{frame}[t]
 \frametitle{Regular Expressions}
 \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\\
 & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\
 & \bl{$\mid$} & \bl{$r^*$}                   & star (zero or more)\\
 \bl{$ab$} and \bl{$ac$}!
 \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}
 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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \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,initial]  (Q_0)  {$\mbox{Q}_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
-\path[->] (q_0) edge node [above]  {\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_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_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 \end{center}
 \begin{itemize}
 \begin{frame}[c]
 \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,initial]  (Q_0)  {$\mbox{Q}_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
-\path[->] (q_0) edge node [above]  {\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_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_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 \end{center}
 for this automaton \bl{$\delta$} is the function\\
 \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{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{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}_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}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \frametitle{Accepting a String}
 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{$\widehat{\delta}(q, []) \dn q$}\\
-\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\
+\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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}
 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}
 \begin{center}
 \begin{tabular}{c}
-\bl{$(q_1, a) \rightarrow q_2$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_2$}\\
-\bl{$(q_1, a) \rightarrow q_3$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_3$}\\
 \end{tabular}
-\hspace{10mm}
+\bl{\ldots}
-\begin{tabular}{c}
+\hspace{10mm}\pause
-\bl{$(q_1, \epsilon) \rightarrow q_2$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \{\mbox{Q}_2, \mbox{Q}_3\}$}
-\end{tabular}
+\end{center}
-\end{center}
+\end{frame}
-\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{An NFA Example}
-\frametitle{Two NFA Examples}
+% 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}
 \begin{tabular}[t]{c@{\hspace{9mm}}c}
 \begin{tikzpicture}[scale=0.7,>=stealth',very thick,
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Rexp to NFA}
 \begin{center}
 \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, initial]  (Q_0)  {$\mbox{}$};
-\node[state, accepting]  (q_1)  [right=of q_0] {$\mbox{}$};
+\node[state, accepting]  (Q_1)  [right=of Q_0] {$\mbox{}$};
-\path[->] (q_0) edge node [below]  {\alert{$c$}} (q_1);
+\path[->] (Q_0) edge node [below]  {\alert{$c$}} (Q_1);
 \end{tikzpicture}\\\\
 \end{tabular}
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \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,
+{\centering%
->=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\only<1>{%
-\node[state, initial]  (q_0)  {$\mbox{}$};
+\begin{tikzpicture}[node distance=3mm,
-\node (r_1)  [right=of q_0] {$\ldots$};
+>=stealth',very thick,
-\only<1>{
+every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20}]
-\node[state, accepting]  (t_1)  [right=of r_1] {$\mbox{}$};
+\node[state, initial]  (Q_0)  {$\mbox{}$};
-\node[state, accepting]  (t_2)  [above=of t_1] {$\mbox{}$};
+\node[state, initial]  (Q_01) [below=1mm of Q_0] {$\mbox{}$};
-\node[state, accepting]  (t_3)  [below=of t_1] {$\mbox{}$};}
+\node[state, initial]  (Q_02) [above=1mm of Q_0] {$\mbox{}$};
-\only<2>{
+\node (R_1)  [right=of Q_0] {$\ldots$};
-\node[state]  (t_1)  [right=of r_1] {$\mbox{}$};
+\node[state, accepting]  (T_1)  [right=of R_1] {$\mbox{}$};
-\node[state]  (t_2)  [above=of t_1] {$\mbox{}$};
+\node[state, accepting]  (T_2)  [above=of T_1] {$\mbox{}$};
-\node[state]  (t_3)  [below=of t_1] {$\mbox{}$};}
+\node[state, accepting]  (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 (A_0)  [right=2.5cm of T_1] {$\mbox{}$};
-\node (b_1)  [right=of a_0] {$\ldots$};
+\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)] {};}
+\node (1) [rounded corners, inner sep=1mm, thick,
-\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)] {};}
+draw=black!60, fill=black!20, fit= (Q_0) (R_1) (T_1) (T_2) (T_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)] {};}
+\node (2) [rounded corners, inner sep=1mm, thick,
-\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}
+draw=black!60, fill=black!20, fit= (A_0) (b_1) (c_1) (c_2) (c_3)] {};
-\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}
+\node [yshift=2mm] at (1.north) {$r_1$};
-\only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}
+\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
 via $\epsilon$-transitions to the starting state of the second automaton.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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,
+\hspace{2cm}
->=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\only<1>{%
-\onslide<1>{\node at (0,0)  (1)  {$\mbox{}$};}
+\begin{tikzpicture}[node distance=3mm,
-\onslide<2>{\node at (0,0) [state, initial]  (1)  {$\mbox{}$};}
+>=stealth',very thick,
-\only<1>{
+every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
-\node[state, initial]  (2)  [above right=16mm of 1] {$\mbox{}$};
+baseline=(current bounding box.center)]
-\node[state, initial]  (3)  [below right=16mm of 1] {$\mbox{}$};}
+\node at (0,0)  (1)  {$\mbox{}$};
-\only<2>{
+\node  (2)  [above=14mm of 1] {};
-\node[state]  (2)  [above right=16mm of 1] {$\mbox{}$};
+\node[state, initial]  (4)  [above=1mm of 2] {$\mbox{}$};
-\node[state]  (3)  [below right=16mm of 1] {$\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{}$};
+\begin{pgfonlayer}{background}
+\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}}
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Case $r^*$}
+\onslide<1->{By recursion we are given an automaton for $r$:\smallskip}
+\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$};
 \node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};
 \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{}$};
-\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)] {};}
+\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)] {};}
+\node [yshift=3mm] at (1.north) {$r$};
-\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$}};}
 \end{pgfonlayer}
-\end{tikzpicture}
+\end{tikzpicture}}
+\only<2->{\begin{tikzpicture}[node distance=3mm,
-\small
+>=stealth',very thick,
-We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
+every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
-\end{frame}
+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{}$};
-\begin{frame}[c]
+\node[state]  (5)  [below=1mm of 2] {$\mbox{}$};
-\frametitle{Case $r^*$}
-\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{}$};}
 \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]  (a1)  [right=of a] {$\mbox{}$};
 \node[state]  (a2)  [above=of a1] {$\mbox{}$};
-\node[state]  (a3)  [below=of a1] {$\mbox{}$};}
+\node[state]  (a3)  [below=of a1] {$\mbox{}$};
-\only<2->{
+\path[->] (1) edge node [below]  {$\epsilon$} (4);
-\path[->] (1) edge node [above]  {\alert{$\epsilon$}} (2);
+\path[->] (1) edge node [below]  {$\epsilon$} (5);
-\path[->] (a1) edge [bend left=45] node [above]  {\alert{$\epsilon$}} (1);
+\path[->] (a1) edge [bend left=45] node [below]  {$\epsilon$} (1);
-\path[->] (a2) edge [bend right] node [below]  {\alert{$\epsilon$}} (1);
+\path[->] (a2) edge [bend right] node [below]  {$\epsilon$} (1);
-\path[->] (a3) edge [bend left=45] node [below]  {\alert{$\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)] {};}
+\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
-\only<2->{\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^*$};
-\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
-\only<2->{\node [yshift=3mm] at (2.north) {\bl{$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?}
 \end{frame}
 \frametitle{Subset Construction}
 \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,initial]  (Q_0)  {$\mbox{Q}_0$};
-\node[state] (q_1) [above=of q_0] {$q_1$};
+\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
-\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
+\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_1);
-\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);
+\path[->] (Q_0) edge node [left]  {\alert{$\epsilon$}} (Q_2);
-\path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();
+\path[->] (Q_0) edge [loop right] node  {\alert{$a$}} ();
-\path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();
+\path[->] (Q_1) edge [loop above] node  {\alert{$a$}} ();
-\path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();
+\path[->] (Q_2) edge [loop below] node  {\alert{$b$}} ();
 \end{tikzpicture}
 \end{center}
 \end{textblock}
 \begin{textblock}{11}(6.5,4.5)
 \end{tikzpicture}}
 &
 \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,initial]  (Q_0)  {$\mbox{Q}_0$};
-\node[state] (q_1) [above=of q_0] {$q_1$};
+\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
-\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
+\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_1);
-\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);
+\path[->] (Q_0) edge node [left]  {\alert{$\epsilon$}} (Q_2);
-\path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();
+\path[->] (Q_0) edge [loop right] node  {\alert{$a$}} ();
-\path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();
+\path[->] (Q_1) edge [loop above] node  {\alert{$a$}} ();
-\path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();
+\path[->] (Q_2) edge [loop below] node  {\alert{$b$}} ();
 \end{tikzpicture}
 \end{tabular}
 \end{center}
 \end{frame}
 \begin{frame}[c]
 \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,initial]  (Q_0)  {$\mbox{Q}_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
-\path[->] (q_0) edge node [above]  {\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_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_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);
 \end{tikzpicture}
 \end{center}
 \mbox{}\\[-20mm]\mbox{}
 \draw (1,0) -- (1, 4);
 \draw (2,0) -- (2, 3);
 \draw (3,0) -- (3, 2);
 \draw (4,0) -- (4, 1);
-\draw (0.5,-0.5) node {$q_0$};
+\draw (0.5,-0.5) node {$\mbox{Q}_0$};
-\draw (1.5,-0.5) node {$q_1$};
+\draw (1.5,-0.5) node {$\mbox{Q}_1$};
-\draw (2.5,-0.5) node {$q_2$};
+\draw (2.5,-0.5) node {$\mbox{Q}_2$};
-\draw (3.5,-0.5) node {$q_3$};
+\draw (3.5,-0.5) node {$\mbox{Q}_3$};
-\draw (-0.5, 3.5) node {$q_1$};
+\draw (-0.5, 3.5) node {$\mbox{Q}_1$};
-\draw (-0.5, 2.5) node {$q_2$};
+\draw (-0.5, 2.5) node {$\mbox{Q}_2$};
-\draw (-0.5, 1.5) node {$q_3$};
+\draw (-0.5, 1.5) node {$\mbox{Q}_3$};
-\draw (-0.5, 0.5) node {$q_4$};
+\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$};
 \draw (2.5,0.5) node {\large$\star$};
 \draw (3.5,0.5) node {\large$\star$};
 \begin{center}
 \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,initial]  (Q_0)  {$\mbox{Q}_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
+\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
+\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
-\path[->] (q_0) edge node [above]  {\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_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_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]
 \draw (0,0) -- (4,0);
 \draw (0,1) -- (4,1);
 \draw (1,0) -- (1, 4);
 \draw (2,0) -- (2, 3);
 \draw (3,0) -- (3, 2);
 \draw (4,0) -- (4, 1);
-\draw (0.5,-0.5) node {$q_0$};
+\draw (0.5,-0.5) node {$\mbox{Q}_0$};
-\draw (1.5,-0.5) node {$q_1$};
+\draw (1.5,-0.5) node {$\mbox{Q}_1$};
-\draw (2.5,-0.5) node {$q_2$};
+\draw (2.5,-0.5) node {$\mbox{Q}_2$};
-\draw (3.5,-0.5) node {$q_3$};
+\draw (3.5,-0.5) node {$\mbox{Q}_3$};
-\draw (-0.5, 3.5) node {$q_1$};
+\draw (-0.5, 3.5) node {$\mbox{Q}_1$};
-\draw (-0.5, 2.5) node {$q_2$};
+\draw (-0.5, 2.5) node {$\mbox{Q}_2$};
-\draw (-0.5, 1.5) node {$q_3$};
+\draw (-0.5, 1.5) node {$\mbox{Q}_3$};
-\draw (-0.5, 0.5) node {$q_4$};
+\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$};
 \draw (2.5,0.5) node {\large$\star$};
 \draw (3.5,0.5) node {\large$\star$};
 \mbox{}\\[-20mm]\mbox{}
 \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,initial]  (Q_02)  {$\mbox{Q}_{0, 2}$};
-\node[state] (q_13) [right=of q_02] {$q_{1, 3}$};
+\node[state] (Q_13) [right=of Q_02] {$\mbox{Q}_{1, 3}$};
-\node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};
+\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_02) edge [bend left] node [above]  {\alert{$a$}} (Q_13);
-\path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);
+\path[->] (Q_13) edge [bend left] node [below]  {\alert{$b$}} (Q_02);
-\path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();
+\path[->] (Q_02) edge [loop below] node  {\alert{$b$}} ();
-\path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);
+\path[->] (Q_13) edge node [above]  {\alert{$a$}} (Q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
+\path[->] (Q_4) edge [loop above] node  {\alert{$a, b$}} ();
 \end{tikzpicture}\\
 minimal automaton
 \end{center}
 \end{frame}
 \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}]
-\only<1>{\node[state,initial]  (q_0)  {$q_0$};}
+\only<1>{\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};}
-\only<2->{\node[state,accepting]  (q_0)  {$q_0$};}
+\only<2->{\node[state,accepting]  (Q_0)  {$\mbox{Q}_0$};}
-\node[state] (q_1) [right=of q_0] {$q_1$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
-\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}
+\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] {$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_0) edge node [above]  {\alert{$a$}} (Q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
+\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
+\path[->] (Q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
+\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
+\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
+\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
-\path[->] (q_0) edge node [above]  {\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_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_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_0) edge node [above]  {\alert{$a$}} (Q_1);
-\path[<-] (q_1) edge node [above]  {\alert{$a$}} (q_4);
+\path[<-] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);
-\path[<-] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
+\path[<-] (Q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[<-] (q_3) edge node [right]  {\alert{$a$}} (q_4);
+\path[<-] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);
-\path[<-] (q_2) edge node [above]  {\alert{$a$}} (q_3);
+\path[<-] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);
-\path[<-] (q_1) edge node [right]  {\alert{$b$}} (q_2);
+\path[<-] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);
-\path[<-] (q_0) edge node [above]  {\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_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_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);}
 \end{tikzpicture}
 \end{center}
 \mbox{}\\[-18mm]
 \small
 \frametitle{DFA to Rexp}
 \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, initial]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
-\only<2->{\node[state, initial,accepting]        (q0) at ( 0,1) {$q_0$};}
+\only<2->{\node[state, initial,accepting]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
-\only<1>{\node[state]                    (q1) at ( 1,1) {$q_1$};}
+\only<1>{\node[state]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
-\only<2->{\node[state,accepting]                    (q1) at ( 1,1) {$q_1$};}
+\only<2->{\node[state,accepting]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
-\only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
+\only<1>{\node[state, accepting] (q2) at ( 2,1) {$\mbox{Q}_2$};}
-\only<2->{\node[state] (q2) at ( 2,1) {$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)
 (q1) edge node[above] {\alert{$a$}} (q2)
 (q2) edge [loop right] node {\alert{$a$}} ()
 \begin{frame}[c]
 \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, initial]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
-\only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
+\only<1->{\node[state]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
-\only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+\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)
 (q1) edge node[above] {\alert{$a$}} (q2)
 (q2) edge [loop right] node {\alert{$a$}} ()
 \onslide<2->{
 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{$\mbox{Q}_0$} & \bl{$=$} & \bl{$2\, \mbox{Q}_0 + 3 \,\mbox{Q}_1 +  4\, \mbox{Q}_2$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$2 \,\mbox{Q}_0 + 3\, \mbox{Q}_1 + 1\, \mbox{Q}_2$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$1\, \mbox{Q}_0 + 5\, \mbox{Q}_1 + 2\, \mbox{Q}_2$}\\
 \end{tabular}
 \end{center}
 }
 \begin{frame}[c]
 \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, initial]        (q0) at ( 0,1) {$\mbox{Q}_0$};}
-\only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
+\only<1->{\node[state]                    (q1) at ( 1,1) {$\mbox{Q}_1$};}
-\only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+\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)
 (q1) edge node[above] {\alert{$a$}} (q2)
 (q2) edge [loop right] node {\alert{$a$}} ()
 \end{center}\bigskip
 \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{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b +  \mbox{Q}_2\,b$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
 \end{tabular}
 \end{center}
 }

changeset 515	3566c8175e63
parent 500	c502933be072
child 517	edab48a5b37e