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


546 users

0 votes

In exercise 4, problem number 2a, I am facing the problem. Can anyone tell me what's wrong with my solution. The question is: Given a FSM: 

where Vin={a}Vin={a}Vout={o}Vout={o}Vstate={p,q}Vstate={p,q}I=I=q,

in FBI (Department of CS / Fachbereich Informatik) by (120 points)
edited by

1 Answer

+1 vote

To see all transitions, you would have to compute a canonical DNF, i.e., fully expanded DNF, e.g., as follows extneding your computation to a DNF:

     ¬(next(q)∧p∧q ∨ next(p) ∨ (o->a))
     <-> ¬(next(q)∧p∧q  ∨  next(p)  ∨  (¬o ∨ a))
     <-> (¬next(q) ∨ ¬p ∨ ¬q)∧¬next(p)∧o∧¬a
     <-> ¬next(q)∧¬next(p)∧o∧¬a ∨ ¬p∧¬next(p)∧o∧¬a ∨ ¬q∧¬next(p)∧o∧¬a
     <-> ¬p∧¬q∧¬a∧o∧¬next(p)∧¬next(q) ∨ 
         ¬p∧¬q∧¬a∧o∧¬next(p)∧ next(q) ∨ 
         ¬p∧ q∧¬a∧o∧¬next(p)∧¬next(q) ∨ 
         ¬p∧ q∧¬a∧o∧¬next(p)∧ next(q) ∨
          p∧¬q∧¬a∧o∧¬next(p)∧ next(q) ∨ 
          p∧¬q∧¬a∧o∧¬next(p)∧¬next(q) ∨
          p∧ q∧¬a∧o∧¬next(p)∧¬next(q)  

However, that is usually a lot of work and is not recommended. You can better compute the transitions as follows: With state variable p and q, we have states {},{p},{q},{p,q}. To compute their transitions, we instantiate the transition relation  with their possible values:

    {}    : ¬(next(p) ∨ (o->a))
    {p}   : ¬(next(p) ∨ (o->a))
    {q}   : ¬(next(p) ∨ (o->a))
    {p,q} : ¬(next(q) ∨ next(p) ∨ (o->a))

Now you see that states {},{p},{q} have the same transitions, namely two transitions both labeled with ¬(o->a) and leading to {} and {q}, respectively. This is so, since ¬(next(p) ∨ (o->a)) is equivalent to ¬next(p) ∧ ¬(o->a)).

The transitions of the remaining state {p,q} are given by ¬(next(q) ∨ next(p) ∨ (o->a)) which is equivalent to ¬next(q) ∧ ¬next(p) ∧ ¬(o->a), so that there is only one transition labeled with ¬(o->a) and leading to {}.

Hence, this is your FSM:

by (166k points)

Related questions

0 votes
1 answer
0 votes
1 answer
+1 vote
1 answer
asked Aug 18, 2018 in * TF "Emb. Sys. and Rob." by a_ (350 points)
Imprint | Privacy Policy