I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion to the number of states (fewer states more probable). Alphabet = {0,1}

Can you please suggest how to implement this enumeration, encoding / decoding.

Something similar to how in Kolmogorov complexity there is an enumeration for Turing machine programs.


One simple encoding is to represent each of the $N$ states by a partial function $f_n:\{0,1\} \rightarrow \{1, \dots, N\}$. Input $x$ in state $n$ will cause a transisition to state $f_n(x)$ if $f_n(x)$ exists and an error condition if not. You can assume that the initial state is always state $1$.

For $N$ states there are $(N+1)^2$ such partial functions (because either $0$ or $1$ or both may fail to have an image), so there are $(N+1)^{2N}$ encodings. However, some of the encodings will represent FSMs that are isomorphic (because they represent the "same" FSM with a re-labelling of states).

For example, for $2$ states there are $9$ partial functions from $\{0,1\}$ to $\{1,2\}$ and each state can be represented by one of these partial functions, so there are $9^2=81$ representations of FSMs. The $2$ state FSM which stays in the same state on input $0$ and changes to the opposite state on input $1$ is represented by the two functions

$f_1(0)=1 \quad f_1(1)=2\\ f_2(0)=2 \quad f_2(1)=1$

  • $\begingroup$ can you please provide an example for 2 states FSM? $\endgroup$
    – Oleg Dats
    Jul 14 '20 at 16:14
  • $\begingroup$ @OlegDats I have added an example to my answer. $\endgroup$
    – gandalf61
    Jul 14 '20 at 18:02
  • $\begingroup$ thank you for the update. Can you explain: for 2 states and |Alphadet|=2 we have a Number of different FSMs = 2^2n=2^4=16. As far as I understand you have a different formula. For 16 different FSMs, I was expecting A=['0000', '0001',...]. then Decode(A[0]) -> FSM. But it should be extended by different final states. $\endgroup$
    – Oleg Dats
    Jul 15 '20 at 8:23
  • $\begingroup$ @OlegDats There are several alternative definitions of an FSM. If the definition you are using does not include error conditions (i.e. the FSM accepts all possible strings in its given alphabet) then each state is represented by a complete function not a partial function, and the formula for the number of FSMs with $N$ states is $N^{2N}$. For 2 states, without error conditions, there are then indeed $2^4=16$ different representations of FSMs. $\endgroup$
    – gandalf61
    Jul 15 '20 at 8:44
  • 1
    $\begingroup$ @OlegDats Sorry, I don't understand some of the terms you are using, so I don't think I can help you any further. I suggest you submit a new question, explaining your problem and how far you have got with it in more detail. Then maybe someone else will be able to help. $\endgroup$
    – gandalf61
    Jul 15 '20 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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