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

0 votes

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

Problem 6a of September, 2022 exams.

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

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer