问题标签 [automaton]

我有一个 DFA A 和一个 CFG G，然后我必须检查 G 是否生成了 A 不接受（被 A 拒绝）的无限词，以及一个不错的复杂度时间。

我想用 CFG 构建一个图，如果它包含一个有向循环，那么就会产生一个无限的语言。顶点是变量，对于每个产品，我都会画一些边。输入都是被 DFA 拒绝的单词，当我找到一个循环时，我可以说 CFG 生成了被 DFA A 拒绝的无限语言。

我不知道如何在算法中转换它，或者如果我的建议不正确，我必须创建一个新的。

编辑：我可以将我的 cfg 转换为 CNF，然后转换为 DFA（使用 chomsky）。之后，我尝试找到一个循环。但是我转换后的 dfa 的状态可能比我的 dfa a 少……我认为我需要如何在我的 cfg 中获得 DFA A 拒绝的单词。

我制作了从正则表达式 3d 数组生成的 NFA，例如 (01*) 表达式。我得到它：

如何编写可以测试满足此自动机的字符串的方法？例如"011111"将返回q0 q1 q2 q3 q2 q3 q2 q3 q2 q3 q2 q3 q4

我只有非常基本的 Maple 技能，不确定如何以图形方式将矩阵表示为块，其中矩阵中的 1 对应于块，0 对应于空白空间。

请参阅下面的代码，我在其中添加一个“1”，即循环中的中央列的块。我想知道这是否可以在枫木中进行动画处理，将“1”作为实心方块。

这是某人使用不同软件取得的成果的图片。任何帮助将不胜感激，谢谢。

我必须证明“半可判定语言被直接态射运算封闭”

我认为从 E 到 F 的直接态射是一对态射 s: E -> F, p: F->E, 其中 p · s = IdE。

所以我的建议是用图灵机做一个证明，因为图灵可识别的语言在∪、°、*和∩下是封闭的，但我不知道如何用在 TM 中运行的特定语言来证明它（如果我的建议是正确的） .

我正在阅读这本书：介绍计算理论并被困在这个例子上。

通过首先将 DFA 转换为 GNFA（广义非确定性有限自动机），然后将 GNFA 转换为正则表达式，将 DFA 转换为等效表达式。

这是示例： 在此处输入图像描述

我应该递归地使用它来到达第四个状态： 在此处输入图像描述

不幸的是，我无法理解从 b 到 c 发生了什么？我只知道我们正在尝试摆脱状态 2，但是我们如何从 b 到达 c 呢？

非常感谢！

根据 Sipser 的《计算理论导论》：如果 A 是机器 M 接受的所有字符串的集合，我们说 A 是机器 M 的语言，写成 L(M) = A。我们说 M 识别 A ...一台机器可以接受多个字符串，但它总是只能识别一种语言。并且我们说如果 A = {w| 则 M 识别语言 A M 接受 w}。

我想这个问题已经得到了回答，但我想知道是否有人对此有任何想法，如果我们可以说关于常规语言的子集有什么有趣的事情，是否可以说原始 DFA 识别它们并且原始 DFA 和识别较小语言的 DFA 之间是否存在任何有趣的关系

我有一个串行版本的 BML，我正在尝试用 OpenMP 编写一个并行版本。基本上，我的代码使用main一个循环调用两个函数来进行水平和垂直移动。像那样：

cur当前网格在哪里。那么水平和垂直函数是类似的，并且有一个嵌套循环：

该代码在每一步都会生成一个 ppm 图像，并且通过某个输入，串行版本会生成一个我们可以认为是好的输出。但是#pragma omp parallel for在两个函数 H 和 V 中使用时，ppm 文件的结果分为线程数（即 4）等区域：

我想问题是每个线程都应该在白蚁之前按顺序执行这两个功能，因为 movememnts 是严格连接的。我不知道该怎么做。如果我像在主循环之前那样将 pragma 设置为更高级别，则没有加速。显然 ppm 文件不能像图像一样被切片。

第一个来自 JavaScript 背景的 C++/Arduino 项目。我对这段代码有一些问题！我收到此错误：

这是cpp：

我曾尝试制作change_callback一个静态函数，但随后会导致错误fade_val，这是一个公共类成员。我有一种感觉，这与指针有关，我仍在纠结。重要的是每个 Pad 实例都有自己的传感器和自己的 fade_val - 它们不能在每个 Pad 之间共享（静态）。

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

问题文字：

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

假设有谓词

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

自动机：

我目前正在阅读 Nancy Lynch 关于分布式系统的书，关于 IO 自动机的章节。我有以下与书籍练习 8.13(c) 相关的问题。

给定一些自动机 A，其中 sig(A) 为空。Traces(P) 是 {1,2} 上的序列集，其中每次出现 1 都紧跟在 2 之后。我需要证明 P 既不是安全属性也不是活性属性。并明确表明 P 可以表示为 S 和 L 的交集。

这是我的问题：我可以证明 P 不安全，因为它破坏了前缀封闭的属性，例如 {2,1,2} 没有属于 P 的前缀（它应该是 {...,1} 的形式P) 是不可能的。但我不知道如何处理 L 属性——要么是空的，要么包含 trace(P)——trace(P) $\subset$ trace(L)。如果它为空，则 traces(P) 为空，因为 traces(P)= traces(S) $\cap$ traces(L) 这是错误的。所以我认为痕迹（P）是痕迹（L）的子集。

我关于痕迹（L）的结论是否正确？

对于这个问题，我如何明确表达 traces(P)=traces(S) $\cap$ traces(L) ？

提前致谢。