GATE CS 2021 Set 2 Q17 — Regular Expressions and Finite Automata

By analyzing the given DFA, we can observe the reachability of its states from the start state $q_0$:

• The start state $q_0$ is a final (accepting) state.
• From $q_0$, on input $a$ we transition to $q_1$ (which is also a final state), and on input $b$ we remain in $q_0$.
• From $q_1$, on input $a$ we remain in $q_1$, and on input $b$ we transition back to $q_0$.
• The state $q_2$ is a non-final state, but there is no path from the start state $q_0$ to $q_2$. Thus, $q_2$ is unreachable.

Since all reachable states ($q_0$ and $q_1$) are final states, every possible sequence of transitions starting from $q_0$ will always end in an accepting state. Therefore, the DFA accepts all strings over the alphabet $\Sigma = \{a, b\}$.

The number of strings of length $8$ over the binary alphabet $\{a, b\}$ is: