Exercise Sheet 4, question 2

Question

Use the same label, inputs, and outputs to compute the state transition diagram of the given FSM.

Submit the initial states and transitions in an explicit form:

init 0,1;

transitions (0,{a},{o},1); (0,{},{o},2); (1,{a},{},3); (3,{},{},3); 

I converted given FSM to following diagram:

also I interpret R as below:

- there are 2 state variable p,q then we have 4 states

- !(p->a) is p&!a 

- next(q)

in this step we have:

p -- !a --> q

p -- !a --> q

p -- !a --> q

p -- !a --> q

- (next(p)|o|q) => because of OR operator we add operand in each state as below, but not sure how is the last one?

p -- !a --> p,q       => added next(p)

p -- !a,o --> q       => added output o

p,q -- !a --> q       => added q

p,q -- !a --> p,q      => ???

and below is my answer:

init 1,3;

transitions (1,{},{o},2); (1,{},*,3); (3,{},*,2); (3,{},*,3);

BUT, still when I want to submit it says it is wrong.

May someone assist to elaborate which part I have done wrongly?

Answer 1

You may first compute a DNF of the transition relation if you like:

    p ∧ ¬a ∧ next(p) ∧ next(q) ∨ 
    p ∧ q ∧ ¬a ∧ next(q) ∨ 
    p ∧ ¬a ∧ o ∧ next(q)

and this way, the transitions of the represented FSM are as follows:

    {p} --- ¬a ---> {p,q}
    {p} --- ¬a∧o ---> {q}
    {p,q} --- ¬a ---> {p,q}
    {p,q} --- ¬a ---> {q}

The represented FSM looks as follows:

So, as far as I can see, your FSM is correct. I therefore conclude that you have a syntax problem with our input, and looking at it, I see that you are using "*" as wildcards, but that is not accepted by the tool. You have to enumerate all the transitions one by one. Maybe the simplest way to achieve that is to compute a DNF of minterms, i.e.:

    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)

It should be easy from here to compute the FSM representation in an explicit form.

This corresponds with the following Krikpe structure (ignoring deadend states):

Comments

I am not able to understand how did we get transition from {p,q} ----- !a ---- {p,q}. Kindly, help me on this.

---

When looking at the satisfying assignments, these are actually two transitions. If you consider the maximal DNF that I listed above, you see seven possible assignments that satisfy the transition relation. Each one should be a transition of the FSM, so that we have the following seven transitions:

    {p}   --{}---> {p,q}
    {p}   --{o}--> {p,q}
    {p}   --{o}--> {q}
    {p,q} --{}---> {p,q}
    {p,q} --{o}--> {p,q}
    {p,q} --{}---> {q}
    {p,q} --{o}--> {q}  

When you now consider pairs of states and wonder about the conditions when these transitions are enabled, you will see e.g. for

    {p}   --(!a&!o | !a&o)---> {p,q}
    {p}   --(!a&o)--> {q}
    {p,q} --(!a&!o | !a&o)--> {p,q}
    {p,q} --(!a&!o | !a&o)--> {q}  

which is by some simplifications

    {p}   --(!a)---> {p,q}
    {p}   --(!a&o)--> {q}
    {p,q} --(!a)--> {p,q}
    {p,q} --(!a)--> {q}

---

how do you get the maximal DNF?

---

Either from the truth table as explained on the slides or by adding all redundant cases from any other DNF, i.e.,  a&b may become a&b&c | a&b&!c this way.

---

It's is given that Initial state = p, so why we considered {p,q} also a initial state?is it because  p is true in that state?. I am confused here.

---

The initial state formula is p. But it is a formula over the variables p and q so when making a truth table you would have to consider four cases and that is similar to what I wrote above: p is equivalent to p&!q | p&q, i.e. the two states {p} and {p,q}. So, yes, it is because p is true there as well. We have to list all states where p is true and q may be true or false.

---

Thank you for precise clarification.

---

when writing the transition the 4th line the DNF format(p ∧ ¬a ∧ o ∧ next(q)) takes only   {p} --- ¬a∧o ---> {q} why can‘t we also add   {p} --- ¬a∧o ---> {p,q} because in both cases q is true.