The Gateway to Computer Science Excellence
+34 votes
3.3k views

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}$
in Theory of Computation by Veteran (425k points)
edited by | 3.3k views
+5

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

+1
yes q should be dead state, correction needed

4 Answers

+30 votes
Best answer

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

by Veteran (425k points)
edited by
+5
From 11, a '0' should go to 10
+4
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.
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.
by (359 points)
0
Awsome Explaination.. thanks alot.......
+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.
by Boss (23.8k points)
+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.

by Junior (993 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,578 answers
195,772 comments
101,771 users