construct the dfa

Question

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

Answer 1

Design a (normal) DFA that accepts strings, over {$0,1$}, that ends with $111$.

Now Look at DFA, $q_3$ is a state where we get a sequence in which no of $1's$ is multiple of $3$. so whenever we reach $q_3$ we get output $1$.

We can design Mealy machine for it , by getting output $1$ on the incoming edges on state $q_3$, and output $0$ at all others.

Or, We can design Moore machine, by putting output $1$ on the state $q_3$ and output $0$ on others.

Comments

Ya,from mealy diagram ,it is clear that o/p is 0011 for i/p 1111.My doubt is in diagram itself. Why did you draw FA like this i.e. FA accepting strings ending with 111? We could draw FA accepting strings starting with 111 or containing 111.

---

NO,

as we need output 1 each time when we get 111 sequence. With FA ending with 111 we will reach q3 only when we get 111 and everytime (else we move to q0 and check again)

in case of start with 111(0+1)* or (0+1)*111(0+1)*, we have no control after 111 bcoz of (0+1)*

---

Yes , got it....many thanx!!!