Problem 6. w-automata Aug. 2023 exam state transition diagram

Question

Greetings, I tried using a truth table to draw the state transition diagram for the automaton, however I can not understand how the relations are appearing. for example in the case of p=0, q=0 our relation is basically false.

Answer 1

Consider the following propositional logic formula that clearly corresponds with the transltion relation:

    (p <-> b | a & xp) & (q <-> p & xp)

You can compute the following BDD for this formula:

It is not that I would suggest to solve the exercise this way, but the BDD above shows all the satisfying assignments, and these correspond with the transitions of the automaton.