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

sir, can you provide sample input and output

---

Isn't this problem similar to find three 1's in a given string and when you encounter with 3rd 1 it will have transition to the final state.Here final state will be the starting state so that you can again check for next three 1's.

Also finite automata with output is nothing but mealy or moore machine. So there will be minimum three states and from last state to starting state there will be 1|1 transition (mealy) to get output 1 for every three 1's.

---

@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.

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

Initially it'll print a $1$ rt?

---

Yes sir, I have included it for the case when there are no ones in the input string.

---

A will be the start state