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

538 users

0 votes

Hi, how do you draw the state transition diagram after generating the transition relations.

Problem 6a of September, 2022 exams.

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

1 Answer

+1 vote

For the transition relation (Xp <-> p | a) & (q -> ¬b & Xq), you consider the transitions in the four possible states:

  •     p=0,q=0: (Xp <-> 0 | a) & (0 -> ¬b & Xq) = (Xp <-> a)
  •     p=0,q=1: (Xp <-> 0 | a) & (1 -> ¬b & Xq) = (Xp <-> a) & ¬b & Xq
  •     p=1,q=0: (Xp <-> 1 | a) & (0 -> ¬b & Xq) = Xp
  •     p=1,q=1: (Xp <-> 1 | a) & (1 -> ¬b & Xq) = Xp & ¬b & Xq

We therefore get the following transitions:

  • In state p=0,q=0, we therefore have transitions for "a" to states {p} and {p,q} as well as transitions to states {} and {q} for input ¬a. 
  • In state p=0,q=1, we therefore have a transitions for a&¬b to state {p,q} as well as a transition to state {q} for input ¬a&¬b.
  • In state p=1,q=0, we therefore have transitions to states {p} and {p,q} for any inputs.
  • In state p=1,q=1, we therefore have a transition to state {p,q} for input ¬b.

by (166k points)
@KS if possible, can you explain how this "(Xp <-> a)" results in these transitions for "a" to states {p} and {p,q} as well as transitions to states {} and {q} for input ¬a.?
Well, the satisfying assignment of "(Xp <-> a)" are those where both Xp and a hold or are both false. So input a leads to states where p holds next, and input !a leads to states where p is false next. Variable q is a don't care and can become true or false.
@KS Thank you!
Imprint | Privacy Policy
...