edited by
14,179 views
68 votes
68 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:

  1. $\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}$
  2. $\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}$
  3. $\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}$
  4. $\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}$
edited by

7 Answers

Best answer
47 votes
47 votes

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

edited by
39 votes
39 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.
17 votes
17 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.
5 votes
5 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.

Answer:

Related questions

71 votes
71 votes
14 answers
1
gatecse asked Aug 5, 2014
18,995 views
What is the complement of the language accepted by the NFA shown below?Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.$\phi$$\{\epsilon\}$$a^*$$\{a , \epsilon...
48 votes
48 votes
4 answers
4
go_editor asked Apr 21, 2016
13,579 views
Consider the following relations $A, B$ and $C:$ $$\overset{\textbf{A}}{\begin{array}{|c|c|c|}\hline\\\textbf{Id}& \textbf{Name}& \textbf{Age} \\\hline12& \text{A...