Construction Of DFA

 

Construction Of DFA-

 

Type-01 Problems-

 

In Type-01 problems -  ending with a particular substring.

 

Steps to construct DFA-

 

Step-01:

 

• Determine the minimum number of states required in the DFA.
• Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE Calculate the length of substring. All strings ending with ‘n’ length substring will always require minimum (n+1) states in the DFA.

 

Step-02:

 

• Decide the strings for which DFA will be constructed.
• The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

• Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE While constructing a DFA, Always prefer to use the existing path. Create a new path only when there exists no path to go with.

 

Step-04:

 

• Send all the left possible combinations to the starting state.
• Do not send the left possible combinations over the dead state.