**dead state
q shouldn't be in double circle otherwise string '000' will be accepted.**

The Gateway to Computer Science Excellence

+38 votes

Consider the set of strings on $\{0,1\}$ in which, *every substring of *$3$* symbols* has at most *two* zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are:

+32 votes

Best answer

+5

Though Sir has explained the logic but the name of the states are themselves very indicative. From a state $q_{ab}$ on input symbol c we go to state $q_{bc}$ which means we need to be concerned about the latest 2 symbols in the i/p string so that we can take action accordingly after seeing the 3rd one.

Eg: From $q_{00}$ on 1 we go to $q_{01}$, From $q_{01}$ on 1 we go to $q_{11}$

Only for From $q_{00}$ on 0 this doesn't hold and we need to send it to Dead state.

Eg: From $q_{00}$ on 1 we go to $q_{01}$, From $q_{01}$ on 1 we go to $q_{11}$

Only for From $q_{00}$ on 0 this doesn't hold and we need to send it to Dead state.

0

Sir, it is necessary to change the Finite automata for the given question else answer would be wrong. Its given that DFA is partially completed but from the options it can be concluded that it is just in terms of missing arcs not in terms of final state. NPTEL link for this paper has q as a non final state. **https://nptel.ac.in/content/Gate_Papers/CS/GATE_CS_2012.pdf **

+24 votes

'000' cannot be accepted. So, '00' when gets another 0 must go to a dead state, q.

So, options A and B are eliminated.

By analyzing options C and D, we can understand that when states like 00, 01, 11 or 10 get an input 1 or 0, the next state is the last two digits of the newly formed string.

11 +0 -> 110 (So, 11 on 0 goes to 10).

01+1 -> 011 (So, 01 on 1 goes to 11).

So option D is correct.

So, options A and B are eliminated.

By analyzing options C and D, we can understand that when states like 00, 01, 11 or 10 get an input 1 or 0, the next state is the last two digits of the newly formed string.

11 +0 -> 110 (So, 11 on 0 goes to 10).

01+1 -> 011 (So, 01 on 1 goes to 11).

So option D is correct.

+13 votes

Option A & B false: state 00 -> i/p 0 -> 01 ( state 01 is a final state) and our goal is to not allow 3 consequtive 0's

Option C is false:- state 10-> i/p 0 -> 10 (self loop is there on state 10 on i/p symbol 0 which allows more than 2 consequtive 0's)

Hence D is Ans.

Option C is false:- state 10-> i/p 0 -> 10 (self loop is there on state 10 on i/p symbol 0 which allows more than 2 consequtive 0's)

Hence D is Ans.

+2 votes

All states are final states except “q” which is trap state(question needs correction,q is not final there). The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.

From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option** A and B are eliminated.**

Now option C has the** self loop **of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.

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

50,833 questions

57,713 answers

199,427 comments

107,709 users