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

870 questions

988 answers

1.4k comments

439 users

0 votes

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?

Thanks for your help.

in * TF "Emb. Sys. and Rob." by (500 points)

1 Answer

+1 vote
 
Best answer

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)

(See also the updated example solutions)

by (139k points)
selected by
Thanks for the answer.

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...