350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   351 \begin{frame}[c]

   352 \frametitle{DFAs}  

   353 

   354 \begin{center}

   355 \begin{tikzpicture}[>=stealth',very thick,auto,

   356   every state/.style={minimum size=0pt,inner sep=2pt,

   357     draw=blue!50,very thick,fill=blue!20},]

   358   

   359 \only<1,3->{\node[state,initial] (Q_0)  {$\mbox{Q}_0$};}

   360 \only<2>{\node[state,initial,fill=red] (Q_0)  {$\mbox{Q}_0$};}  

   361 \only<1,2,4->{\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}

   362 \only<3>{\node[state,fill=red] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}

   363 \only<-3,5->{\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}

   364 \only<4>{\node[state,fill=red] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}

   365 \only<-4,6->{\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}

   366 \only<5>{\node[state,fill=red] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}

   367 \only<-5>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}

   368 \only<6->{\node[state, accepting,fill=red] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}

   369 

   370 \path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);

   371 \path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);

   372 \path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();

   373 \path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);

   374 \path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);

   375 \path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);

   376 \path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);

   377 \path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();

   378 \path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);

   379 \end{tikzpicture}

   380 \end{center}

   381 

   382 \begin{textblock}{9}(4,12)

   383 \LARGE{}

   384 \only<3->{\boldmath\alert{$a$}}%

   385 \only<4->{\boldmath\alert{$b$}}%

   386 \only<5->{\boldmath\alert{$a$}}%

   387 \only<6->{\boldmath\alert{$a$}}%

   388 \only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}% 

   389 \end{textblock}

   390   

   391 \end{frame}

   392 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   393 

   394 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   395 \begin{frame}[t]

   396 \frametitle{DFAs}

   397 

   398 A \alert{\bf deterministic finite automaton}, DFA, consists of

   399 5 things:

   400 

   401 \begin{itemize}

   402 \item an alphabet \bl{$\varSigma$}  

   403 \item a set of states \bl{$\mbox{Qs}$}

   404 \item one of these states is the start state \bl{$\mbox{Q}_0$}

   405 \item some states are accepting states \bl{$F$}, and

   406 \item there is transition function \bl{$\delta$}\bigskip 

   407 

   408 \small

   409 which takes a state  and a character as arguments and produces a 

   410 new state; this function might not be everywhere defined 

   411 \end{itemize}

   412 

   413 \begin{center}

   414 \bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}

   415 \end{center}

   416 

   417 \end{frame}

   418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   419 

   420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   421 \begin{frame}[c]

   422 \frametitle{NFAs}  

   423 

   424 \begin{center}

   425 \begin{tikzpicture}[>=stealth',very thick, auto,

   426     every state/.style={minimum size=0pt,inner sep=3pt,

   427       draw=blue!50,very thick,fill=blue!20},scale=2]

   428 \node[state,initial]  (Q_0)  {$\mbox{Q}_0$};

   429 \node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};

   430 \node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};

   431 \path[->] (Q_0) edge [loop above] node  {\alert{$b$}} ();

   432 \path[<-] (Q_0) edge node [below]  {\alert{$b$}} (Q_1);

   433 \path[->] (Q_0) edge [bend left] node [above]  {\alert{$a$}} (Q_1);

   434 \path[->] (Q_0) edge [bend right=45,looseness=1.3] node [below]  {\alert{$a$}} (Q_2);

   435 \path[->] (Q_1) edge [loop above] node  {\alert{$a,b$}} ();

   436 \path[->] (Q_1) edge node  [above] {\alert{$a$}} (Q_2);

   437 \end{tikzpicture}

   438 \end{center}

   439 

   440 \end{frame}

   441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   442