The Gateway to Computer Science Excellence
+3 votes
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$.
in Digital Logic by Boss (30.1k points)
retagged by | 409 views
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.

1 Answer

+5 votes
Best answer

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.

by Boss (21.6k points)
selected by
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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,461 answers
100,247 users