466 

   467 As seen in the subset construction, the translation 

   468 of an NFA to a DFA can result in a rather ``inefficient'' 

   469 DFA. Meaning there are states that are not needed. A

   470 DFA can be \emph{minimised} by the following algorithm:

   471 

   472 \begin{enumerate}

   473 \item Take all pairs $(q, p)$ with $q \not= p$

   474 \item Mark all pairs that accepting and non-accepting states

   475 \item For all unmarked pairs $(q, p)$ and all characters $c$

   476       test whether 

   477       

   478       \begin{center} 

   479       $(\delta(q, c), \delta(p,c))$ 

   480       \end{center} 

   481       

   482       are marked. If there is one, then also mark $(q, p)$.

   483 \item Repeat last step until no change.

   484 \item All unmarked pairs can be merged.

   485 \end{enumerate}

   486 

   487 \noindent To illustrate this algorithm, consider the following 

   488 DFA.

   489 

   490 \begin{center}

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

   492                     every state/.style={minimum size=0pt,

   493                     inner sep=2pt,draw=blue!50,very thick,

   494                     fill=blue!20}]

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

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

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

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

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

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

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

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

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

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

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

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

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

   508 \path[->] (q_3) edge [bend left=95, looseness=1.3] node 

   509   [below]  {$b$} (q_0);

   510 \end{tikzpicture}

   511 \end{center}

   512 

   513 \noindent In Step 1 and 2 we consider essentially a triangle

   514 of the form

   515 

   516 \begin{center}

   517 \begin{tikzpicture}[scale=0.6,line width=0.8mm]

   518 \draw (0,0) -- (4,0);

   519 \draw (0,1) -- (4,1);

   520 \draw (0,2) -- (3,2);

   521 \draw (0,3) -- (2,3);

   522 \draw (0,4) -- (1,4);

   523 

   524 \draw (0,0) -- (0, 4);

   525 \draw (1,0) -- (1, 4);

   526 \draw (2,0) -- (2, 3);

   527 \draw (3,0) -- (3, 2);

   528 \draw (4,0) -- (4, 1);

   529 

   530 \draw (0.5,-0.5) node {$q_0$}; 

   531 \draw (1.5,-0.5) node {$q_1$}; 

   532 \draw (2.5,-0.5) node {$q_2$}; 

   533 \draw (3.5,-0.5) node {$q_3$};

   534  

   535 \draw (-0.5, 3.5) node {$q_1$}; 

   536 \draw (-0.5, 2.5) node {$q_2$}; 

   537 \draw (-0.5, 1.5) node {$q_3$}; 

   538 \draw (-0.5, 0.5) node {$q_4$}; 

   539 

   540 \draw (0.5,0.5) node {\large$\star$}; 

   541 \draw (1.5,0.5) node {\large$\star$}; 

   542 \draw (2.5,0.5) node {\large$\star$}; 

   543 \draw (3.5,0.5) node {\large$\star$};

   544 \end{tikzpicture}

   545 \end{center}

   546 

   547 \noindent where the lower row is filled with stars, because in

   548 the corresponding pairs there is always one state that is

   549 accepting ($q_4$) and a state that is non-accepting (the other

   550 states).

   551 

   552 Now in Step 3 we need to fill in more stars according whether 

   553 one of the next-state pairs are marked. We have to do this 

   554 for every unmarked field until there is no change anymore.

   555 This gives the triangle

   556 

   557 \begin{center}

   558 \begin{tikzpicture}[scale=0.6,line width=0.8mm]

   559 \draw (0,0) -- (4,0);

   560 \draw (0,1) -- (4,1);

   561 \draw (0,2) -- (3,2);

   562 \draw (0,3) -- (2,3);

   563 \draw (0,4) -- (1,4);

   564 

   565 \draw (0,0) -- (0, 4);

   566 \draw (1,0) -- (1, 4);

   567 \draw (2,0) -- (2, 3);

   568 \draw (3,0) -- (3, 2);

   569 \draw (4,0) -- (4, 1);

   570 

   571 \draw (0.5,-0.5) node {$q_0$}; 

   572 \draw (1.5,-0.5) node {$q_1$}; 

   573 \draw (2.5,-0.5) node {$q_2$}; 

   574 \draw (3.5,-0.5) node {$q_3$};

   575  

   576 \draw (-0.5, 3.5) node {$q_1$}; 

   577 \draw (-0.5, 2.5) node {$q_2$}; 

   578 \draw (-0.5, 1.5) node {$q_3$}; 

   579 \draw (-0.5, 0.5) node {$q_4$}; 

   580 

   581 \draw (0.5,0.5) node {\large$\star$}; 

   582 \draw (1.5,0.5) node {\large$\star$}; 

   583 \draw (2.5,0.5) node {\large$\star$}; 

   584 \draw (3.5,0.5) node {\large$\star$};

   585 \draw (0.5,1.5) node {\large$\star$}; 

   586 \draw (2.5,1.5) node {\large$\star$}; 

   587 \draw (0.5,3.5) node {\large$\star$}; 

   588 \draw (1.5,2.5) node {\large$\star$}; 

   589 \end{tikzpicture}

   590 \end{center}

   591 

   592 \noindent which means states $q_0$ and $q_2$, as well as $q_1$

   593 and $q_3$ can be merged. This gives the following minimal DFA

   594 

   595 \begin{center}

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

   597                     every state/.style={minimum size=0pt,

   598                     inner sep=2pt,draw=blue!50,very thick,

   599                     fill=blue!20}]

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

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

   602 \node[state, accepting] (q_4) [right=of q_13] 

   603   {$q_{4\phantom{,0}}$};

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

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

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

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

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

   609 \end{tikzpicture}

   610 \end{center}

   697 Not all languages are regular\ldots{}

   698 

   699