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

1.6k comments

529 users

+1 vote

Hello,

In October 2017 paper Problem 5 While converting NDetG to DetG we remove all unsafe states. Why we removed initial state ? Initial state is reaching to acceptance state why it is unsafe state as well. When there is Initial state how We apply subset construction?

in # Study-Organisation (Master) by (190 points)

2 Answers

+1 vote
For ω-automata with G/F/FG/GF-acceptance, we always have to determine a set of accepting states which is done completely independent of the definition of initial states. Thus, a state can be either initial or accepting, or both or neither of the two. In particular, initial states may not be accepting states.

In case of NDet-G automata, this is however unfortunate, since the G-acceptance demands that a run is accepting iff it only runs through safe states, i.e., accepting states. If an initial state of NDet-G automaton is not accepting, it is useless, since none of its outgoing paths can accept a word. Hence, you can safely remove this state without changing the meaning of the automaton. The same holds for any other non-accepting states of NDet-G automata. We therefore can remove them all, just working with the safe (accepting states).

If we do that for the NDet-G automaton of the exam 2013.10.07 (problem 5), an automaton is obtained that has no initial states anymore, thus cannot accept any word. This makes the solution trivial (just list any automaton that accepts no word). The subset construction will then just create one state {} with a self-loop that can be taken for any input (and that state is not a safe/accepting one).
by (166k points)
0 votes
As you have learned, omega-automata have acceptance conditions to decide whether an infinite run is accepting or not. In particular, safety automata have a condition that demands that the run consist only of safe states. A state is thereby safe if it is declared as such, i.e., it is part of the specification to define this.

In the exam question you mention, there is only one initial state, namely q0 and the only safe states are q1 and q2. It is pointless to discuss why that is so, it is simply given like that by this exercise, and another exercise may make another choice.

Hence, in this case, none of the runs that start in the initial state will be an accepting run, so that the automaton accepts no word. Removing all unsafe states yields an automaton without initial states, so that also that one does not accept any word. The subset construction could be applied, but again it would yield an automaton without initial states which also does not accept any word.

How is the subset construction applied? Well, as usual, we start with the set of initial states which is in this case the empty set of states {}, and this one is its only successor state for any input. It is not an initial state, however, since it does not contain an initial state. You may try this also with the corresponding teaching tool and you will see the same as written here. Try it and see.

At the end, the exam problem is therefore quite trivial and could be answered without applying any determinization procedure.
by (166k points)
edited by

Related questions

Imprint | Privacy Policy
...