问题标签 [finite-automata]

Perl 中称为“正则表达式”的字符串解析引擎与书籍中的术语“正则表达式”非常不同。

所以，我的问题是：是否有一些文档描述了 Perl 的正则表达式实现以及它与经典表达式的真正不同之处和方式（经典我的意思是可以真正转换为普通 DFA/NFA 的正则表达式）以及如何有用？

谢谢你。

我正在阅读 UVA 的练习，我需要模拟确定性堆栈自动机，以查看 DSA 在给定条目上是否接受某些字符串，格式如下：

输入的第一行将是一个整数 C，表示测试用例的数量。每个测试用例的第一行包含五个整数 E、T、F、S 和 C，其中 E 表示自动机中的状态数，T 表示转换数，F 表示最终状态数，S 表示初始状态和C 分别为测试字符串的数量。下一行将包含 F 个整数，代表自动机的最终状态。然后是 T 行，每行有 2 个整数 I 和 J 以及 3 个字符串 L、T 和 A，其中 I 和 J (0 ≤ I, J < E) 分别表示过渡状态的起始状态和目的地状态。L 表示从磁带中读取的字符进入过渡，T 表示在堆栈顶部找到的符号，A 表示在此转换结束时使用堆栈顶部执行的操作（用于表示堆栈底部的字符始终为 Z。字符串，或unstack 不考虑栈顶的动作用于转换字符£)。堆栈的字母表将是大写字母。对于链 A，符号从右到左堆叠（与程序 JFlap 的方式相同，即栈的新顶部将是左侧的字符）。然后是 C 行，每行都有一个输入字符串。输入字符串可能包含小写字母和数字（不一定存在于任何转换中）。或 unstack 不考虑堆栈顶部的操作用于转换字符£)。堆栈的字母表将是大写字母。对于链 A，符号从右到左堆叠（与程序 JFlap 的方式相同，即栈的新顶部将是左侧的字符）。然后是 C 行，每行都有一个输入字符串。输入字符串可能包含小写字母和数字（不一定存在于任何转换中）。或 unstack 不考虑堆栈顶部的操作用于转换字符£)。堆栈的字母表将是大写字母。对于链 A，符号从右到左堆叠（与程序 JFlap 的方式相同，即栈的新顶部将是左侧的字符）。然后是 C 行，每行都有一个输入字符串。输入字符串可能包含小写字母和数字（不一定存在于任何转换中）。

每个测试用例第一行的输出必须显示以下字符串“Case G:”，其中 G 表示测试用例的数量（从 1 开始）。如果自动机接受字符串，则在 C 行上打印单词“OK”，否则打印“Reject”。

例如：

这是输出：

我需要一些帮助，或者知道如何模拟这个 DSA，我不是在问我解决问题的代码，因为我想制作自己的代码（这个想法是学习对吗？？），但我需要一些帮助（一些想法或伪代码）开始实施。

我想实现一个复杂的分支逻辑 Android 业务应用程序，用作营销问卷工具，有很多问题，并根据用户的反应在其中进行分支。我很困惑是将对话逻辑实现为 FSM 还是行为树。作者使用树来实现状态机。例如，在 Ian Millington 等人的人工智能游戏中，作者建议将决策树用于 FSM。但是，我认为 FSM 可以有闭包，例如在“发出警报”和“防御”之间进行转换将使其成为图表而不是树。我的第一个问题是树和状态机有什么区别？第二个是什么对我的应用程序来说是一个好的实现，管理高水平的分支复杂性？

我使用 FSM 制作了几个菜单，但界面非常笨拙。为了便于搬迁，我从编程中休息了一年，就在今晚重新编写了我的旧 FSM 代码。

可以在这里看到

我的代码的问题是，每当您更改实现时，都需要对 StateMachine 类和事件处理器进行大量返工。因为这是在嵌入式设备上，所以我不能使用 BOOST::FSM，所以我想编写自己的类，该类足够健壮，可以处理菜单和编程反对数之类的事情（例如，PIC 的 ICSP 是一个简单的 FSM）

你们会如何建议我让我的状态机更有用？

如果我制作一个状态机并想使用这样的界面：

这样，当我处于 state1 并且 FSM 收到 Key_UP 时，程序会打印：

问题是如何在不要求程序员更改数组大小的情况下将状态和过渡信息存储在类中。我在想我可以使用 2D 数组并像往常一样使其成为状态表，并使其更便携，我只需通过使用矢量类型根据需要调整大小来处理事件和状态的添加。向量的问题是没有多少嵌入式设备可以使用内存分配调用。我的第二个选择是使用状态机调用构造函数并将表所需的大小传递给它，但是如果我添加任何新的状态或事件，我也需要更改这些值......

那么我应该如何存储我的状态、事件和函数指针呢？！

您如何确定特定字母表上有多少不同的转换图？例如，字母表 {x, y} 上有多少个 TG。我正在上一堂课，上面有 Daniel IA Cohen 的书“计算机理论导论”中的类似问题。有很多关于如何创建 TG 的示例，但无法确定每种语言可以创建多少个。我假设我正在寻找有限数量的 TG？非常感谢！

确定两个自动机之间等价的最好或最简单的方法是什么？

即，如果给定两个有限自动机 A 和 B，我如何确定两者是否识别相同的语言？

它们都是确定性的或都是非确定性的。

明天考试，教授让我们知道一个问题:)。

在该图的上下文中，L 是 epsilon（空字符串），Z0 是堆栈空符号。

我在确定有关该语言生成的单词的一些规则方面取得了一些进展，但无法确定整个语言。

谢谢！

什么是 Python 最完整的有限自动机库，它能够进行基本操作，例如：

• 最小化，
• 非确定性有限自动机的确定
• 这些自动机生成的语言的并集、交集和乘积等。

我发现的所有库要么不完整，要么不能即插即用。

我现在正在学习计算理论课程。我可以很好地理解这些概念。我能够解决问题。而且，当我向我的导师询问现实世界的应用程序时，他告诉我这些概念在编译器设计中肯定是有用且必不可少的。但是，至少要进行有意义的研究，我需要一些关于如何在我的编码中使用这些概念的解释。

例如，如果我想设计自己的 grep。我将在 C 中使用字符串函数。我不知道如何在编码中使用正则表达式。

同样的情况也适用于图灵机。

如果我想添加两个数字，为​​什么我必须使用那些一元概念。硬件是否实现了这些概念？