Difference between revisions of "NFA to DFA"

Line 9: Line 9:
  
 
<graphviz caption='NFA'>
 
<graphviz caption='NFA'>
−
digraph example2 {
+
digraph NFA {
 
rankdir=LR;
 
rankdir=LR;
 
node [shape = none] "";
 
node [shape = none] "";
Line 23: Line 23:
  
 
<graphviz caption='DFA'>
 
<graphviz caption='DFA'>
−
digraph example2 {
+
digraph DFA {
 
rankdir=LR;
 
rankdir=LR;
 
node [shape = none] "";
 
node [shape = none] "";
−
node [shape = doublecircle] q1;
+
node [shape = doublecircle] q1, q12;
 
node [shape = circle];
 
node [shape = circle];
  

Revision as of 22:53, 26 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?

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 NFA { 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"]; }

<graphviz caption='DFA'> digraph DFA { rankdir=LR; node [shape = none] ""; node [shape = doublecircle] q1, q12; node [shape = circle];

""-> q0; q0->q1 [label="a"]; q1->q0 [label="a"]; q1->q1 [label="a"]; q1 -> q0 [label="b"]; }

Retrieved from "https://gatecse.in/w/index.php?title=NFA_to_DFA&oldid=4141"

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?

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"]; }

<graphviz caption='DFA'> 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"]; }