# Can the pseudo-random-sequence generator be described as a finite state automaton?

I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot describe a pseudor-andom-sequence generator (e.g. LFSRs) by using $$(Q, \Sigma, \delta, q_{0}, F)$$.

Specifically, the input of the pseudo-random-sequence generator is the seed which is a short string. However its output is a long (or even an infinite) string. Maybe we need construct a FSA with a clock, but I have no idea. And what is $$F$$ (the set of final states) here? I cannot image what is the language of a pseudo-random-sequence generator.

• Have you tried with a simple pseudo-pseudo-random-sequence generator first? For example, $r(n)=r(n-1)+1 (\text{mod }2)$. – John L. Jan 14 '19 at 5:22
• @Apass.Jack It cannot help. Assume that there is a FSA $M$ which achieves it. Thus, $M(0) = (01)^{\infty}$ and $M(1) = (10)^{\infty}$. But if $M(x) = y$, then $|x| = |y| < + \infty$. And maybe there are more than two states: $s_{0}$ denotes that the output is $0$ and $s_{1}$ denotes that the output is $1$. I do not know what should the $F$ be. – TeamBright Jan 14 '19 at 9:08