Question

VRS - Exam [August 31, 2021], Problem 2a,b 

In part a) we compute the product structure K₁ x K₂ and there are 2 unreacheable states (P₁Q₄, P₁Q₅).The question states that we can remove the unreaceable states if necessary. However the solution of part (a) and part (b) both use the unreacheable states. 
Shoud we remove the unreacheable states and then solve part (b)?

Answer 1

You can proceed either ways, the result will be the same since the simulation relation does not dependent on the unreachable states (at the end, we have to check whether for any initial computation of the first structure, there is an initial computation of the second one). The solution has been given with all states, if you do that without the unreachable states, you should you get for the simulation relation of K1xK2<=K2 the following:

    step 0: {(P0Q0,Q0);(P1Q1,Q1);(P1Q1,Q4);(P2Q2,Q2);(P2Q3,Q3);(P1Q4,Q1);(P1Q4,Q4);(P1Q5,Q5)}
    step 1: {(P0Q0,Q0);(P1Q1,Q1);(P2Q2,Q2);(P2Q3,Q3);(P1Q4,Q1);(P1Q4,Q4);(P1Q5,Q5)}

Also, SIM3 holds: For every initial state of K1xK2, i.e., for P0Q0, there is an initial state in K2, namely Q0, that simulates it. Hence, K1xK2<=K2 holds.