Arjun Suresh (talk | contribs) (Created page with "[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$$ state NFA. But what about the minimum...") |
Arjun Suresh (talk | contribs) |
||
(9 intermediate revisions by the same user not shown) | |||
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. | ||
− | 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? |
− | 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 | + | digraph NFA { |
rankdir=LR; | rankdir=LR; | ||
node [shape = none] ""; | node [shape = none] ""; | ||
− | node [shape = doublecircle] | + | node [shape = doublecircle] q2; |
node [shape = circle]; | node [shape = circle]; | ||
− | "" | + | ""-> q1; |
− | |||
− | |||
q1->q1 [label="a"]; | q1->q1 [label="a"]; | ||
− | q1 -> | + | q1->q2 [label="a"]; |
+ | q2 -> q2 [label="b"]; | ||
+ | } | ||
+ | </graphviz> | ||
+ | |||
+ | ===DFA=== | ||
+ | <graphviz caption='DFA'> | ||
+ | digraph DFA { | ||
+ | rankdir=LR; | ||
+ | node [shape = none] ""; | ||
+ | node [shape = doublecircle] q2, q12; | ||
+ | node [shape = circle]; | ||
+ | |||
+ | ""-> q1; | ||
+ | q1->q12 [label="a"]; | ||
+ | q12->q12 [label="a"]; | ||
+ | q12->q2 [label="b"]; | ||
+ | q2->q2 [label="b"]; | ||
+ | q2 -> q3 [label="a"]; | ||
+ | q1 -> q3 [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.
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
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? In the worst case this can remain $2^n$ - that is no minimization can be possible. We can see this in the following example
<graphviz caption='NFA'> digraph example2 { rankdir=LR; node [shape = none] ""; node [shape = doublecircle] q1; node [shape = circle];
""-> q0; q0->q1 [label="a"]; q1->q0 [label="a"]; q1->q1 [label="a"]; q1 -> q0 [label="b"]; }