“The computer was born to solve problems that did not exist before.”

Random Posts

Monday, November 22, 2021

Optimization of DFA

To optimize the DFA you have to follow the various steps. These are as follows:

Step 1: Remove all the states that are unreachable from the initial state via any set of the transition of DFA.

Step 2: Draw the transition table for all pair of states.

Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states and T2 contains non-final states.

Step 4: Find the similar rows from T1 such that:

δ (q, a) = p  
δ (r, a) = p  

That means, find the two states which have same value of a and b and remove one of them.

Step 5: Repeat step 3 until there is no similar rows are available in the transition table T1.

Step 6: Repeat step 3 and step 4 for table T2 also.

Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the transition table of minimized DFA.

Example

Optimization of DFA

Solution:

Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.

Step 2: Draw the transition table for rest of the states.

Optimization of DFA 1

Step 3:

Now divide rows of transition table into two sets as:

1. One set contains those rows, which start from non-final sates:

Optimization of DFA 2

2. Other set contains those rows, which starts from final states.

Optimization of DFA 3

Step 4: Set 1 has no similar rows so set 1 will be the same.

Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to same state on 0 and 1. So skip q5 and then replace q5 by q3 in the rest.

Optimization of DFA 4

Step 6: Now combine set 1 and set 2 as:

Optimization of DFA 5

Now it is the transition table of minimized DFA.

Transition diagram of minimized DFA:

Optimization of DFA 6

         Fig: Minimized DFA


No comments:

Post a Comment

Post Top Ad

Your Ad Spot

Pages

SoraTemplates

Best Free and Premium Blogger Templates Provider.

Buy This Template