Minimize the following DFA using table filling method or Myhill-Nerode Theoram

 Minimize  the following DFA using table filling method or Myhill-Nerode Theoram

Solution:

The steps to be followed:

STEP 1: Draw a table for all pairs of points:

	A	B	C	D	E
A
B
C
D
E

The cells that are not required are painted red.

STEP 2: Mark all the pairs ( with green ) which involves one state final state and another one non final state.

	A	B	C	D	E
A
B
C
D
E

 

STEP 3: Now, iterate over all the unmarked pairs, if there is any pair that shows transition to a pair that is already marked after taking the inputs, mark the pair else leave without any change.

1) (B,A) => δ ( B,0) : B

                    δ ( A,0): B

                    BB is not marked.

                    δ( B,1) : D

                    δ ( A,1 ): C

                    DC is not marked.

2) (C,A) => δ ( C,0): B

                    δ ( A,0 ): B

                    BB is not marked.

                    δ ( C, 1): C

                    δ ( A, 1): C

                    CC is not marked.

3) ( C, B) => δ ( C, 0): B

                      δ ( B,0) : B

                     BB is not marked

                       δ( C,1): C

                       δ( B,1): D

                     CD  is not marked

4) ( D, A)=>  δ ( D,1 ): E

                       δ (A,1):  C

                       EC is already marked. So, mark DA

                           

	A	B	C	D	E
A
B
C
D
E

5) ( D, B)=> δ( D,0): B

                    δ ( B,0): B

                    BB is not marked.

                    δ( D,1): E

                    δ( B,1): D

                    ED is already marked. So, mark DB 

	A	B	C	D	E
A
B
C
D
E

6) ( D, C)=> δ( D, 0): B

                     δ( C,0 ) : B

                      BB is not marked.

                    δ (D, 1): E

                    δ ( C, 1): C

                    EC is already marked. So, mark DC

	A	B	C	D	E
A
B
C
D
E

 Repeat the process again 

7) ( B,A): δ ( B, 0) : B

                 δ( A,0) : B

                BB is not marked.

                δ (B, 1): D

                δ( A, 1): C

                DC is already marked, so mark BA.

	A	B	C	D	E
A
B
C
D
E

8) (C,A) => δ ( C,0): B

                    δ ( A,0 ): B

                    BB is not marked.

                    δ ( C, 1): C

                    δ ( A, 1): C

                    CC is not marked.

9) 3) ( C, B) => δ ( C, 0): B

                      δ ( B,0) : B

                     BB is not marked

                       δ( C,1): C

                       δ( B,1): D

                    DC is already marked, so mark CB

	A	B	C	D	E
A
B
C
D
E

We can see that CA can not be marked, no matter how iterations we made.

STEP 4: Combine the unmarked pairs as single state i.e. C and A will be combined as CA. Now, draw the DFA.