From 11, a '0' should go to 10

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 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:

- $\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}$
- $\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}$
- $\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}$
- $\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}$

+27 votes

Best answer

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

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.

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.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,129 questions

53,252 answers

184,785 comments

70,505 users