3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why couldn't you convert this to a DFA? $\endgroup$ – JimN Dec 22 '17 at 6:08
  • $\begingroup$ Can you convert? @JimN $\endgroup$ – Mr. Sigma. Dec 22 '17 at 8:32
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.