问题标签 [fsm]

我正在开始编写一个 Java 库来实现高性能有限状态机。我知道那里有很多库，但我想从头开始编写自己的库，因为几乎所有的库都构建了优化的自动机，一次只能处理一个。

我想知道在实现此类高性能库时，SO 社区中涉足状态机设计的人们认为最重要/最好的设计原则是什么。

注意事项

1. 生成的自动机通常并不庞大。（约 100-500 个州）。
2. 不过，实施应该能够扩展。
3. 实现应该能够实现快速转换（最小化、确定等）。
4. 希望实现 DFA、NFA、GNFA、PDA 和可能的 Tree Automata。如果可能的话，希望在单个界面下。
5. 应该在内存使用和性能之间取得很好的平衡。

目前对我来说有关设计的问题是：

1. 应该定义State,Symbol和的类吗？Transition或者应该使用“隐藏”的内部结构。就我个人而言，我觉得像这样使用类会浪费大量内存，因为相同的信息可以以更简洁的形式存储。但是，这是否可以实现更快的转换？它还有其他优点/缺点吗？

2. 在内部存储数据的最佳方式是什么？HashMap使用类似和的数据结构HashSet可以实现分摊的常数时间查找，但会涉及到一个开销元素。这是最好的方法吗？将转换信息存储为原始（或非）数组似乎会浪费大量内存。尤其是当库需要一次处理大量自动机时。不同数据结构的优缺点是什么？

我很感激任何意见。谢谢！

在关于摩尔自动机的维基百科文章中，据说时钟数字电路是摩尔自动机的一种形式。

http://en.wikipedia.org/wiki/Moore_machine#Mechanism

反过来呢。数字电子学中的任意摩尔自动机如何实现，是否有任何规则如何构建电路。或者这从来没有做过？就是想...

我已经看到以下用于在 Verilog 模块中进行状态更改：

state <= 2'b10;

state <= #1 IDLE;

为什么使用 <= 而不仅仅是 =？使用#1 的目的是什么？这有什么不同吗？

这是 FSM 的一些 Verilog 代码，显示了第一个正在使用的代码。如果换成第二个，效果会不会一样？

我为这个电路画了一个有两种状态的mealey机器，但是我不能画一个摩尔机器状态图，我不明白怎么做。

电路如下：

该电路是具有一个二进制输入 X 和一个二进制输出 Y 的摩尔机器。输出 Y 取决于在最近的两个时钟脉冲处采样的两个 X 值。Y 应该始终是这两个输入值的 XOR 组合的结果。

因此，基本上，如果状态为 1，输入为 1，则变为 0。如果为 0，则变为 1，则变为 1。只要与状态相反，它就会变为 1 .

这在状态图上是如何表示的？转换表呢？

我正在研究用 VHDL 创建一个系统，该系统在通过 FTDI usb 到串行设备接收图像后过滤图像。作为其中的一部分，我相信我已经确定了我的 CPLD 应该处于的状态，但我之前从未在 VHDL 中创建过复杂的状态机，所以我质疑我的方法是否合理。目前，我的状态机的基本轮廓是这样的：

我的问题是，我能够在每个上升沿（或类似的，但每个时钟一次）上找到更改状态的每个状态机教程，并且该设备应该经常处于空闲状态，并且只有在 USB_RXFN 变低时才转换到 NEGOTIATING，停留在 NEGOTIATING 直到完成，停留在 RECEIVING 直到整个图像被传输等等......

我的方法是否存在根本性的缺陷？CPLD 是否根本不适合此目的？或者是否有可能在一个状态下停留超过一个时钟，并且为了简单起见，教程只是以这种方式编写的？

只是想知道我是否在 VHDL 中实现了一个有限状态机，是否需要说明所有输出在每种可能状态下的状态？即使我知道某些输出不会从一种状态变为另一种状态，并且我知道状态的顺序也将是相同的顺序？

例如，在这个（强制）示例中：

根据我的理解，如果我不这样做，那么会创建闩锁吗？

在那个例子中这没什么大不了的，但是如果我的机器有超过 10 个输出和超过 10 个状态，那么我的 VHDL 文件开始看起来非常混乱，我确信复制和粘贴一定是不好的做法同样的事情一遍又一遍。有没有更好的方法来做到这一点？

编辑：我可以为输出定义“默认”状态吗？IE 在所有进程之外将 b 设置为 1，然后仅在它为 0 的 case 语句中定义它是什么？那行得通吗？

如果我有一台mealy机器，并且我有一个大字符串，我如何检查mealy机器是否可以生成该字符串？

我考虑过将mealy机器转换为正则表达式，但我也不清楚如何做到这一点。

谢谢你。

我有 erlang gen_fsm，我的第一个状态：

然后我有：

但我没有Test在 shell 中看到注释

如何正确过渡到新状态？

感谢这个伟大网站的人们，我设法将几乎完整且有效的代码放在一起。我有最后一个问题。

这是代码：

我对转换函数 find-next-state 有疑问。如何定义它以测试传入的字符，并基于此在 fsm 达到最终状态时返回真值，或者在没有达到最终状态时返回假值？

谢谢您的回答。

更新：

感谢您的回答，很抱歉代码令人困惑。我已经修复了过渡的定义，现在看起来像这样：

但现在我正在尝试定义转换函数。当我没有固定的过渡字符并且我使用了字符字母时？和 char-numeric?，这些代码行就像一个魅力：

但是我应该改变什么来使用 fsm-trans 中新的状态定义？在 DrScheme 中输入此代码时，会显示错误行：((second (first trl)) ch))。

感谢您的进一步协助！

我是 UML 新手，正在重新定义 FSM 图，如何表示导致相同状态的两个转换，例如，我处于 ​​state1：

我的意思是我需要从 state1 到 state2 画两条线吗？