Test by Bikram | Theory of Computation | Test 2 | Question: 16

Question

Consider the following incomplete DFA.

What will be the transitions of state D such that automata will accept the set of all binary strings containing $010$ as sub-string ?

• A. $d (D,0)=A$  $d (D,1)=D$
• B. $d (D,0)=C$  $d (D,1)=B$
• C. $d (D,0)=D$  $d (D,1)=B$
• D. $d (D,0)=D$  $d (D,1)=D$

Comments

the machine is already accepting sub string containing  o1o,then all should be correct y only d?

---

@kamakshi

if u give self loop on D ...u can accept any number of 0's and 1's after that because already substring is obtained

but consider other cases

for example (D,0) goes to A

then its not possible to generate a string which just ends with 0 after the substring 010..it will again have to travel through some values and then reach D

---

Thankyou

Answer 1

Now this is complete DFA then we can say that d(D,0)=D and d(D,1)=D this is the two transition.

Then Option D is correct.