Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 26: | Line 26: | ||
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]; | ||
""-> q0; | ""-> q0; | ||
q0->q1 [label="a"]; | q0->q1 [label="a"]; | ||
− | q1-> | + | q0->q3 [label="b"]; |
− | q1-> | + | q1->q12 [label="a"]; |
− | + | q1->q0 [label="b"]; | |
+ | q12 -> q0 [label="b"]; | ||
} | } | ||
</graphviz> | </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.
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: 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