The regular paperfolding sequence is defined for $n \geq 0 $ per the following rules. $\epsilon_{2n} = (-1)^n$ and $\epsilon_{2n+1} = \epsilon_n$. How would I draw a deterministic finite automaton diagram for a DFA which accepts n if and only if $\epsilon_n = 1$?
I've tried reading input both from left to right, and from right to left, but I can't think of a good way to handle the state transitions. Any hints?
If you want to take $n$ as the input of your automaton, and accept $n$ iff $\epsilon_n = 1$, I think the keyword you're looking for is automatic sequence.
Since the paper-folding sequence is an example a such a ($2-$)automatic sequence, you can indeed find an automaton which tells you what is $\epsilon_n$ when you feed it the binary representation of $n$.
This automaton is depicted here (in french, sorry), and more about this can be found in the link of the OEIS entry (J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182. seems to be particularity indicated)