GO Classes DPP | GATE CS | Theory of Computation | DFA Language

Answer 1

The states in the given DFA correspond to the following conditions:

• $q_0 :$ Remainder $0$ on division by $4$
• $q_1 :$ Remainder $1$ on division by $4$
• $q_2 :$ Remainder $2$ on division by $4$
• $q_3 :$ Remainder $3$ on division by $4$

Since $q_1$ and $q_3$ are the final states, it means the DFA accepts all binary strings which have remainder $1$ or $3$, i.e. all binary strings which are odd.

The correct answer is C.

Answer 2

for strings of length $\lt 2$:
$q_0$ is reached by $\varepsilon, 0$
$q_1$ is reached by $1$

for strings of length $\ge 2$:
$q_0$ is reached by strings ending with $00$
$q_1$ is reached by strings ending with $01$
$q_2$ is reached by strings ending with $10$
$q_3$ is reached by strings ending with $11$

for final accepting state being $q_1 \text{and}\ q_3$, we have all strings that end with $1$.

Thus the DFA accepts only and all Binary strings representing odd numbers.

Answer: C

Answer 3

string ended by 1 so in binary if any binary number having last bit as 1 that number is odd in decimal. So option C is correct