VRS Exam [August 31, 2021] - Problem 5.b - Determinize the NDetF automaton

Question

In the solution [Link here], 

The acceptance condition of the automaton is changed to FG and then breakpoint construction is applied. Although, we also have another method to determinize it by totaling the NDet_F(partial) and then applying subset construction which does not always work.

How do we know before applying the subset construction that it will not work for the given automaton?

Answer 1

That question is discussed on pages 90-91 of the related chapter in the lecture slides. In general, if the language of the automaton does not change when making it totally defined, then you can work with the subset construction afterwards. Whether that is the case, is not that easy to check in general, but in many cases, it can be easily seen. The safe way that always works is the way over NDetFG and the breakpoint construction.