Line 7: Line 7:
 
*'''Q:''' After converting from  NFA to DFA and  we get $2^n$ states. Now we apply minimization- how many states can we get after this?  
 
*'''Q:''' After converting from  NFA to DFA and  we get $2^n$ states. Now we apply minimization- how many states can we get after this?  
 
A: In the worst case this can remain $2^n$ - that is no minimization can be possible. We can see this in the following example  
 
A: In the worst case this can remain $2^n$ - that is no minimization can be possible. We can see this in the following example  
 
+
===NFA===
 
<graphviz caption='NFA'>
 
<graphviz caption='NFA'>
 
digraph NFA {
 
digraph NFA {
Line 21: Line 21:
 
}
 
}
 
</graphviz>
 
</graphviz>
 +
 +
===DFA===
 
<graphviz caption='DFA'>
 
<graphviz caption='DFA'>
 
digraph DFA {
 
digraph DFA {

Revision as of 20:55, 28 July 2014

Conversion

  • Q: I know that $2^n$ are the maximum states in DFA for an $n$ state NFA. But what about the minimum no of states in a DFA for an $n$ state NFA?

A: I would say 1 because the $n$ states can be connected through $ε$ moves and hence all of these will be combines to a single start state in DFA.

  • Q: After converting from NFA to DFA and we get $2^n$ states. Now we apply minimization- how many states can we get after this?

A: In the worst case this can remain $2^n$ - that is no minimization can be possible. We can see this in the following example

NFA

NFA

DFA

DFA

Conversion

  • Q: I know that $2^n$ are the maximum states in DFA for an $n$ state NFA. But what about the minimum no of states in a DFA for an $n$ state NFA?

A: I would say 1 because the $n$ states can be connected through $ε$ moves and hence all of these will be combines to a single start state in DFA.

  • Q: After converting from NFA to DFA and we get $2^n$ states. Now we apply minimization- how many states can we get after this?

A: In the worst case this can remain $2^n$ - that is no minimization can be possible. We can see this in the following example

NFA[edit]

NFA

DFA[edit]

DFA