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

912 questions

1k answers

1.4k comments

441 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 (142k points)
selected by
Thanks for the answer.

Related questions

0 votes
1 answer
0 votes
1 answer
asked Aug 24, 2022 in * TF "Emb. Sys. and Rob." by CS_E (2.9k points)
0 votes
1 answer
asked Sep 1, 2022 in * TF "Emb. Sys. and Rob." by learner (330 points)
Imprint | Privacy Policy
...