## Conversion from NFA to DFA (Thompson’s rule)

Again Freestudy9 has come back with new post related to the Conversion from NFA to DFA (Thompson’s rule). Additionally, we have a new post very soon.

### (a+b)*abb [Conversion from NFA to DFA (Thompson’s rule)]

- ε – closure (0) = {0,1,2,4,7} —- Let A
- Move(A,a) = {3,8}

ε – closure (Move(A,a)) = {1,2,3,4,6,7,8} Let B{1,2,3,4,6,7,8}

Move(A,b) = {5}

ε – closure (Move(A,b)) = {1,2,4,5,6,7} Let C{1,2,4,5,6,7}

- Move(C,a) = {3,8}

ε – closure (Move(C,a)) = {1, 2, 3, 4, 6, 7, 8} B{1, 2, 3, 4, 6, 7, 8}

Move(C,b) = {5}

ε – closure (Move(C,b)) = {1,2,4,5,6,7} C{1,2,4,5,6,7}

- Move(B,a) = {3,8}

ε – closure (Move(B,a)) = {1,2,3,4,6,7,8} B{1,2,3,4,6,7,8}

Move(B,b) = {5,9}

ε – closure (Move(B(Move(B,b)) = {1,2,4,5,6,7,9}

Let D

- Move(D,a) = {3,8}

ε – closure (Move(D, a)) = {1,2,3,4,6,7,8} B{1,2,3,4,6,7,8}

Move(D,b) = {5,10}

ε – closure (Move(D,b)) = {1,2,4,5,6,7,10} Let E{1,2,4,5,6,7,10}

- Move(E,a) = {3,8}

ε – closure (Move(E,a)) = {1,2,3,4,6,7,8} B{1,2,3,4,6,7,8}

Move(E,b) = {5}

ε – closure (Move(E,b)) = {1,2,4,5,6,7} C{1,2,4,5,6,7}

### DFA Optimization (Conversion from NFA to DFA (Thompson’s rule)

The algorithm for minimizing the number of states of a DFA Algorithm

- Construct an initial partition Π of the set of states with two groups: the accepting states F and the non-accepting states S – F.accepting
- Apply the repartition procedure to Π to construct a new partition Πnew.
- If Π new = Π, let Πfinal= Π and continue with step-4 Otherwise, repeat step (2) with ΠΠfinal== Πnew.
- for each group G of Π do begin partition G into subgroups such that two states s and t of G in the same subgroup if and only if for all input symbols a, states s and t have transitions on a to states in the same group of Π.
- replace G in Πnew by the set of all subgroups formed

- Choose one state in each group of the partition Πfinal as the representative for that group. The representatives will be the states of M’. Let s be a representative state, and suppose on input a there is a transition of M from s to t. Let r be the representative of t’s group. Then M’ has a transition from s to r on a. Let the start state of M’ be the representative of the group contain start state s0 of M, and let the accepting states of containing M’ be the representatives that are in F.
- If M’ has a dead stated (non accepting, all transitions to self), then remove d from M non-accepting, Also remove any state not reachable from the start state.

### Example for Thompson’s rule

Consider the transition table of the above example and apply the algorithm.

- An initial partition consists of two groups (E) accepting state and non-accepting states (ABCD).
- E is the single state so, cannot be split further.
- For (ABCD), an input, an each of these statements has transitioned to B. but on input b. however, A, B, and C go to the member of the group (ABCD), while D goes to E, a member of other groups.
- Thus, (ABCD) split into two groups, (ABC) and (D). so, new groups are (ABC)(D) and (E).
- Apply same procedure again no splitting on input a, but (ABC) must be splitting into procedure group (AC) and (B), since on input b, A and C each have a transition to C, while B has transitioned to D. So, new groups (AC)(B)(D)(E). Now, no more splitting is possible.
- If we chose A as the representative for a group (AC), then we obtain a reduced true transition

**Related Search**

Compiler Design, Regular Expression, Finite Automata, Free Study.

## Leave a Reply