如何定义一组有限状态机的枚举？

Question

我想编写一个函数，将n（最大状态的状态）作为参数枚举，最多可以枚举n个状态的所有可能的有限状态机，并返回随机的随机fsm与状态数量成比例（更少状态更可能的）。字母= {0,1}

您可以建议如何实现此枚举，编码/解码。

类似于Kolmogorov复杂程度如何进行图灵机程序的枚举。

Answer 1

一个简单的编码是通过部分函数 $ f_n：\ {0 ，1 \} \ lightarrow \ {1，\ dots，n \} $ 。输入 $ x $ 在状态 $ n $ 将导致转换到陈述 $ f_n（x）$ 如果 $ f_n（x）$ 存在，如果不是，则存在错误条件。您可以假设初始状态始终是状态 $ 1 $ 。

对于 $ n $ 状态有 $（n + 1）^ 2 $ 这样的部分函数（因为 $ 0 $ 或 $ 1 $ 或两者都可能没有映像），所以有< SPAN Class=“Math-Container”> $（n + 1）^ {2n} $ 编码。但是，一些编码将代表是同构的fsms（因为它们代表了具有重新标记状态的“相同”FSM）。

例如，对于 $ 2 $ 状态有 $ 9 $ 部分函数来自 $ \ {0,1 \} $ 到 $ \ {1,2 \} $ ，每个状态都可以由一个表示在这些部分函数中，因此有 $ 9 ^ 2= 81 $ fsms表示。 $ 2 $ 状态fsm，它在输入 $ 0 $ 上保持在相同状态，并更改为相反的状态输入 $ 1 $ 由两个函数表示

$ f_1（0）= 1 \ quad f_1（1）= 2 \\ f_2（0）= 2 \ quad f_2（1）= 1 $