Is the following statement True or False When an NDFA M1 is

Is the following statement True or False?

When an NDFA M1 is converted into an equivalent DFA M2, then the number of states in the DFA is guaranteed to be minimal.

Please explain. Thanks a lot for your help!!!

Solution

Answer:

It is not guaranteed to be minimal but minimal DFA can be exponentially larger than DFA . In NDFA transition from one state to multiple states but in DFA transition can be from one state to only one state at a time thus we can say that DFA is more minimal than NFA , but is is not guaranteed that we will get minimal DFA. Yes , the possibility of minimal DFA is exponential than NFA.