# Prob 6 NDet FG (SEP 2022) breakpoint construction

In the following breakpoint construction from

Ndet Automata A

to

Det Automata B

we have a transition in Automata B
transition(q2,b,q3)
Because in Automata A there exists no
transition(s3,b,s3)

And also we have a transition in Automata B
transition(q1,!a,q1)
There is a transition in Automata A
transition(s0,!a,s0) and a
transition(s1,!a&!b,s1)
therefore their combination in Automata B would be

transition(q1,!a&!a&!b,q1) <-> transition(q1,!a&!b,q1)

What is going wrong over here such that I am not able to arrive at the same answer as Automata B?

+1 vote

Don't confuse the breakpoint construction with the product structure of two Kripke structures or automata. In the breakpoint construction, there is a transition from a state A := {sa, sb, ...} to a state B :=  {si, sj, ...} with input x if you can reach each element of B from at least one state of A via input x. So not all states of A need to be able to react to input x! It suffices if there is one state that is able to react to x and in total all states of B need to be reached somehow by any state of A.

So to have a concrete example:

If you start at s2 and get the input b you can either go to s2 or to s3

=> reachable(s2, b) = {s2, s3}

If you start at s3 and get the input b there is no possible transition

=> reachable(s3, b) = {}

From that we get:

reachable({s2, s3}, b) = reachable(s2, b) U reachable(s3, b) = {s2, s3} U {} = {s2, s3}

This procedure is actually the same as with the subset construction, the only difference is the second state set in each qi that is about the final sets (of which I didn't talk about here).

To conclude I do the same for you second example, although it is a bit more complicated:

If you start at s0 and get the input !a you can either go to s0 or to s1

=> reachable(s0, !a) = {s0, s1}

If you start at s1 and get the input !a, the result depends on the value of b, so you either get the following:

=> reachable(s1, !a & !b) = {s1} or

=> reachable(s1, !a & b) = {}

However regardless of those values of b, the union of the reachable states will contain s1 in any case due to having s1 in reachable(s0, !a)

=> reachable({s0, s1}, !a) = {s0, s1}

by (3.4k points)