Doubt regarding Automaton

Question

I have doubt regarding NDetF automaton. In the below question, we were asked to Determinize the automaton. Because the given automaton is Partially defined we can either do:  create a sink state and then Rabin scott subset construction  OR convert NDetF to NDetFG and apply breakpoint construction. But how we can select one method over other? Is there any specific cases such that? But in this question when i tried Liveness automaton, the automata accepted the word a!a!a , which is invalid in the given automaton. How can we directly select the "NDetF to NDetFG and apply breakpoint construction" instead of other method? Could you please help to solve this issue?

Answer 1

The class NDetF is more expressive than the class DetF, hence, there are NDetF automata that cannot be converted to a DetF automaton. This is explained in the slides and also examples were given where the subset construction computes an automaton that is not equivalent to the given NDetF automaton. Sometimes making the NDetF automaton gives an equivalent automaton, but not always. So, you have to check whether the automaton you got with the sink state is equivalent to the original one. If so, you can apply the subset construction since that construction is safe for totally defined NDetF automata, but not for all the others.

If you add a sink state to the automaton you described, it will accept also any word a(!a)(!a)... which are words that are not accepted by the original automaton. Hence the subset construction does not work here.

The alternative to convert NDetF to NDetFG and then applying the breakpoint construction is always correct, thus maybe preferable, but you get more states by the breakpoint construction and the conversion from NDetF to NDetFG also introduces further states.

Comments

I got the point. Thanks for clarifying. Thank you, Professor.