1
$\begingroup$

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an DFA which is NOT minimal (the min. automata have 2 states ) but det(rev(A)) is the same automata (obviously det(rev(det(rev(A))) is also the same). Can you tell me what am I doing wrong ? Tnx. enter image description here

$\endgroup$
1
$\begingroup$

Your initial automaton has two final states. Its reverse should have two initial states. You wanted to avoid that, and added a new initial state.

The proper construction just uses the two initial states. The determinization algorithm can handle that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.