439 \includegraphics[scale=0.7]{pics/ch3.jpg}

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

   442                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   443 \node[state,initial]  (q_0)  {$q_0$};

   444 \node[state] (q_1) [right=of q_0] {$q_1$};

   445 \node[state] (q_2) [below right=of q_0] {$q_2$};

   446 \node[state] (q_3) [right=of q_2] {$q_3$};

   447 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   448 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   449 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

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

   451 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   452 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   453 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   454 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

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

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

   457 \end{tikzpicture}

   456 \includegraphics[scale=0.7]{pics/ch3.jpg}

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

   476                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   477 \node[state,initial]  (q_0)  {$q_0$};

   478 \node[state] (q_1) [right=of q_0] {$q_1$};

   479 \node[state] (q_2) [below right=of q_0] {$q_2$};

   480 \node[state] (q_3) [right=of q_2] {$q_3$};

   481 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   482 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   483 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

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

   485 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   486 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   487 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   488 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

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

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

   491 \end{tikzpicture}

   463 \bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\

   498 \bl{$(q_0, a) \rightarrow q_1$} & \bl{$(q_1, a) \rightarrow q_4$} & \bl{$(q_4, a) \rightarrow q_4$}\\

   464 \bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\

   499 \bl{$(q_0, b) \rightarrow q_2$} & \bl{$(q_1, b) \rightarrow q_2$} & \bl{$(q_4, b) \rightarrow q_4$}\\

   518 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\

   553 \bl{$(q_1, a) \rightarrow q_2$}\\

   519 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\

   554 \bl{$(q_1, a) \rightarrow q_3$}\\

   523 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\

   558 \bl{$(q_1, \epsilon) \rightarrow q_2$}\\

   533 \frametitle{An NFA}

   568 \frametitle{An NFA Example}

   556 

   591 \frametitle{Rexp to NFA}

   557 \begin{center}

   592 

   558 \begin{tabular}[b]{ll}

   593 \begin{center}

   559 \bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\

   594 \begin{tabular}[t]{l@{\hspace{10mm}}l}

   560 \bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\

   595 \raisebox{1mm}{\bl{$\varnothing$}} & 

   561 \bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\

   596 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   597 \node[state, initial]  (q_0)  {$\mbox{}$};

   598 \end{tikzpicture}\\\\

   599 \raisebox{1mm}{\bl{$\epsilon$}} & 

   600 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   601 \node[state, initial, accepting]  (q_0)  {$\mbox{}$};

   602 \end{tikzpicture}\\\\

   603 \raisebox{2mm}{\bl{$c$}} & 

   604 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   605 \node[state, initial]  (q_0)  {$\mbox{}$};

   606 \node[state, accepting]  (q_1)  [right=of q_0] {$\mbox{}$};

   607 \path[->] (q_0) edge node [below]  {\alert{$c$}} (q_1);

   608 \end{tikzpicture}\\\\

   570 \begin{frame}[c]

   617 \begin{frame}[t]

   571 

   618 \frametitle{Case $r_1\cdot r_2$}

   572 \begin{center}

   619 

   573 \begin{tabular}[t]{ll}

   620 \mbox{}\bigskip

   574 \bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\

   621 \onslide<1>{By recursion we are given two automata:\bigskip}

   575 \end{tabular}

   622 

   576 \end{center}

   623 \begin{tikzpicture}[node distance=3mm,

   577 

   624                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   578 \end{frame}}

   625 \node[state, initial]  (q_0)  {$\mbox{}$};

   579 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   626 \node (r_1)  [right=of q_0] {$\ldots$};

   580 

   627 \only<1>{

   581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   628 \node[state, accepting]  (t_1)  [right=of r_1] {$\mbox{}$};

   582 \mode<presentation>{

   629 \node[state, accepting]  (t_2)  [above=of t_1] {$\mbox{}$};

   583 \begin{frame}[c]

   630 \node[state, accepting]  (t_3)  [below=of t_1] {$\mbox{}$};}

   584 

   631 \only<2>{

   585 \begin{center}

   632 \node[state]  (t_1)  [right=of r_1] {$\mbox{}$};

   586 \begin{tabular}[t]{ll}

   633 \node[state]  (t_2)  [above=of t_1] {$\mbox{}$};

   587 \bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\

   634 \node[state]  (t_3)  [below=of t_1] {$\mbox{}$};}

   588 \end{tabular}

   635 \only<1>{\node[state, initial]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};}

   589 \end{center}

   636 \only<2>{\node[state]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};}

   590 

   637 \node (b_1)  [right=of a_0] {$\ldots$};

   591 \end{frame}}

   638 \node[state, accepting]  (c_1)  [right=of b_1] {$\mbox{}$};

   592 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   639 \node[state, accepting]  (c_2)  [above=of c_1] {$\mbox{}$};

   593 

   640 \node[state, accepting]  (c_3)  [below=of c_1] {$\mbox{}$};

   594 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   641 \only<2>{

   595 \mode<presentation>{

   642 \path[->] (t_1) edge node [above, pos=0.3]  {\alert{$\epsilon$}} (a_0);

   596 \begin{frame}[c]

   643 \path[->] (t_2) edge node [above]  {\alert{$\epsilon$}} (a_0);

   644 \path[->] (t_3) edge node [below]  {\alert{$\epsilon$}} (a_0);

   645 }

   646 \begin{pgfonlayer}{background}

   647 \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)] {};}

   648 \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)] {};}

   649 \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)] {};}

   650 \only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}

   651 \only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}

   652 \only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}

   653 \end{pgfonlayer}

   654 \end{tikzpicture}\bigskip\bigskip

   655 

   656 \small

   657 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them

   658 via $\epsilon$-transitions to the starting state of the second automaton. 

   659 

   660 \end{frame}}

   661 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   662 

   663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   664 \mode<presentation>{

   665 \begin{frame}[t]

   666 \frametitle{Case $r_1+ r_2$}

   667 

   668 \onslide<1>{By recursion we are given two automata:\smallskip}

   669 

   670 \begin{tikzpicture}[node distance=3mm,

   671                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   672 \onslide<1>{\node at (0,0)  (1)  {$\mbox{}$};}

   673 \onslide<2>{\node at (0,0) [state, initial]  (1)  {$\mbox{}$};}

   674 \only<1>{

   675 \node[state, initial]  (2)  [above right=16mm of 1] {$\mbox{}$};

   676 \node[state, initial]  (3)  [below right=16mm of 1] {$\mbox{}$};}

   677 \only<2>{

   678 \node[state]  (2)  [above right=16mm of 1] {$\mbox{}$};

   679 \node[state]  (3)  [below right=16mm of 1] {$\mbox{}$};}

   680 

   681 \node (a)  [right=of 2] {$\ldots$};

   682 \node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};

   683 \node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};

   684 \node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};

   685 

   686 \node (b)  [right=of 3] {$\ldots$};

   687 \node[state, accepting]  (b1)  [right=of b] {$\mbox{}$};

   688 \node[state, accepting]  (b2)  [above=of b1] {$\mbox{}$};

   689 \node[state, accepting]  (b3)  [below=of b1] {$\mbox{}$};

   690 \only<2>{

   691 \path[->] (1) edge node [above]  {\alert{$\epsilon$}} (2);

   692 \path[->] (1) edge node [below]  {\alert{$\epsilon$}} (3);

   693 }

   694 \begin{pgfonlayer}{background}

   695 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}

   696 \only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}

   697 \only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}

   698 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}

   699 \only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}

   700 \only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}

   701 \end{pgfonlayer}

   702 \end{tikzpicture}

   703 

   704 \small

   705 We (1) need to introduce a new starting state and (2) connect it to the original two starting states.

   706 \end{frame}}

   707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   708 

   709 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   710 \mode<presentation>{

   711 \begin{frame}[c]

   712 \frametitle{Rexp to NFA}