Minimum number of states in the DFA

Question

I am trying to solve following problem but unable to solve this. Can anyone tell me how to approach this kind of problems where it is not easy to make DFA.

The minimum number of states required to construct a DFA that recognizes the language of strings over the alphabet ${a,b}$ whose tenth symbol from the right end is $a$?

I tried converting R.E of the language which is $(a+b)^*a(a+b)^9$ into DFA but couldn't convert. Can anyone convert this into DFA or provide a $generalized$ solution when it is $n^{th}$ symbol from the right hand of the string?

Answer 1

Let $L_n$ consist of all words over $\{a,b\}$ such that the $n$th symbol from the right is $a$. The minimum number of states in a DFA accepting $L_n$ is $2^n$.

First, let us construct a DFA with so many states. The states of the DFA correspond to strings of length $n$ over $\{a,b\}$. The starting state is $b^n$. When in state $\sigma_1\ldots \sigma_n$ and reading $\sigma$, we move to state $\sigma_2 \ldots \sigma_n \sigma$. A state is accepting if the first symbol is $a$.

Second, we use the Myhill–Nerode theorem to show that $2^n$ states are necessary. We claim that all words of length $n$ are pairwise inequivalent. Indeed, let $x \neq y$ be words of length $n$. Then $x_i \neq y_i$ for some $i$, say $x_i = a$ and $y_i = b$. This implies that $x b^{i-1} \in L_n$ whereas $y b^{i-1} \notin L_n$, showing that $x,y$ are inequivalent modulo $L_n$.