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.

  • $\begingroup$ Have you tried with a simple pseudo-pseudo-random-sequence generator first? For example, $r(n)=r(n-1)+1 (\text{mod }2)$. $\endgroup$
    – John L.
    Jan 14, 2019 at 5:22
  • $\begingroup$ @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. $\endgroup$
    – Blanco
    Jan 14, 2019 at 9:08

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.