Omega automaton determinisation

Question

I have some general doubts regarding automaton's determinisation.

1) NDetG -> DetG => By removing all unsafe states, then use subset construction.

 If the NDetG not fully defined also can we proceed like this? Or should we add a sink state?

2) NDetF partial , to determinise this, can we add a sink state then use subset construction?

 Or should we convert F to FG then use breakpoint?

Answer 1

For NDetG -> DetG, you can always use the subset construction after removing the unsafe states.

For NDetF, that is not always possible, at least it works for totally defined automata, and sometimes also for others, which is however not that easy to decide. The safe way for NDetF is therefore to convert it to NDetFG and to use the breakpoint construction to get a DetFG automaton. Note that some NDetF automata do not have equivalent DetF automata at all.

Comments

Yeah.. I understood. If it's fully defined also I can convert to NDetFG then breakpoint to get DetFG, that's also a valid case right?

---

Sure, that is always the safe way!

---

Thanks for the clarification. I understood it.