# Prob 6 NDet FG (SEP 2022)

 P Q Relation 0 0 (!Xp | a) & (!a | Xp) 0 1 (!Xp | a) & (!a | Xp)& (!b & Xq) 1 0 Xp 1 1 Xp & !b &Xq

for this specific question could u please explain how from this transition we draw transition diagram for state p0qo and p0q1?as far as I understood we can draw with DNF but in case p0q0 it is CNF.

Lets take the state p = q = 0 which is the starting state of any transition the remaining relation (!Xp | a) & (!a | Xp) talks about. Now you can check for every possible "ending state" of a transition what inputs you need for that (if possible at all):

p' = q' = 0 => Relation reduces to: (1 | a) & (!a | 0) = 1 & !a = !a

=> the loop from state {} to state {} needs input !a

p' = 0, q' = 1 => The same result as before as q' does not appear in the relation

=> the transition from state {} to state {q} needs input !a

p' = 1, q' = 0 => Relation reduced to (0 | a) & (!a | 1) = a & 1 = a

=> the transition from state {} to state {p} needs input a

p' = q' = 1 => Again the same result as before

=> the transition from state {} to state {p,q} needs input a

Technically by doing this you are trying every of the 16 possible combinations of p, q, p' and q' and you could create a truth table for all of these 16 cases. However as you just saw you don't need to actually do all cases as some are equal to some others; for example in the current case the value of q' didn't matter as it didn't appear in this relation when starting at p = q = 0 thus you only needed to check half of the cases.

Another easy example for that is the case p = 1 and q = 0 where the relation is just p', so the only condition is that the successor state has p in its label, thus the four cases are directly clear:

Draw a transition from {p} to {p} and to {p,q} with a star symbol * each (i.e. the input doesn't matter or all inputs are allowed for those transitions); on the other side there are no transitions from {p} to either {} or {q} as the relation evaluates to false in those cases.

For that reason you normally don't want to do a truth table for all 16 entries but just a partial truth table as you did here (for the starting states) as this allows you do reduce some time when evaluating all possible cases.

Final example for p = q = 1:

The relation is a direct conjunction so the only possible transition goes to state p' = q' = 1 by having input !b.
by (3.4k points)
selected by