Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


538 users

0 votes

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

In part a) we compute the product structure K1 x K2 and there are 2 unreacheable states (P1Q4, P1Q5).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)?

in * TF "Emb. Sys. and Rob." by (640 points)

1 Answer

+1 vote
Best answer

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.

by (166k points)
selected by
Imprint | Privacy Policy