# Exam 2019.08. 4d.

Hello all,

In the following question, how would I solve it by "sharp looking"? The logic I used is:

All the paths from each state should eventually reach the loop s1,s2,s5. The answer I get is {s7}. Is this correct?

+1 vote

You first consider EGa which are the states that have an outgoing infinite path where a holds. Thus, just consider the a-states {s0;s1;s2;s5;s7} and try to find such path starting in these states. Clearly, the cycle s2->s1->s5->s2 is such a path and shows that these state belong to EGa. Also s0 can join this cycle with s0->s5, however, s7 has no outgoing transition and does not satisfy this. Hence, we found that EGa is {s0;s1;s2;s5}.

AF{s0;s1;s2;s5} are the states where all outgoing paths (if any) will eventually reach one of the states {s0;s1;s2;s5}. This is immediate for states {s0;s1;s2;s5}, and it is easy to see that the rest does also have transitions to this set (and s7 does not have infinite outgoing paths and therefore also satisfies this).
by (147k points)
selected
Thank you for the explanation.