sir, can you provide sample input and output

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

+2

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.

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.

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,461 answers

195,358 comments

100,247 users