问题标签 [automata-theory]

只需跟踪自动机所处的状态以及它在输入字符串中的距离，就可以轻松地在输入字符串上模拟非确定性自动机。但是如何模拟非确定性转换器（当然，转换器可以将输入符号转换为输出符号，并给出一个字符串作为输出，而不仅仅是一个布尔值）？这似乎更复杂，因为我们需要以某种方式跟踪输出字符串，由于不确定性，输出字符串可能很多。

我有一个问题，但我还没有找到答案。我需要使用单头磁带对双头磁带图灵机进行在线模拟。我在网上找到了一些文章，说明一个单头磁带不足以解决这个问题，应该使用两个单头磁带进行模拟，但我无法准确模拟两个-head TM 使用这些单头磁带。有没有关于如何做到这一点的想法？谢谢，

听说DFA可以用Loop模拟，NFA可以用递归模拟。我不明白这是怎么回事。谁能给我一个例子？

如何为以下语言构建上下文无关语法：

我开始尝试：

然后A=别的东西......但我无法让它工作。

.

我想知道我们如何才能记住为 no 增加了多少 c 的 shud。b的增加？
例如：

我很难理解我们如何使用线性时间逻辑对这些自动机建模。有人可以请在此链接图片中的案例上向我解释这一点，或者将我指向一个在示例中解释这一点的来源。

我提前感谢您的帮助。

我很难理解 LR(1) 中的前瞻原理 - 项目。如何计算前瞻集？

举个例子，我有以下语法：

然后第一个状态将如下所示：

我知道前瞻是什么，但我不知道如何计算它们。我已经用谷歌搜索了答案，但找不到以简单方式解释这一点的网页。

提前致谢

找不到任何肯定的东西。具有任何 epsilon 转换的 NFA 是 epsilon-NFA 吗？谢谢。

As the question states:

I am trying to understand automata. Can every regular language have a linear bounded automaton?

在所有的图灵机扩展中（例如双向无限磁带、RAM、多个读/写磁头和不确定性），它们中的任何一个都允许 TM 决定以前无法确定的问题吗？

在我的书中说“有不可判定的语言”，证据是：

每个算法都是一个词。那么只有可数算法。但是有无数种语言，因此不仅仅是算法。

为什么说每个算法都是一个词？单词是符号、字母表元素的串联，那么单词和算法之间的关系是什么？谁能给我解释一下？