Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata? Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes representing accept states, and two directed edges labeled 0, 1 coming out of each node. It changes state in the natural way as it reads input. Given an $\epsilon$, find $f:\{0,1\}^{k}\to \{0,1\}^n$ such that for every $d$-state finite automaton computing some function $A$, $$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|< \epsilon.$$ Here $U_k$ denotes the uniform distribution on $k$ variables, and we want $k$ to be as small as possible (e.g. $\log n$). I'm thinking of $d$ being on the order of $n$, though we can also ask the question more generally (ex. would the number of bits required grow with $n$?). Some backgroundConstruction of pseudorandom generators is important in derandomization, but the general problem (PRG's for polynomial-time algorithms) has so far proved too difficult. There has however been progress on PRG's for bounded-space computation. For example this recent paper (http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf) gives a bound of approximately $\log n\log d$ for regular read-once branching programs. The question with general read-once branching programs is still open (with $k=\log n$), so I'm wondering if the answer for this simplification is known.  (A finite automaton is like a read-once branching program where every layer is the same.)
Pseudorandom generator for finite automata
automata theory;pseudorandomness;pseudorandom generators