CMI2020-A: 1

Question

Which of the following languages over the alphabet $\{0,1\}$ are $not$ recognized by deterministic finite state automata $(DFA)$ with $three$ states?

• A. Words which do not have $11$ as a contiguous subword
• B. Binary representations of multiples of three
• C. Words that have $11$ as a suffix
• D. Words that do not contain $101$ as a contiguous subword

Answer 1

If we do by option Elimination, then I think D is the correct answer as 101 as a contiiguous sub word will require at least 4 states.

 

All the other 3 options are possible within 3 states.

q0___1____q1_____0____q2____1____q3

you can complete the min DFA, but I am sure, D is the correct answer.

Answer 2

 

Option D : Minimal DFA that do not contain 101 as a contiguous sub word required minimum 4 states

Answer 3