问题标签 [automaton]

维基百科指出，确定性状态自动化“为每个输入字符串生成自动机的唯一计算（或运行）”。

我一直理解这一点，因为只有 1 种可能的路径来计算任何唯一的字符串。在这种情况下，以下是 DSM。

但是现在我想多了，并将描述解释为每个输入字符串都有一个可能的路径，并且该路径与所有其他输入字符串都是唯一的。在这种情况下，以下不是 DSM，因为“11”和“12”遵循相同的路径。

所以我的问题是，以下是 DSM 还是 NDSM？

我正在为自动机理论做作业，我必须确定一个词是否被确定性有限自动机的转移函数接受

我有这个输入文件：

输入以 4 个整数开头，第一个是自动机的状态数，接下来是自动机的转移数，第三个数字是初始状态，然后是最终状态数。然后是最终状态（在示例中，最终状态是 2 和 5）。

然后是 N 行（N 是转换的数量），每行有 2 个整数和一个字符 I、J 和 C，表示转换的状态，即转换从状态 i 到状态 J，字符 C。在这一行之后是一个整数 S，它将包含要测试的字符串的数量，然后是 S 行与相应的字符串。

这个程序的输出应该是：

它应该说明字符串是被接受还是被拒绝。到目前为止，我只使用输入对工作进行了编码。

我不知道如何最方便地表示 automaton。我应该简单地使用数组吗？我会对数组应用什么逻辑？在事先不知道自动机字母表的情况下，有什么办法可以做到吗？我需要一个数据结构来表示自动机吗？我对这个任务有点坚持，并且想要一些想法，一些伪代码或想法来完成它。代码是另一种语言吗？我不想要解决方案，因为我想做我的任务，但如果我可以使用一些帮助

正如我在这篇文章中解释的那样，我正在做一个模拟非确定性有限自动机的任务。我从文件中读取了这个输入tarea4.in：

输入的第一行是一个整数 T，表示要评估程序的案例数。每个测试用例以 4 个整数开头，第一个是自动机的状态数，接下来是自动机的转换数，第三个数字是初始状态，然后是最终状态数。然后是最终状态（在示例中，最终状态是 2 和 5）。然后是 F 行，每行都有一个整数 E，表示 E 是一个最终状态。

然后是 N 行（N 是转换的数量），每行有 2 个整数和一个字符 I、J 和 C，表示转换的状态，即转换从状态 i 到状态 J，字符 C。在这一行之后是一个整数 S，它将包含要测试的字符串的数量，然后是 S 行与相应的字符串。

预期的输出是：

产生我的代码的输出：

这是我的代码：

我的问题是：为什么我得到不正确的输出？我认为这是因为测试用例中定义的自动机的不确定性，但是我如何正确评估字符串？如何evaluate_string以某种方式将调用的函数更改为检查可以使自动机通过非确定性评估字符串的不同路径？

我已经坚持了好几天了，老实说，我有点绝望。

几天来，我试图做一个程序来模拟一个不确定的有限自动机（NFA），更具体地说，一个字符串识别器。在几次失败后，感谢用户Konrad Rudolph，我可以根据这个伪代码实现一个解决方案：

好吧，在 NFA 中，您有一组当前状态，并且在每个步骤中，您都会遍历所有当前状态，并且为每个状态选择所有有效转换。这些组合集形成了您的新状态集。

最后，检查当前状态和接受状态的交集是否为非空。

在伪代码中，如下所示：

这可以逐行翻译成 C++ 代码。他建议让这个简单，使用std::set<int> for the current and next sets

这是我在 C++ 中的实现：

我有这个输入：

预期的输出是：

但是，我的代码作为输出生成：

而对于测试用例的最后一个字符串，程序什么也不做，只是不停止运行。我的问题是为什么我的程序会因这个特定的输入而崩溃。我在JFlap中设计了相同的自动机 NFA并识别了最后一个输入

呸呸呸呸

.

我在执行代码时犯了什么错误？

在 Haskell 中表示有限自动机的好方法是什么？它的数据类型如何？

在我们大学，自动机被定义为一个 5 元组

其中 Q 是自动机状态的集合，X 是字母表（这部分是否必要），delta 是从 (Q,X) 获取 2 元组并返回 state/-s 的转换函数（在非确定性版本中）和F 是接受/结束状态的集合。

最重要的是，我不确定delta应该有什么类型......

我正在做两个自动机的组合（实际上它是一个换能器）。因此，我想直观地表示它来分析它。

哪个是最好的工具/库？

人们建议我使用 dot 和 graphviz。哪个更好？我正在用 OCaml 编写代码。那有什么图书馆可以画吗？

这是我要绘制的示例换能器？

我正在尝试使用 TAP（测试任何协议）作为我们的测试结果格式。但是，需要将一些日志文件附加到测试结果中。我正在寻找一种好的做法来实现这一目标。

例如，我有一个 tap 文件和两个日志文件：a.log、b.log

有没有什么好方法可以将日志文件内容插入到这个 tap 文件中？谢谢。

我想在mathematica中创建一个模块，如果自动机是确定性的则返回。我正在考虑，如果有 2 个转换从同一状态开始并读取相同的符号，或者存在一个空转换，则自动机不是确定性的。

我想调试这段代码，但我不能：

A 是一个自动机，其中第一个元素是状态列表，第二个是字母表，第三个是转换，第四个是初始状态，第五个是最终状态列表。

主要问题是，当我将函数应用于 A 时，它永远不会结束。

编辑：已解决

这是最终代码：

我是学生，在我的编程课程中，我们必须学习 Haskell。所以我是新手，我没有那么多经验。另外我不熟悉在论坛上发布问题。

所以首先我会发布图书馆，我必须与之合作。（DA：确定性自动机）

toDA 函数在其列表表示中采用自动机并将其转换为自动机。此功能和图书馆的其余部分由讲座主席提供。

现在的问题是写一个类型的函数

该函数接受一个自动机、一个状态和一个字符串，并在读取字符串后返回自动机的状态。

到目前为止，这个想法很清楚。DA 型自动机有一个状态转移函数增量。所以函数“advance”必须以某种方式调用那个 delta 函数。但是我怎样才能访问一个集成在一个类型中的函数呢？

我试图以多种方式解决这个问题，并在几个地方都没有答案。问题如下：

[问题]
给定两种常规语言（可以称为有限描述语言，idk）L1和L2，我们定义一种新语言如下：

我应该用来证明L is regular，但是我有以下限制：

• 我必须使用 Equivalence 类，别无他法

• 我不能使用Rank(L)，如显示对等价类数量的限制，而是必须显示它们

• 我可以使用所有常规语言都拥有的闭包属性

我并不期待一个完整的证明（尽管这将不胜感激），而是对如何去做这样的事情的解释。
提前致谢。