状态机压缩

State machine compression

我有一个给定输入的输出日志，例如：

0 =A=> 1 =B=> 1 =B=> 0 =A=> 1 =A=> 0 =A=> 0

我想找到代表它的最小状态机。

我尝试手动将其分解为有序的转换列表：

  1. 0 =A=> 1
  2. 1 =B=> 1
  3. 1 =B=> 0
  4. 0 =A=> 1
  5. 1 =A=> 0
  6. 0 =A=> 0

如果我们认为只有两种状态：

列表变为：

  1. q0 (0) =A=> q1 (1)
  2. q1 (1) =B=> q1 (1)
  3. q1 (1) =B=> q0 (0)
  4. q0 (0) =A=> q1 (1)
  5. q1 (1) =A=> q0 (0)
  6. q0 (0) =A=> q0 (0)

我们可以看到，从状态 q0，输入 A 在第 1 行和第 4 行导致 q1，但在第 6 行导致状态 q0。 q1 状态与操作 B 中的相同问题。 所以我必须创建两个额外的状态 q2 输出 0，以及 q3 输出 1。 然后我可以按以下方式重写列表：

  1. q0 (0) =A=> q1 (1)
  2. q1 (1) =B=> q3 (1)
  3. q3 (1) =B=> q0 (0)
  4. q0 (0) =A=> q1 (1)
  5. q1 (1) =A=> q2 (0)
  6. q2 (0) =A=> q0 (0)

完成。

手工看起来很简单，但我找不到实现给定转换列表的算法。 我知道这个例子有几个解决方案，但我需要能找到一个。

我考虑过将其视为优化问题并使用例如模拟退火或遗传算法，但这似乎有些矫枉过正。 另外，我真的觉得有一个简单的方法可以做到这一点，也许与图论有关？

编辑：

感谢@sascha 的评论，现在我知道以下列表描述了一个非确定性有限状态自动机 (NDFA)：

  1. q0 (0) =A=> q1 (1)
  2. q1 (1) =B=> q1 (1)
  3. q1 (1) =B=> q0 (0)
  4. q0 (0) =A=> q1 (1)
  5. q1 (1) =A=> q0 (0)
  6. q0 (0) =A=> q0 (0)

有一些算法可以将其转换为确定性有限状态自动机 (DFA)，请参阅 NDFA to DFA conversion

我明天会尝试，但是，我担心我得不到与此 NDFA 等效的最小 DFA。

我找到了一种方法来做我想做的事情（至少在这个例子中有效）：

一个。从输出日志 0 =A=> 1 =B=> 1 =B=> 0 =A=> 1 =A=> 0 =A=> 0 我构建了一个转换列表：

  1. q0 (0) =A=> q1 (1)
  2. q1 (1) =B=> q2 (1)
  3. q2 (1) =B=> q3 (0)
  4. q3 (0) =A=> q4 (1)
  5. q4 (1) =A=> q5 (0)
  6. q5 (0) =A=> q6 (0)

乙。我把它转换成状态 table:

 q  │ A  │ B  │ Output
────┼────┼────┼────────   
 q0 │ q1 │ ── │ 0     
────┼────┼────┼────────   
 q1 │ ── │ q2 │ 1     
────┼────┼────┼────────   
 q2 │ ── │ q3 │ 1     
────┼────┼────┼────────   
 q3 │ q4 │ ── │ 0     
────┼────┼────┼────────   
 q4 │ q5 │ ── │ 1     
────┼────┼────┼──────── 
 q5 │ q6 │ ── │ 0     
────┼────┼────┼────────   
 q6 │ ── │ ── │ 0

C。然后我使用Moore Reduction Procedure。由于机器未完全指定，因此必须做出选择。

P0 = [{q0, q1, q2, q3, q4, q5, q6}]

P1 是按输出分组的状态列表：P1 = [{q0, q3, q5, q6}, {q1, q2, q4}]

P1[0] 是 {q0, q3, q5, q6}:

  • q0(A) = q1 ∈ P1[1]
  • q0(B) = ?
  • q3(A) = q4 ∈ P1[1]
  • q3(B) = ?
  • q5(A) = q6 ∈ P1[0]
  • q5(B) = ?
  • q6(A) = ?
  • q6(B) = ?

所以q0和q3是兼容的，q5是不兼容的。 q6 可以兼容这些状态中的任何一个，这里我们将选择 q6 与 q0 和 q3.

分组

P1[1] 是 {q1, q2, q4}:

  • q1(A) = ?
  • q1(B) = q2 ∈ P1[1]
  • q2(A) = ?
  • q2(B) = q3 ∈ P1[0]
  • q4(A) = q5 ∈ P1[0]
  • q4(B) = ?

所以 q1 和 q2 彼此不兼容。 q4可以兼容这些状态中的任何一个，这里我们选择将q4和q1组合在一起。

所以我们有 P2 = [{q0, q3, q6}, {q5}, {q1, q4}, {q2}]

P2[0] 是 {q0, q3, q6}:

  • q0(A) = q1 ∈ P2[2]
  • q0(B) = ?
  • q3(A) = q4 ∈ P2[2]
  • q3(B) = ?
  • q6(A) = ?
  • q6(B) = ?

因此q0、q3和q6仍然相互兼容。

P2[1]是{q5}：q5与自身兼容。

P2[2] 是 {q1, q4}:

  • q1(A) = ?
  • q1(B) = q2 ∈ P2[3]
  • q4(A) = q5 ∈ P2[1]
  • q4(B) = ?

所以q1和q4仍然相互兼容。

P2[3] 是 {q2}: q2 与自身兼容。

所以我们有 P3 = [{q0, q3, q6}, {q5}, {q1, q4}, {q2}] = P2.

我们现在有以下状态table

  q            │ A            │ B            │ Output
 ──────────────┼──────────────┼──────────────┼────────   
  {q0, q3, q6} │ {q1, q4}     │ ──────────── │ 0     
 ──────────────┼──────────────┼──────────────┼────────   
  {q1, q4}     │ q5           │ q2           │ 1     
 ──────────────┼──────────────┼──────────────┼────────   
  q2           │ ──────────── │ {q0, q3, q6} │ 1     
 ──────────────┼──────────────┼──────────────┼────────   
  q5           │ {q0, q3, q6} │ ──────────── │ 0

还有...瞧！

感谢您的评论，他们确实帮助我在搜索引擎上做出正确的查询。

编辑：由于必须做出选择，因此有理由假设这种方法通常不是最优的。为了让它成为最优，我想唯一的办法就是尝试所有的选择组合，然后选择最好的一个。