问题标签 [finite-state-automaton]

我了解正则表达式是如何得名的，并阅读了相关问题（为什么正则表达式称为“正则”表达式？），但我仍然想知道正则表达式是否总是正则表达式。

例如，反向引用如何是常规的？这是否不需要一些内存，因此不可能由有限状态自动机匹配/生成？

我正在尝试为 L = {w ∈ {a,b}*| 构建一个 npda n a (w) <= 3*n b (w)}。这意味着对于每个b最多可以有 3 个a。

首先，这是我到目前为止所做的。从开始状态开始，我们将一个“ a ”压入堆栈。（在一天结束时，我们需要看到这个“ a ”才能到达最终状态，如果每个 b 有 3 个以上的 a，我们就会弹出这个“ a ”，并且我们不会到达最终状态状态）。

然后对于字符串上的每个b，我会推动 3 个a。对于输入上的每个a我都会弹出一个“ a ”。

最后，如果堆栈上有一个a，我们就进入最终状态。

点击这里查看 npda 图纸

因此，让我们考虑一个字符串，其中 nb(w)= 1 和 na(w) = 3。我们可以有排序为 baaa、aaab、abaa、aaba 的字符串。（还有其他的）

如果我们要为 baaa 运行 npda。这会很好。

什么都不读（lambda）我们推一个. 然后我们读b，然后按aaa。堆栈内容为 (aaaa)。然后我们读取 a 并弹出一个 a。我们这样做 3 次，堆栈变为 (a)。读取字符串后，堆栈上有一个左侧，所以我们可以进入最终状态。

问题在于，这种结构仅在b在a出现在字符串上之前首先向堆栈提供 3 个 a时才有效。如果我们在字符串 aaab 上运行 npda，这将不再有效。我们将在堆栈上有一个 a ，读取第一个a我们必须弹出一个a。读第二个，没有什么可以做的操作。堆栈上没有任何东西，我们不能压入a，因为那会搞砸一切。

我该如何修复这种结构，或者该语言是否有更好的 npda 结构。

我已经为此工作了好几天。帮助将不胜感激。

也知道我对 npda 很陌生，所以可能是我在做一些根本错误的事情。所以，解释清楚。

谢谢

让正则表达式；

将此表达式转换为有限状态机的规则是什么？

这是问题所在：

这是我第一次遇到它时的推理路线：

• 这个好像很难
• 为其查找正则表达式似乎很棘手，因此我无法按照此路径将正则表达式转换为 DFA
• 所以我决定解决问题的第一部分：接受一个“a”个数是 3 的倍数的字符串。这很简单，你只需要 3 个状态：1、2、3，以 1 为起始状态，如果有输入'a'，则进入下一个，如果是'b'，则停留在该状态，并且开始状态也是完成状态。但在本练习中，这 3 个州实际上是 3 个“大”州。然后问题就变成了设计这些“大国”的内部结构以及它们如何相互作用。

我别无选择，只能使用猜测来得出解决方案。这是我想出的（1,2,3 是完成状态，3 是开始状态，如果收到输入“a”，7 和 9 都变为 1）： 我还使用了 DFA 最小化，并发现它已经很小了。但是，教科书给出了另一种解决方案：

但我不明白它是如何正确的！我只是想不通:(。我什至不知道我的解决方案是否 100% 正确。请帮助我，非常感谢 :)

使用开源 Java 自动机库，例如：org.apache.lucene.util.automaton 或 dk.brics.automaton，如何构建自动机进行前缀匹配？

例如：从字符串集 ["lucene", "lucid"] 创建的自动机，在给定 "luc" 或 "luce" 时将匹配，但在给定 "lucy" 或 "lucid dream" 时不匹配。

我需要一个在 FST 运行期间打印/可视化输入/输出对的应用程序。我的意思是，对于 fst 的每个状态，它需要打印出一个元组，其中包含该状态的输入和该状态的输出。现在我可以生成与foma、hfst和xfst fst工具兼容的 fst 文件。所以，我想我需要的可视化工具应该足以兼容其中任何一个。有没有人知道这样的工具？

我找不到以下问题的答案。自动机接受诸如“A:5739”之类的字符串。或“C::399\4342)”，这些提醒我文件系统的路径，但我不确定。

问题文字：

考虑以下用 Prolog 编写的有限状态自动机。 似乎认出了什么？

假设有谓词

当它的参数是字母或数字时，这是正确的。

自动机：

我正在尝试建立一个表格来描述下面描述的硬币兑换机的 FSA 行为。

有一个插槽可以接受 50c 硬币和 2 个按钮，用户可以按下这些按钮来获得 20c 或 10c 硬币作为找零。一旦插入 50c 硬币，机器就会锁定以防止再添加硬币。当用户按下 20c 按钮时，机器检查剩余值是否足够，然后给用户一个 20c 硬币。如果剩余值不够，则机器“死机”（为简单起见）。10c 按钮的工作原理类似。

机器的事件是insert50c, give20c, give10c。

所以，据我了解，这个 FSA 有 6 个状态，比如说 0、10、20、30、40、50。状态由剩余要退还的钱的​​价值来表示。我在这里画了一个粗略的状态图，但我错过了任何转换吗？

我想在一个简单的街头霸王风格游戏中实现一个人工智能，我想用一个有限状态机来做到这一点。举个简单的例子，这个 FSM 有以下状态：

攻击、追逐、逃跑

从我在网上阅读的内容来看，实现这一点的一个好方法是使用枚举，尽管我对如何做到这一点有点困惑。

在任何时候，FMS 都处于当前状态并且应该在游戏中发生变化，这种状态可以通过转换函数 (next()) 改变。使用像下面这样的枚举，我将如何跟踪当前状态，以及在调用 next() 函数时如何进行此更改？

这是我第一次制作有限状态自动机。我尝试制作一个停止灯类型的程序，如果您单击按钮，灯会改变一次，从绿色开始，如果再次单击则变为黄色，然后变为红色，然后再次循环。我设法使它工作，除了一个小错误。在屏幕更新之前需要单击它两次，我真的不知道如何修复它。

我在控制台上注意到，当我单击它时 currentLightState 会发生变化，但在第一次单击时会恢复为以前的颜色。我发现这是因为它与我的状态不同步。但是，当我尝试将 currentLightState 放入类中并分配 this.state.light 时，currentLightState 变得未定义。我尝试在 this.state.light 的末尾添加一个 .bind(this)，但我只是收到另一个错误，说它不是一个函数。有什么建议么？

我没有发布我的更新函数或我的 onHandleClick 函数，因为它不直接处理 currentLightState。

编辑：这是我的 onHandleClick 功能:)

另外，我想我只需用 this.state.light 替换渲染函数中的 currentLightState 就解决了我的问题。

如果这是否是一个合法的修复，我想知道，但它目前似乎有效。

如果有人仍然可以回答为什么当您将 currentLightState 放入类中并将 state.light 分配给它时，它会变得未定义，那就太好了。这将有助于扩展我的 React 知识 :)