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


543 users

0 votes

In question 3 we're asked to submit the deadends of a given Kripke structure in DNF. I was given this FSM:

input: {a}
output: {}
init states: p&q
transitions: a&q&!p&!next(q)&next(p)|p&q&next(p)&next(q)|q&!a&!p&!next(p)&next(q)
State transition diagram:

Given state transition diagram

Using the teaching tool I got the following Kripke structure of which I thought that only the states s0, s1, s4 and s5 are deadends as they don't have any outgoing transitions. When the exercise system displayed the solution as incorrect I thought that also s3 and s2 should be deadends because neither s2 nor s3 are init states and hence cannot be reached by any means.

As this also was displayed as incorrect it was obvious that the only possible solution can be s0, s1, s4, s5 and s3 being deadends but I don't get why exactly s3 is a deadend (and also why s3 and not s4 as well) as only the previous two solutions seem to make sense for me based on my understanding of deadends?

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

1 Answer

+1 vote
Depends on your definition of deadends. There are deadends in the sense of “no successors” and “no successors on infinite paths”. The latter is the definition we applied here.
by (25.6k points)
Imprint | Privacy Policy