The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
2.8k 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}$
asked in Theory of Computation by Veteran (396k points)
edited by | 2.8k views

3 Answers

+27 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$'.

answered by Veteran (396k points)
edited by
+5
From 11, a '0' should go to 10
+1
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.
+22 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.
answered by (329 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.
answered by Boss (23.6k points)
Answer:

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,129 questions
53,252 answers
184,785 comments
70,505 users