Difference between revisions of "NFA to DFA"

Revision as of 20:54, 28 July 2014

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

@@ Line 12: / Line 12: @@
 rankdir=LR;
 node [shape = none] "";
-node [shape = doublecircle] q1;
+node [shape = doublecircle] q2;
 node [shape = circle];
-""-> q0;
+""-> q1;
-q0->q1 [label="a"];
+q1->q2 [label="a"];
-q1->q0 [label="a"];
+q1->q2 [label="a"];
-q1->q1 [label="a"];
+q2 -> q2 [label="b"];
-q1 -> q0 [label="b"];
 }
 </graphviz>
@@ Line 26: / Line 25: @@
 rankdir=LR;
 node [shape = none] "";
-node [shape = doublecircle] q1, q12;
+node [shape = doublecircle] q2, q12;
 node [shape = circle];
-""-> q0;
+""-> q1;
-q0->q1 [label="a"];
-q0->q3 [label="b"];
 q1->q12 [label="a"];
-q1->q0 [label="b"];
+q12->q12 [label="a"];
-q12 -> q0 [label="b"];
+q12->q2 [label="b"];
+q2->q2 [label="b"];
+q2 -> q3 [label="a"];
+q1 -> q3 [label="b"];
 }
 </graphviz>