2.7 Minimum Deterministic Finite Automata 77
(^0 0 1) O
L-2
1
X
0
1 0
c) u
(^0) 0, 1
Y
0 1 0 0 1 b
1 0
(^0) 0, f
0 0
------e----w--- l
(^0 0)
v
0
I
I I
-l ---;-- i
I I
I
I I I
8
I
I I 0 I I
I -we - I
1
I --e-----m------
l I I
0 0
I
I I I I
------------a-- I
I ---------------
I I I
I 0 0 0 0 I
I ---------m-e--- I l
I I ----- I I -----
I
0
I
I I I I i@):
----- l I ----- I I
Q Q
0 1 @
I ----- I
Figure 2.51: The third method.
there is an a E C such that (S(qi, a), S(qj, a>) has the value Ic - 1. We repeat
this process until no new pairs are marked in a stage. The pairs (ai, qj> which
remain unmarked must then satisfy qi RL qj.
For this example, the above table buildup process is shown in Figure 2.50.
The pairs of states which remain unmarked are (Qo, ql) and (qz, 43). 0
Solution 3. Instead of building a table to check the relation RF, we can also
do it directly on the transition diagram of AL Initially, we divide all states
into two blocks F and Q - F. Then, at each subsequent stage, we check every
block S of states. For every a E C, we consider S( qi , a) for all qi E S. If
they do not all belong to the same block, then we divide S into smaller blocks
according to their destination blocks; that is, if 6(qi, a) and S(qj, a) belong to
the same block but 6( qk , a> belongs to a different block, then qi and qj remain
in the same smaller block and qk belongs to a different smaller block. We
repeat this process until no block of states can be divided further.
The whole process on this example is shown in Figure 2.51. cl
Corollary 2.49 gives us a simple characterization of regular languages. It
is very useful in the analysis of the structure of regular languages. In the
following two examples, we show how to apply it to prove that a given language