# Exercise Sheet 4, question 2 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      => ???

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?

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): by (143k points)
edited by
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.

+1 vote