W-Automata, Converting liveness automata to totally defined automata

Question

Example: August 2017 question 6c.

My assumption : we must convert the given liveness automatan to toally defined automatan using sync state before applying Subset construction. But in question 6c its applied in a similar way as we do for breakpoint construction.Is there a reason for that?

and the acceptance condition given is used to mark the states after construction right?

Also isn't Q0 of the construction an acceptance state? because every run from it either goes to nodes with s0 in it..?

Comments

What do you mean by “its applied in a similar way as we do for breakpoint construction”?

Answer 1

The acceptance condition is the standard condition for prefix automata: F(sates containing a formerly accepting state) ∧ G(!unsafe state).

Q0 is not an accepting state because it is a super state that does not contain at least one of the states s0, s1. The phrasing in the question said that runs are accepting if they visit such a super state at least once. That just meant the F of the acceptance condition. And such super states (that contains s0 or s1) are the once that should be marked as the accepting states of this F.

Answer 2

First of all: in general, it is not sufficient to make a partially defined NDet-F automaton totally defined using a sink state and then applying the subset construction. Slide 86 of the corresponding chapter discusses this: 

Now to question 6c of the mentioned exam. That automaton is very special; in part a) it should be observed that all states can be declared to be accepting states without changing the accepted language. That is why in part b) and c) also s2 and s3 are considered as accepting states. 

Part c) does not make any claim about general automata, and not even on this one. It just gives you commands to work out, and says that you should apply the subset construction (for whatever reason) and define an acceptance condition as explained there. Don't think too much about the why here, except for whether that may work in general, and the slides of the chapter will tell you that this is not the case. Det-FG is more expressive than Det-Prefix.

Moreover, 6c) says that you should apply the subset construction to the original automaton whose accepting states are only s0 and s1 (and neither s2 nor s3). That is why Q0:{s2,s3} is not accepting. Whether you could make it accepting without changing the language is another question. 

Comments

So in this case Can i convert the Non deterministic liveness automaton to Deterministic FG   by breakpoint construction since DetFG and DetF are expressive??

---

DetFG is more expressive than DetF, you mean that DetFG is equally expressive as NDetF. For this reason, every NDetF automaton can be converted to a DetFG automaton. However, it is not the case that you can just apply the breakpoint construction to the given NDetF automaton. You first have to convert it to an equivalent NDetFG automaton, and then you can apply the breakpoint construction.
In part a) of the exam problem, it was learned that we can make all states accepting for the coBüchi condition. Then, you can also make it a safety automaton where all four states are safe states. That one can be determined by the subset construction, so that this example can even be given as DetG automaton.
For particular variants of the constructions, see the updated solutions of the exam paper, in particular, you cannot apply the breakpoint construction to the generate a DetFG, since the word where a is always false will no longer be accepted.