GATE CSE 2012 | Question: 46

Question

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:

• A. $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{}  &  \textbf{00} & \textbf{01} & \textbf{10}&  \textbf{11} & \textbf{q}  \\\hline  \textbf{00}  &  \text{1} & \text{0} & \text{}&  \text{} & \text{}  \\\hline   \textbf{01}  &  \text{} & \text{} & \text{}&  \text{1} & \text{}  \\\hline  \textbf{10}  &  \text{0} & \text{} & \text{}&  \text{} & \text{}  \\\hline  \textbf{11}  &  \text{} & \text{} & \text{0}&  \text{} & \text{}  \\\hline  \end{array}$
• B. $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{}  &  \textbf{00} & \textbf{01} & \textbf{10}&  \textbf{11} & \textbf{q}  \\\hline  \textbf{00}  &  \text{} & \text{0} & \text{}&  \text{} & \text{1}  \\\hline   \textbf{01}  &  \text{} & \text{1} & \text{}&  \text{} & \text{}  \\\hline  \textbf{10}  &  \text{} & \text{} & \text{}&  \text{0} & \text{}  \\\hline  \textbf{11}  &  \text{} & \text{0} & \text{}&  \text{} & \text{}  \\\hline  \end{array}$
• C. $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{}  &  \textbf{00} & \textbf{01} & \textbf{10}&  \textbf{11} & \textbf{q}  \\\hline  \textbf{00}  &  \text{} & \text{1} & \text{}&  \text{} & \text{0}  \\\hline   \textbf{01}  &  \text{} & \text{1} & \text{}&  \text{} & \text{}  \\\hline  \textbf{10}  &  \text{} & \text{} & \text{0}&  \text{} & \text{}  \\\hline  \textbf{11}  &  \text{} & \text{0} & \text{}&  \text{} & \text{}  \\\hline  \end{array}$
• D. $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{}  &  \textbf{00} & \textbf{01} & \textbf{10}&  \textbf{11} & \textbf{q}  \\\hline  \textbf{00}  &  \text{} & \text{1} & \text{}&  \text{} & \text{0}  \\\hline   \textbf{01}  &  \text{} & \text{} & \text{}&  \text{1} & \text{}  \\\hline  \textbf{10}  &  \text{0} & \text{} & \text{}&  \text{} & \text{}  \\\hline  \textbf{11}  &  \text{} & \text{} & \text{0}&  \text{} & \text{}  \\\hline  \end{array}$

Comments

ERROR IN GO PDF q should not be final

---

Start by eliminating options. we have to reject 000 as substring   when we take '100010' as a string it contain 000 so we have to reject it so at third 0 the state must be at dead state which is present in option D

---

From 00 state 0 should only go to state q that is non final because otherwise it violates the condition of having at most 2 0's in every 3 length substring.

This eliminates option A and B

Now from 01 state the 1 can go anywher we are not sure yet.

But if you see from 10 state 0 cant be a self loop because then there can be infinitely mant zeros that occur the appear continuosly in the string and again it will violate the condition in the question. So from 10 state it goes to 00 state.

Hence the answer is option D

Answer 1

(D) is the answer. From $00$ state, a '$0$' should take the DFA to the dead state-$q$. From $11$, a '$0$' should go to $10$ representing the $10$ at the end of string so far. Similarly, from $00$ a $1$ should go to $01$, from $01$ a '$1$' should go to $11$ and from $10$ a '$0$' should go to '$00$'.

Comments

 From 00 state, a '0' should take the DFA to the dead state-q. 

But here $q$ is a final state. It should be dead state. Edit necessary in question @Arjun Sir, @Shaik Masthan Sir.

Also in GO Pdf

---

Sir i think there is no issue even if all final states has a self loop on input 1.

---

yeah that's right coz its not concern abt $1$ here we've to ensure the no of $0's$ only

Answer 2

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

Comments

Awsome Explaination.. thanks alot.......

---

Brother q have 2 circles, it means it is final state, how finalstate can me dead.????

---

So assuming that state name is the last two digit of string, we can say option D is correct, but technically both option C and D are correct know? Am i missing something?

---

no q is actually having single circle ,q is dead state

 

Answer 3

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.

Answer 4

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.

Answer 5

All states are final states except “q” which is trap state. 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.

Comments

Thanks Brother after your solution i understand it properly.

Answer 6

In Go Book Q is made as accepting state. please correct..