问题标签 [finite-automata]

我想用 C 构建一个词法分析器，我正在关注龙书，我可以理解状态转换，但如何实现它们？

有更好的书吗？

事实上，我必须通过多个状态解析一个字符串，这样我才能判断该字符串是否可以接受！

1. 你如何找到最小的确定性 FSM？
2. 有没有办法标准化非确定性 FSM？
3. 是否有线性时间限制算法来找到给定机器的最小 FSM？
4. 有没有办法查看两个 FSM 是否等效？

这不是一个家庭作业问题。我正在看这个系列讲座，只是很好奇。

有没有人有一个用 Objective-C 代码编写的基本、紧凑的有限状态机/自动机的解决方案？

我对可重用组件感兴趣，因此 FSM 添加了状态并定义了使用可重用状态类的操作。

Marvin Minsky在我的口语考试中问了我以下问题：

当蚂蚁走路时，它每走一步就会打印一个二进制数（例如，101）。二进制数的最小长度是多少，以数字为单位，可以在不查看字符串的开头或结尾的情况下判断蚂蚁的行进方向？蚂蚁告诉你二进制数。

示例：蚂蚁的二进制数是 101，因此蚂蚁留下的轨迹如下所示：101101101101101101101。请注意，无法判断蚂蚁的行进方向。因此，这个特定的数字不起作用（但可能有一个三位数的二进制数）。

示例：蚂蚁的二进制数是 011，因此蚂蚁留下的轨迹如下所示：011011011011011011。同样，如果不查看字符串的末端，就无法判断蚂蚁的行进方向。

这个问题的答案是什么？请注意，答案不能只是一个有效的二进制数示例。答案需要包含一个证明，证明长度小于 n-1 的二进制数不会起作用，其中 n 是起作用的示例二进制数的长度。详尽列举的证明是可以的，但令人不快。:)

您可以阅读这个问题，我在其中询问有关机器应用程序的最佳架构的小背景故事，尽管这对于帮助我解决这个问题并不是完全必要的。

我对有限状态机的理解（尤其是实现）有点年轻，可能还有些欠缺，但我正在将这个应用程序作为一个应用程序来实现，而且我有一个地方需要嵌套 FSM。基本上机器有一些高级状态（冷[又名刚开始]，归位，设置，准备运行，运行，报告，重置）但是当机器运行时，它需要有它自己的小 FSM 实现（加载镜头、定位边缘、测量楔形、测量圆度和完整 [可能还有更多内容]）。

我的问题是：我是否应该建立具有“嵌套状态”的能力，其中状态可以具有子状态列表并且系统可以进入这些子状态并且这些子状态可以返回到父状态？或者我应该将 FSM 实现放在 Running 状态中，并将它们保持为两个不同的 FSM？还是您认为我在做或在想一些愚蠢的事情，应该重新考虑？

欢迎大家提出想法、建议、批评和建议。

我已经阅读了一个包含符号、状态和转换的文本文件，并将它们全部放在一个表格中。它看起来像这样：
符号 a、b
状态 q1、q2、q3、q4
开始状态 q4
最终状态 q2、q3

过渡状态：
q4, epsilon, q1
q1, a, q2
q3, a, q3
q3, b, q1

我已经阅读了有关如何将 NFA 转换为 DFA 的算法，但我并不真正了解该算法。我将如何创建转换方法以及我应该有什么状态类？

我最近阅读了有关boost::statechart库（有限状态机）的内容，我喜欢这个概念。

C# 有类似的机制吗？还是可以使用特定的设计模式来实现？

有限自动机有什么用？以及我们在计算理论中研究的所有概念。我还没有看到它们的用途。

考虑一个类似于 pac-mac 的游戏，我们想用 FSA 图来表示它。我们有一个迷宫（桌子），里面有随机位置的浆果。目标是吃掉迷宫中的所有浆果。我们必须考虑的控制命令如下：
GOAHEAD、LEFT、RIGHT、CHECKBERRY（检查吃豆人前面是否有浆果）、EAT 和 OFF-MAZE。
我们需要最多 10 个阶段......并且请记住，我们不能连续有多个间隙。谢谢

编辑： 替代文字 http://img338.imageshack.us/img338/2479/graphp.jpg

好吧。我创建了图表，但找不到跨越间隙的方法。例如：在迷宫中，经过一排浆果后，突然前面出现了一个缺口，下一个浆果就在缺口的下方。所以我不确定我的图表会是什么样子，即使我向左或向右转 checkberry 命令也不会返回 TRUE 值。所以必须有一种方法让吃豆人在不吃东西的情况下移动到间隙广场，但它如何决定是移动到前面的那个还是其他的？

我想开发一个工具来构造任何有限自动机的转换图，给定它的转换表，使用Lex 和 Yacc的开始状态和最终状态。工具还应提供检查自动机是否接受字符串的工具。

谁能告诉我该怎么做。