Create a NFA for the following regular language Exponential Blowup of Subset Construction
Definition: $L_n = \{w ∈ \{0, 1\}^\star\,|\,w_{|w|-n}=1\}$. In other words,
$L_n$ is the set of binary words having a $1$ in the nth position from the end. Here $|w|$ is the length of the word $w$.
Note: an NFA with only $n+1$ states can be designed to recognized $L_n$.
Attempt: Construct a NFA $B$ with $n+1$ states for the reverse of $w$. Change the start state of $B$ to be the last state in $B$.

Theorem: A DFA that recognizes $L_n$ can not have less than $2^n$ states

Why not less than $n+2$? All we need to do is to add one more branch to $B$ to make it DFA.
 A: A simple proof that no DFA with fewer than $2^n$ states accepts $L_n$ is by invocation of the Myhill-Nerode theorem.  The idea is to count the number of distinct language quotients, because each of them must correspond to a distinct state of the minimal DFA for $L_n$.  Let $\Sigma = \{0,1\}$.  Let's recall that the quotient of $L$ w.r.t. word $x$ is defined by
$$ x^{-1}L = \{w \mid xw \in L  \} \enspace. $$
To keep notation at a minimum, let's examine the case of $n=3$.  This means that words whose ends match $1\Sigma\Sigma$ are accepted, while the other words---those whose ends match $0\Sigma\Sigma$ or are shorter than three letters---are rejected.
Let $x$ be a word that ends in $000$.  Then $x^{-1}L_n = 1\Sigma\Sigma$.  The same is true for $|x| < 3$ as long as $x$ contains no $1$.  On the other hand, if $x$ ends in $001$, then $x^{-1}L_n = \Sigma\Sigma \cup 1\Sigma\Sigma$.  Continuing, we get eight different quotients all the way to $(\Sigma^*111)^{-1}L_n = \epsilon \cup \Sigma \cap \Sigma\Sigma \cup 1\Sigma\Sigma$.
This argument generalizes to arbitrary $n$ and shows that the minimal DFA for $L_n$ needs $2^n$ states.
Incidentally, an implementation of the DFA that accepts $L_n$ is an $n$-bit shift register, started from the all-zero state, and with the output taken from the "oldest" bit.
A: Completing the excellent answer of @Fabio Somenzi, $L_n^R$ the reversal is easier to build because you exactly know how to count from the initial state. Hence you need just $n+1$ states.
When turning to $L_n$, you know the beginning of the word but you don't know where the end is, therefore you must check in some sense all the possible subsets of $\{1,2,\ldots,n\}$ (the possible situations before end)
and this set has size $2^n$.
