Give the definition of a deterministic finite state automaton and of a regular language.

State and prove the pumping lemma for regular languages.

Let $S=\left\{2^{n} \mid n=0,1,2, \ldots\right\}$ be the subset of $\mathbb{N}$ consisting of the powers of 2 .

If we write the elements of $S$ in base 2 (with no preceding zeros), is $S$ a regular language over $\{0,1\}$ ?

Now suppose we write the elements of $S$ in base 10 (again with no preceding zeros). Show that $S$ is not a regular language over $\{0,1,2,3,4,5,6,7,8,9\}$. [Hint: Give a proof by contradiction; use the above lemma to obtain a sequence $a_{1}, a_{2}, \ldots$ of powers of 2, then consider $a_{i+1}-10^{d} a_{i}$ for $i=1,2,3, \ldots$ and a suitable fixed d.]