6 votes 6 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$. Digital Logic gate1987 digital-logic digital-counter descriptive + – makhdoom ghaya asked Nov 14, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 2.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Shaik Masthan commented Aug 27, 2018 reply Follow Share sir, can you provide sample input and output 0 votes 0 votes Swapnil Naik commented Aug 27, 2018 reply Follow Share 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. 2 votes 2 votes Shaik Masthan commented Aug 27, 2018 reply Follow Share @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. 0 votes 0 votes Satbir commented Jun 15, 2019 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
Best answer 10 votes 10 votes 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. Satbir answered Jun 15, 2019 • selected Aug 13, 2019 by Arjun Satbir comment Share Follow See all 3 Comments See all 3 3 Comments reply Arjun commented Jun 15, 2019 reply Follow Share Initially it'll print a $1$ rt? 2 votes 2 votes Satbir commented Jun 15, 2019 reply Follow Share Yes sir, I have included it for the case when there are no ones in the input string. 4 votes 4 votes JAINchiNMay commented Nov 13, 2022 reply Follow Share A will be the start state 1 votes 1 votes Please log in or register to add a comment.