Module 3 Exercise Solutions

    13.  Convert the following to a DFA.
    Let's create a table of e-transitions:
 
 state  e-transition state
 0  0
 1  1,2,3,5,7
 2  2,3,5
 3  3
 4  4,7,2,3,5
 5  5
 6  6,7,2,3,5
 7  7,2,3,5
 8  8
 
 
 state
 $
 LD
 0
 1' = {1,2,3,5,7}
 -
 1
 2' = {4,7,2,3,5,8}
 3' = {6,7,2,3,5}
 2
 {8,4,7,2,3,5} = 2'
 {6,7,2,3,5} = 3'
 3
 {8,4,7,2,3,5} = 2'
 {6,7,2,3,5} = 3'
 
 
New States:
0' = {0}
1' = {1,2,3,5,7}
2' = {2,3,4,5,7,8}
3' = {2,3,4,6,7}
 
    We can draw this new DFA as a transition diagram using the states 0', 1', 2', and 3':
    14.  Convert the following to a minimal DFA.
 
 
 
a
b
>A 
B
 A,D,F
B 
 
C,F 
 C 
A
G,D
D 
E
E,D,H
E 
 
F
*F 
 
D,H
G 
B
G,D,H
*H 
 
 
 
    Step 1:
     
     
    a
    b
    >A 
     
     
     
     
     
     
     
     
     
     
     
    Step 2:
     
     
    a
    b
     
    a
    b
     
     a
     b
    >A 
    B
    ADF
    >A
    B
     ADF
    >A
     B
     ADF
    B 
     
     
    B
     
    CF 
    B
     
    CF 
     ADF 
     
     
    *ADF
    BE
    ADEFH
    *ADF
    BE
     ADEFH
     
     
     
    Þ
    CF
     
     
    		 Þ
    *CF
    A
    DGH 
     
     
     
    BE
     
     
    BE
     
     CF
     
     
     
    ADEFH
     
     
    *ADEFH
     BE
    ADEFH 
     
     
     
     
     
     
    *DGH
     BE
    DEGH
     
     
     
     
     
     
    *DEGH
     BE
    DEFGH
     
     
     
    *DEFGH
    BE
    DEFGH
     
    The result of Step 2  is a DFA.

    Now let's minimize it.

    Step 1:

     
     
     a
     b
    >A
     B
     ADF
    B
     
    CF 
    BE
     
    CF
    - - - -  - - - - -  - - - - -
    *CF
    A
    DGH 
    *ADF
     BE
     ADEFH
    *ADEFH
     BE
    ADEFH 
    *DGH
     BE
    DEGH
    *DEGH
     BE
    DEFGH
    *DEFGH
    BE
    DEFGH
    Step 2:
     
     
     a
     b
    >A
     B
     ADF
    - - - -  - - - - -  - - - - -
    B
     
    CF 
    BE
     
    CF
    - - - - - - - - - - - - -  - - - - - - - 
    *CF
    A
    DGH 
    *ADF
     BE
     ADEFH
    *ADEFH
     BE
    ADEFH 
    *DGH
     BE
    DEGH
    *DEGH
     BE
    DEFGH
    *DEFGH
    BE
    DEFGH
     
    Step 3:
     
     
     a
     b
    >A
     B
     ADF
    - - - - - - - - - - - - - - - - - - - -
    B
     
    CF 
    BE
     
    CF
    - - - - - - - - - - - - -  - - - - - - - 
    *CF
    A
    DGH 
    - - - - - - - - - - - - - -
    *ADF
     BE
     ADEFH
    *ADEFH
     BE
    ADEFH 
    *DGH
     BE
    DEGH
    *DEGH
     BE
    DEFGH
    *DEFGH
    BE
    DEFGH
     
    Step 4:
     
     
     a
     b
    >A
    B
    D
    B
     
    C
    *C
    A
    D
    *D
    B
    D