As the title states, I'm trying to define a DFA that checks whether the $n$:th number from the right is a $1$.
The alphabet consists of only 0 and 1, i.e. $ \Sigma = \{0,1\} $.
For example, if $n$ = 4, the input $1111110000001$ would not be accepted, whereas $0001111011$ would be.
I'm currently been at this problem for hours, and while did come up with a solution for it, I'm struggling to see whether there's a way to minimize it or not.
Right now, the solution I have requires $ 2^{n-1} $ accepting states, and a total amount of states of $ 2*2^{n-1} $ (while $n$ is larger than 0). It involves remembering any combination of the last n digits, but since it's exponential, it becomes very large very fast. For example, to check whether the 10th symbol from the last is a $1$ or not, you would need a totalt of 512 accepting states and 1024 states in total.
Of course, checking the $n$:th number from the left would just require one accepting state, since the size of the input is irrelevant when it becomes larger than 5, but doing it from the right seems to make it a lot more complicated.
Is there a way to minimize this in any way (like reverse the input or something...), or is this as small as it can get? Any help is greatly appreciated!
I give you the answer without proof. Let me know if you need further help.
The language you are considering is $L_n = \Sigma^*1\Sigma^{n-1}$. It turns out that the minimal automaton of $L_n$ has precisely $2^n$ states (and $2^{n-1}$ final states).