GATE CSE 1987 | Question: 10c

Question

Give a minimal DFA that performs as a $\mod - 3,\;$ $1$'s counter, i.e. outputs a $1$ each time the number of $1$'s in the input sequence is a multiple of $3$.

Comments

@Swapnil Naik

i am also thinking that in the same way... and one more doubt about alphabet, is it binary or decimal.

for confirmation i asked sample input.

---

Whatever be in the input whether it is decimal or binary we don't have to care.

we just have to count number of 1's in the given sequence and if it is multiple of 3 then we have to print 1.

for eg : -

input is 1011 in decimal then also print 1.

input is 1101 in binary then also print 1.

---

@Satbir,

yes, input alphabet (should include 1 always) is not significant here due to our focus is on only number of 1's.

However, while drawing DFA/Melay/Moorey, input alphabet have significance to draw the transitions.

Answer 1

Since it is given that the minimal DFA outputs $1$ $\implies$ we have to make a minimal DFA and then convert it into mealy/ moore machine by associating output with each input or state.

the minimal DFA will be as shown below :-

I am associating output with each input i.e. creating a mealy machine. It will print 1 each time the number of 1's in the input sequence is a multiple of 3.

Comments

There is no final state in case of mealy / moore machine why did you put it ?

---

@ash_kholai think they have made, to count if number of 1's is 0 .

---

@Prakash_ No use of final state in mealy/moore machine.