Confusion in quotient structure on self-transition

Question

Hi KS,

I have a question, I was going through the solution and was wondering why is there a self-loop/transition on S1S4 or s1={} (in your above diagram).

In the actual question, there is a transition from S1 to S4  but there is no transition from S4 to S1 or S1 to S1. So, I don't think that there should be a self-transition on S1S4.

As I understand for the final structure, there will be a transition from S1S4 to S2S5 if:

In the original question, there was a transition from:

1. Either S1 to S2 and S4 to S5

2. Or  S1 to S5 and S4 to S2

Am I wrong? Is this concept correct or not?

Thank you!
Looking forward to hearing from you

Answer 1

We have computed the following equivalence relation:

    B1 = {(S0,S0);(S1,S1);(S2,S2);(S3,S3);(S4,S4);(S5,S5);
          (S0,S3);(S1,S4);(S2,S5);
          (S3,S0);(S4,S1);(S5,S2)}

That equivalence relation partitions the set of states into the following classes:

    {S0;S3}
    {S1;S4}
    {S2;S5}

The quotient structure is a state transition system on these classes, and instead of using the above classes, we pick a representative of each class (which is the state with least index). The transitions between classes are added whenever the classes contain states which were connected by a transition.

The self-loop on S1 of the quotient structure is actually a self-loop from the class {S1;S4} to itself. Why is it there? Since we had a transition from S4 to S4 which is contained in the class of S1. Recall that the transitions of {S1;S4} (which is actually the state S1 in the quotient structure) are the transitions of S1 and also of S4.

Comments

Hi KS,
Thank you for the quick reply, even on the weekend.
Really appreciate your cooperation.

From What I understand from your explanation,

For example, for a set of states: S1, S2, S3, S4. In the merged states: S1S2 and S3S4.
if there was a transition from S1 to S3 in the original structure then, we will draw a transition from S1S2 to S3S4 in the final structure, whether there is a transition from S2 to S4 or not.
Did I understand it right?

---

Right! You got it!

---

Thank you very much :)