Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| 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 { | ||
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.
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: 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.
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
GATECSE