How to find the transition relation of NDetFG automation using truth table

Question

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

Problem 6a of September, 2022 exams.

Answer 1

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.

Comments

@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!