Let $L_n=\{w\in\{0,1\}^* \mid \text{ the } n^{\text{th}}\text{ from last character is } 1\}$.
Define a DFA for this language, for all $n\in\mathbb{N}$.
- Hint: consider a binary word in length $n$.
$Solution.$ Let $$A=(Q,\Sigma,q_0,\delta,F)$$ be the DFA for $L_n$.
Let $m\in\mathbb{N}$, then: $$Q=\{q_0,q_1,\dots,q_{n+m}\}$$ $$F=\{q_{n+m}\}$$ and let $\displaystyle \delta :( Q\times \Sigma )\rightarrow Q$, such that:
$$\forall i\in[1,n+m+1] \backslash\{q_m\}:\delta(q_{i-1},\sigma)=q_i$$ $$\delta(q_{m-1},1)=q_m$$ $$\delta(q_{m-1},0)=q_{pit}$$
Now, I know that defining $m$ it's not good of what I heard. Therefore, I will be glad to know if it isn't correct to define $m$, and how can I solve it by using only $n$?
Thanks!
I would choose $Q = \{0,1\}^{\le n}$, the set of strings consiting of $0$ and $1$ of length at most $n$, including the empty string $\emptyset$.
The informal interpretation of this (which then gives the idea how to define the rest of the DFA) is: You interpret these states as storing the last $n$ digits you have read up to now (or less then $n$, if you have been reading less than $n$ digitis up to now).
Hence, your initial position is $q_0 = \emptyset$ (you haven't read anything up to now).
Your accepting set is $F = \{ 1a : a \in \{0,1\}^{n-1} \}$, i.e. all strings of length $n$ where the first digit is 1. (Since your states are indetend to represent exactlythe $n$-th last digits of your string, this exactly says that the $n$-th last digit is $1$)
The transition function $\delta : Q \times \{0,1\} \to Q$ is "writing the digit you read to the end of the string and forget the first digit, if it would get longer than $n$". That means $\delta(a,x) = ax$, if $a \in \{0,1\}^{\le n-1}$ and $x \in \{0,1\}$. And $\delta(a,x)=a_2\dots a_nx$, if $a =(a_1\dots a_n) \in \{0,1\}^n$ and $x \in \{0,1\}$.