Transitions Diagramm of W-Automata Klausur August 29, 2023 Problem 6

Question

The Graph above is the answer from the automata. I have problem to determine some of those transitions. I used a truth table to dertermine which the trasitions. This way works well for other Klausur examples. 

p	q	ϕR
0	0	!(b | a & next(p))
0	1	!(b | a & next(p)) & next(q)
1	0	b | a & next(p) & !next(q)
1	1	b | a & next(p) & next(q)

How are we getting the transitions ({p,q}, b , {q}) ; ({p}, b , {}) ; ({}, !b ,{}) ; ({}, !b ,{q}) ?

Answer 1

I think that we have the following transition relation:

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

which reduces to the following sets of transitions per state:

• p=0;q=0 : !b&!a|!b&!next(p)) 
• p=0;q=1 : false
• p=1;q=0 :  (b|a&next(p))&!next(q) 
• p=1;q=1 :  (b|a&next(p))& next(q) 

So, your truth table seems to be wrong since you ignored some brackets and precedences. With the above formulas, you get the transitions of the given solution.