2017.02.15 problem 6. Breakpoint construction.

Question

when to use robin/scott or breakpoint while determinizing the automata. In this problem how to interpret ϕF = FG(¬q1 ∧ q2)?. why there is a state transition from Q5 to Q6. Also, why Q5 contain {} as a accepting state set.

Answer 1

FG(¬q1 ∧ q2) means that we accept those paths that after finite time (F), stay forever (G) in the state set {s2} (only state satisfying ¬q1 ∧ q2)

We introduced q₅ as a successor of q₄. State q₄ represented {s1, s2} of which s2 was breakpoint-accepting. The successors of s2 (for input c1) are all non-accepting. Thus, the the chain of accepting states is broken, which resets the breakpoint-accepting states to the empty set {}. Thus, we introduce state q5 representing {s0, s1, s2, s3} and having no breakpoint-accepting states. From there on, we can only stay in this set of states. But since we currently have no breakpoint-accepting states, the accepting states in the successor are reevaluated. That's why we introduce state q6 that differs from q5 by having an accepting state.