sir, can you provide sample input and output

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+3 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.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,833 questions

54,800 answers

189,505 comments

80,724 users