(a) Define
\mathcal{L}_{n}=\left\{x \mid x \in\{0,1\}^{*} \text { and the } n^{\text {th }} \text {-symbol from the left is a } 1\right\}
Show that there is some constant number c (independent of n ) such that there is a DFA that accepts \mathcal{L}_{n} with at most n+c states.
(b) Define
\mathcal{R}_{n}=\left\{x \mid x \in\{0,1\}^{*} \text { and the } n^{\text {th }} \text {-symbol from the right is a } 1\right\} \text {. }
Show that any DFA that accepts \mathcal{R}_{n} has at least 2^{n} states.