Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
[http://condor.depaul.edu/glancast/444class/docs/nfa2dfa.html Conversion] | [http://condor.depaul.edu/glancast/444class/docs/nfa2dfa.html Conversion] | ||
| − | *'''Q:''' I know that $2^n$ are the maximum states in DFA for an n | + | *'''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. | 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. | ||
| Line 21: | Line 21: | ||
q1 -> q0 [label="b"]; | q1 -> q0 [label="b"]; | ||
} | } | ||
| − | + | </graphviz> | |
<graphviz caption='DFA'> | <graphviz caption='DFA'> | ||
digraph DFA { | digraph DFA { | ||
rankdir=LR; | rankdir=LR; | ||
node [shape = none] ""; | node [shape = none] ""; | ||
| − | node [shape = doublecircle] q1 | + | node [shape = doublecircle] q1; |
node [shape = circle]; | node [shape = circle]; | ||
| Line 35: | Line 35: | ||
q1 -> q0 [label="b"]; | q1 -> q0 [label="b"]; | ||
} | } | ||
| + | </graphviz> | ||
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.
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.
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