(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...")
 
 
(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$$  state NFA. But what about the minimum no of states in a DFA for an $n$ state NFA?
+
*'''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 example2 {
+
digraph NFA {
 
rankdir=LR;
 
rankdir=LR;
 
node [shape = none] "";
 
node [shape = none] "";
node [shape = doublecircle] q1;
+
node [shape = doublecircle] q2;
 
node [shape = circle];
 
node [shape = circle];
  
""-> q0;
+
""-> q1;
q0->q1 [label="a"];
 
q1->q0 [label="a"];
 
 
q1->q1 [label="a"];
 
q1->q1 [label="a"];
q1 -> q0 [label="b"];
+
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>

Latest revision as of 21:02, 28 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?

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

NFA

DFA

DFA

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