# 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)$. – Apass.Jack Jan 14 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 at 9:08

## 1 Answer

A finite-state automaton can output an unending sequence of outputs, so you don't need to do anything special. The regular language will contain all prefixes of possible output streams.

If you really want to consider infinite strings, you could use Büchi automata to model that. Personally, I don't see the point.