103 

   104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   105 \mode<presentation>{

   106 \begin{frame}<1-2>[c]

   107 

   108 \begin{center}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   125 \end{tikzpicture}

   126 \end{center}

   127 

   128 \mbox{}\\[-20mm]\mbox{}

   129 

   130 \begin{center}

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

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

   133 \node[state,initial]  (q_02)  {$q_{0, 2}$};

   134 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

   135 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

   136 \path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

   137 \path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

   138 \path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();

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

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

   141 \end{tikzpicture}\\

   142 minimal automaton

   143 \end{center}

   144 

   145 \end{frame}}

   146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   147 

   148 

   149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   150 \mode<presentation>{

   151 \begin{frame}[c]

   152 

   153 \begin{enumerate}

   154 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}

   155 \item Mark all pairs that are accepting and non-accepting states

   156 \item For  all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether

   157 \begin{center}

   158 \bl{($\delta$(q,c), $\delta$(p,c))}

   159 \end{center} 

   160 are marked. If yes, then also mark \bl{(q, p)} 

   161 \item Repeat last step until no chance.

   162 \item All unmarked pairs can be merged.

   163 \end{enumerate}

   164 

   165 \end{frame}}

   166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   167 

   168 

   169 

   170