Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


510 users

0 votes

I have some doubts here, 

1) How can i find the transition relation from this automaton? 

 I am not sure we can generate the associate kripke then take  transition relation and use that. 

2) How can i find the acceptance state relation? 

Could you please help on this?

in # Study-Organisation (Master) by (2.7k points)

1 Answer

0 votes
Well, the simplest way is that you would have to list all transitions as minterms of a DNF. It would start like this:

    !p&!q&!Xp&!Xq | !p&!q&!Xp&Xq | ...

You could generate the associated Kripke structure, but that is just more work and you will get the same formula as the one above. So, that is not useful.

The acceptance condition is the set of gray states (I guess) which is


but from the diagram, we don't know whether that is a safety, liveness or whatever automaton.
by (162k points)
Should we also consider the input as well ?
like here , if the input state has {{a}, {}}
 !a&!p&!q&!Xp&!Xq | !p&!q&!Xp&Xq | etc ...

Since the state transition does not have input inside the state, if we draw the Kripke then we can have input in the state , for instance,
a&p&q&a&p' etc..
Should we use input as well? or just states in the automaton without  considering input and output ?

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy