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

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes

Problem 6)a) from the August 29,2023 paper.

Conversion of the given NDetFG Automation to state transition diagram.

automata

In the above question, I tried to find the transitions from each state through the truth table and got the following : 

tt

But I am not able to figure out the inputs and transitions to each state from the above.

For example, how does state s0 have an outgoing edge to s1 with input !b? 

Is this method correct? What is that I am missing here?

in * TF "Emb. Sys. and Rob." by (360 points)
edited by

1 Answer

0 votes
 
Best answer

Your truth table is correct as far as I can say, and you should be able to derive the state transition diagram from it. 

It should go like this: We have four states s0:{}, s1:{q}, s2:{p}, s3:{p,q} and the transitions are obtained as follows: For example, in state s0:{}, we have !p&!q, so that the transition relation reduces to !(b|a&xp) which is equivalent to !p'&!b | !a&!b. You know that already. Hence, we have a transition to all other four states and we obtain their labels by further instantiating this formula with the target state: 

  • For the transition s0->s0, we have !p'&!q', so that the transition relation becomes !b | !a&!b which is equivalent to !b.  
  • For the transition s0->s1, we have !p'&q', so that the transition relation becomes !b | !a&!b which is equivalent to !b.  
  • For the transition s0->s2, we have p'&!q', so that the transition relation becomes !a&!b.  
  • For the transition s0->s3, we have p'&q', so that the transition relation becomes !a&!b.  

In the same way, you get the other transitions and their labels.

by (170k points)
selected by
Oh! I get it now. Thank you very much:)!
Imprint | Privacy Policy
...