8   It is now the time for use to discuss further about the way.

     8 

     9 The intuition behind our treatment is still automata. Taking the automaton in 

    10 Fig.\ref{fig_origin_auto} as an example, like any automaton, it

    11 represents the vehicle used to recognize a certain regular language.

    12 For any given string, the process starts from the left most and proceed 

    13 character by character to the right, driving the state transtion of automaton 

    14 starting from the initial state (the one marked by an short arrow). There could

    15 be three outcomes:

    16   \begin{enumerate}

    17    \item The process finally reaches the end of the string and the automaton is at an accepting

    18         state, in which case the string is considered a member of the language.

    19          For the automaton in Fig.\ref{fig_origin_auto}, @{text "a, ab, abb, abc, abbcc, b, baa"}

    20          are such kind of strings.

    21    \item The process finally reaches the end of the string but the automaton is at an non-accepting

    22          state, in which case, the string is considered a non-member of the language. For the automaton 

    23          in Fig.\ref{fig_origin_auto}, @{text "ad, abbd, adbd, bdabbccd"}

    24          are such kind of strings. \label{case_end_reject}

    25    \item \label{case_stuck}

    26      The process get stuck at the middle of the string, in which case, the string is considered

    27            a non-member of the lauguage.  For the automaton in Fig.\ref{fig_origin_auto}, 

    28            @{text "c, acb, bbacd, aaccd"} 

    29            are such kind of strings.

    30   \end{enumerate}

    31 To avoid the situation \ref{case_stuck} above, we can augment a normal automaton with a ``absorbing state'',

    32 as the state $X_3$ in Fig.\ref{fig_extended_auto}. In an auguments automaton, the process of strings never

    33 get stuck: whenever a string is recognized as not belonging to the language, the augmented automaton

    34 is transfered into the ``absorbing state'' and kept there until the process reaches the end of the string, 

    35 in which case, the string is rejected by situation \ref{case_end_reject} above.

    36 

    37 Given a language @{text "Lang"} and a string @{text "x"}, the equivalent class @{text "\<approx>Lang `` {x}"}

    38 corresponds to the state reached by processing @{text "x"} with the augmented automaton. 

    39 

    40 \begin{figure}[h!]

    41 \centering

    42 \subfigure[Original automaton]{\label{fig_origin_auto}

    43 \begin{minipage}{0.4\textwidth}

    44 \scalebox{0.8}{

    45 \begin{tikzpicture}[ultra thick,>=latex]

    46   \node[draw,circle,initial] (start) {$X_0$};

    47   \node[draw,circle,accepting] at ($(start) + (3.5cm,2cm)$) (ac1) {$X_1$};

    48   \node[draw,circle,accepting] at ($(start) + (3.5cm,-2cm)$) (ac2) {$X_2$};

    49 

    50   \path[->] (start) edge [bend left] node [midway, above] {$a$} (ac1);

    51   \path[->] (start) edge [bend right] node [midway, below] {$b$} (ac2);

    52   \path[->] (ac1) edge [loop above] node [midway, above] {$b$} (ac1);

    53   \path[->] (ac2) edge [loop below] node [midway, below] {$a$} (ac2);

    54   \path[->] (ac1) edge [bend right] node [midway, left] {$c$} (ac2);

    55   \path[->] (ac2) edge [bend right] node [midway, right] {$c$} (ac1);

    56   \path[->] (ac1) edge node [midway, sloped, above] {$d$} (start);

    57   \path[->] (ac2) edge node [midway, sloped, above] {$d$} (start);

    58 \end{tikzpicture}}

    59 \end{minipage}

    60 }

    61 \subfigure[Extended automaton]{\label{fig_extended_auto}

    62 \begin{minipage}{0.5\textwidth}

    63 \scalebox{0.8}{

    64 \begin{tikzpicture}[ultra thick,>=latex]

    65   \node[draw,circle,initial] (start) {$X_0$};

    66   \node[draw,circle,accepting] at ($(start) + (3.5cm,2cm)$) (ac1) {$X_1$};

    67   \node[draw,circle,accepting] at ($(start) + (3.5cm,-2cm)$) (ac2) {$X_2$};

    68   \node[draw,circle] at ($(start) + (6.5cm,0cm)$) (ab) {$X_3$};

    69 

    70   \path[->] (start) edge [bend left] node [midway, above] {$a$} (ac1);

    71   \path[->] (start) edge [bend right] node [midway, below] {$b$} (ac2);

    72   \path[->] (ac1) edge [loop above] node [midway, above] {$b$} (ac1);

    73   \path[->] (ac2) edge [loop below] node [midway, below] {$a$} (ac2);

    74   \path[->] (ac1) edge [bend right] node [midway, left] {$c$} (ac2);

    75   \path[->] (ac2) edge [bend right] node [midway, right] {$c$} (ac1);

    76   \path[->] (ac1) edge node [midway, sloped, above] {$d$} (start);

    77   \path[->] (ac2) edge node [midway, sloped, above] {$d$} (start);

    78 

    79   \path [draw, rounded corners,->,dashed] (start) -- ($(start) + (0cm, 3.7cm)$)

    80          -- ($(ab) + (0cm, 3.7cm)$)  node[midway,above,sloped]{$\Sigma - \{a, b\}$} -- (ab);

    81   \path[->,dashed] (ac1) edge node [midway, above, sloped] {$\Sigma - \{b,c,d\}$} (ab);

    82   \path[->,dashed] (ac2) edge node [midway, below, sloped] {$\Sigma - \{a,c,d\}$} (ab);

    83   \path[->,dashed] (ab) edge [loop right] node [midway, right] {$\Sigma$} (ab);

    84 \end{tikzpicture}}

    85 \end{minipage}

    86 }

    87 \caption{The relationship between automata and finite partition}\label{fig_auto_part_rel}

    88 \end{figure}

    89