# How to determinize NDetF symbolically and explicitly?

Exam question 17.02.2021 Problem 5 (c) :  https://es.cs.uni-kl.de/teaching/vrs/exams/2021.02.17.vrs/2021.02.17.vrs.solutions.pdf I am a bit confused about the solution given in the solution.

Q1: Is state 'r' => sink state here? And the automata determinization is then performed by subset construction method?

Q2: If yes, then do we need the first state {q,r} here?  I am getting states {q}, {} and the sink state {r} only?

Q3: Are the transitions (phi_r) written as in the state transition diagram in the automata equation?

+1 vote

Q1: Yes, {r} is the sink state, in the sense it is that state that is added as target state by the subset construction for the missing transitions. But also {q} is a sink state.

Q2: We do not need state {r,q} in the sense that the subset construction does not generate that state. However, as we encode the states by two state variables, we get four states and have to deal with the fourth state.

Q3: The transition relation can be encoded in different ways. Since it is deterministic, one can also write it as a conjunction of equations

(r′ ↔ r ∨ ¬r∧¬q∧¬a∧¬b) ∧ (q′ ↔ q ∨ ¬r∧¬q∧b)

by (147k points)
selected by