For the initial relation, we have to related states that agree on the truth value of the shared variables. The two structures have variables a,b,d and a,b,c so that the shared variables are only a,b. Hence, we ignore the variables c and d, and only construct state pairs that agree on the truth values of variables a and b.

For examples, in states S0 and Q0 the labels are {d} and {c}, respectively, so that both an and b are false. Hence, these states agree on the shared variables (a and b).