Translation of DFA to Regular Expressions

COMP218 Tutorials 2021-10-22

1. Convert from $\epsilon$-NFA to NFA:

   1. First keep track of the closures (The states that have epsilon transitions):

      • $CL(B)=(B,D)$
      • $CL(E)=(E,B,C,D)$

      Accept states include those that have an accept state in their closure.

      Then make a table of the transitions including epsilon transitions:

      	0	1
      $A$	$E,B,C,D$	$B,D$
      $B$	$\emptyset$	$C$
      $C$	$\emptyset$	$D$
      $D$	$\emptyset$	$\emptyset$
      $E$	$F$	$C,D$
      $F$	$D$	$\emptyset$

      This can then be drawn as a graph:

       stateDiagram-v2
       direction LR
       [*] --> A
       A --> E:0
       A --> B:0
       A --> C:0
       A --> D:0
       A --> B:1
       A --> D:1
       B --> C:1
       C --> D:1
       E --> F:0
       E --> C:1
       E --> D:1
       F --> D:0
       D --> [*]
       B --> [*]
       E --> [*]
      

   2. Another one:

      • $CL(1)=(1,2)$

      Then the table of transitions:

      	a	b
      0	1,2	2
      1	1,2	0
      2	1,2	0

      and then the associated graph:

       stateDiagram-v2
       direction LR
       [*] --> 0
       2 --> 1:a
       0 --> 1:a
       0 --> 2:a
       0 --> 2:b
       1 --> 0:b
       1 --> 1:a
       1 --> 2:a
       2 --> 2:a
       2 --> 0:b
       2 --> [*]
       1 --> [*]
      

2. Convert the following to GFAs