Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 9: | Line 9: | ||
<graphviz caption='NFA'> | <graphviz caption='NFA'> | ||
− | digraph | + | digraph NFA { |
rankdir=LR; | rankdir=LR; | ||
node [shape = none] ""; | node [shape = none] ""; | ||
Line 23: | Line 23: | ||
<graphviz caption='DFA'> | <graphviz caption='DFA'> | ||
− | digraph | + | 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]; | ||
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
<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"]; }
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
<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"]; }