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

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

Problem 6a of September, 2022 exams.

+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 (147k 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!