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

1.1k questions

1.3k answers

1.7k comments

557 users

+2 votes

Hello,

I would like to ask what unsafe state means in the context of the Rabin/Scott algorithm. I would think that this refers to the sink state, but why is it given in the exercise if we have to return it separately?

in * TF "Emb. Sys. and Rob." by (220 points)
That is what I am also interested in. In ex 8, task 3 I determinized given existential liveness automaton by Rabin/Scott. But, system is not accepting. (
Same here, I even checked it with the tool and the system does not accept my answer.
Hey Michael Will and erji. Have you tried making the automaton complete first before determinizing it?
Yeah I realized this was my problem, it worked now. Thank you.

1 Answer

+1 vote
 
Best answer
The Rabin/Scott algorithm, also called subset construction, and sometimes also called powerset construction is at first nothing else than a function that computes for a given nondeterministic automaton with a designated set of states a corresponding deterministic automaton.

In case of finite automata on finite words, it is easy to prove that the constructed automaton is equivalent to the given nondeterministic one. For omega-automata, this is not that simple. To determinize safety automata, you have to remove all unsafe states, and then apply the subset construction. The new acceptance condition states then that the sink state {} will never be reached (this definition is independent of the Rabin/Scott construction).

Now, what is an unsafe state? Safety automata are defined as automata with a designated set of states which are called the safe states. Their acceptance condition demands that a run is accepting if and only if it only visits safe states. Thus, unsafe states are actually useless for acceptance (since no accepting run may traverse them). We can therefore remove all unsafe states in a safety automaton, so that finally all states are safe (but this can only be done in nondeterministic safety automata).

We cannot discuss exercise sheet 8, task 3 here since there are many different versions of this exercise, so we don't know which automaton is meant here. Please ask your tutor if you think your solution is correct, and you don't understand why it is not accepted.
by (170k points)
selected by
One little remark about the semantics of the sink state: Imagine it as the “if you are here, then the original automaton had no run with the same labels”-state. If a word induces are finite path, then this path might touch the accepting state, but the word is nevertheless refused as there is no infinite path. The sink state makes all paths infinite. Hence, paths reaching the sink state need to be refused.

Related questions

Imprint | Privacy Policy
...