问题标签 [finite-automata]

首先，这不是要求算法将 NFA 转换为 DFA 的问题。

已知（并证明）一个 NFA 的等效 DFA 最多有 2 ⁿ个状态，尽管大多数时候它的状态数与 NFA 或多或少相同。

我如何预测 NFA 等效 DFA 将具有的状态数的估计值？哪种特定类型的 NFA 需要等效的 DFA 才能具有 2 ⁿ个状态？

我提出这个问题的原因是能够“发明”一些 NFA，这些 NFA 肯定会在不考虑最小化的情况下产生 2 ⁿ - 1 个状态加上“死状态”。

出于好奇，我试图确定我使用的系统的计算模型在功能上等效，并证明等效性。我在这个问题上花费的时间越长，我就越怀疑这个系统不是图灵等效的。我对图灵机和递归可枚举语言的理解很好，但我对功能较少的自动机（例如下推自动机）了解不多，所以我不知道如何进行。

首先，任何人都可以推荐一个好的资源来学习不同的计算模型吗？我对语法、语言和自动机，以及如何证明它们之间的等价和差异感兴趣。理想情况下，资源会非常详细地分解每个模型的所有元素并进行比较。

其次，在尝试将系统拟合到任何这些计算模型时，是否应该使用通用方法或框架？

我正在为考试准备无上下文语法。我不明白为什么语言

是上下文无关的，但不是常规的。为什么不规律？我们什么时候可以说表达式不规则？

谢谢

我想测试两种语言是否有共同的字符串。这两种语言都来自下面描述的常规语言的子集，我只需要知道两种语言中是否存在字符串，而不是生成示例字符串。

语言由类似 glob 的字符串指定，例如

/foo/**/bar/*.baz

where**匹配 0 个或多个字符，并*匹配零个或多个非 字符/，并且所有其他字符都是文字。

有任何想法吗？

谢谢，迈克

编辑：

我实现了一些似乎表现良好的东西，但还没有尝试过正确性证明。你可以看到源代码和单元测试

我正在寻找一个可以绘制 FSM 或 Automata 的基于开源GUI 的应用程序。有人知道吗？

我正在研究一个状态机，它应该提取表单的函数调用

提取的数据将pref("this.is.a.string.which\"can have QUOTES\"", 123456); 来自文件的位置。目前，要处理一个 41kb 的文件，这个过程需要将近一分半钟的时间。我在这里对这个有限状态机有什么严重误解吗？

比利3

编辑：嗯，这是我见过的最奇怪的事情之一。我刚刚重建了这个项目，它又可以正常运行了。奇怪的。

我正在为我的计算理论课程复习一些笔记，我有点坚持展示以下陈述，我希望有人可以帮助我解释:)

设 A 为正则语言。语言 B = {ab | a 存在于 A 而 b 不存在于 A*} 为什么 B 是常规语言？

有些观点对我来说是显而易见的。如果 b 只是一个常量字符串，这是微不足道的。由于我们知道 a 在 A 中并且 b 是一个字符串，因此常规语言在联合下是封闭的，因此联合接受这两个字符串的语言显然是常规的。但是，我不确定 b 是恒定的。也许是这样，如果是这样，那么这不是一个真正的问题。我很难理解它。谢谢！

考虑以下 FST：

我如何对这两个FST（即T1 o T2）执行合成操作我看到了一些算法但不太了解。如果有人能以简单的方式解释它，那将是一个很大的帮助。

请注意，这不是家庭作业。该示例取自给出解决方案的演讲幻灯片，但我不知道如何解决。

在阅读一些关于循环神经网络的图灵完备性的论文时（例如：Turing computability with neural nets，Hava T. Siegelmann 和 Eduardo D. Sontag，1991），我觉得那里给出的证明并不是真的那样实际的。例如，参考论文需要一个神经网络，其神经元活动必须具有无限精确性（以可靠地表示任何有理数）。其他证明需要一个无限大小的神经网络。显然，这并不是那么实际。

但我现在开始怀疑，要求图灵完备是否真的有意义。按照严格的定义，现在没有一个计算机系统是图灵完备的，因为它们都无法模拟无限磁带。

有趣的是，编程语言规范最常将其打开，无论它们是否完整。这一切都归结为他们是否总是能够分配更多内存以及函数调用堆栈大小是否无限的问题。大多数规范并没有真正指定这一点。当然，所有可用的实现都在这里受到限制，因此编程语言的所有实际实现都不是图灵完备的。

因此，您可以说所有计算机系统都与有限状态机一样强大，仅此而已。

这让我想到了一个问题：图灵这个术语到底有多大用处？

回到神经网络：对于神经网络（包括我们自己的大脑）的任何实际实现，它们将无法表示无限数量的状态，即根据图灵完备性的严格定义，它们不是图灵完备的。那么，如果神经网络是图灵完备的，这个问题是否有意义呢？

它们是否与有限状态机一样强大的问题已经在更早的时候得到了回答（Minsky 于 1954 年给出的答案：是的），而且似乎也更容易回答。即，至少在理论上，这已经证明它们与任何计算机一样强大。

其他一些更多关于我真正想知道的问题：

• 是否有任何理论术语可以更具体地说明计算机的计算能力？（鉴于其有限的内存空间）

• 您如何将神经网络的实际实现与计算机的计算能力进行比较？（如上所述，图灵完备性没有用。）

您如何实现 FSM（编辑：有限状态机）状态？我通常认为 FSM 像一组函数、一个调度程序和一个线程来指示当前的运行状态。意思是，我确实阻止了对代表状态的函数/函子的调用。

刚才我以不同的风格实现了一个，我仍然用函数（对象）表示状态，但是线程只是调用一个state->step()方法，它试图尽快返回。如果状态已经完成并且应该发生转换，它会相应地指示。我将其称为“轮询”样式，因为这些函数大多看起来像：

我知道它是 FSM 中的 FSM。

感觉比较简单，但是有一定的优势。虽然线程被阻塞或处于某种 while (!CanGoForward)checkGoForward(); 循环中可能很麻烦且笨拙，但轮询感觉更容易调试。那是因为FSM对象在每一步之后都会重新获得控制权，并且发布一些调试信息是轻而易举的事。

好吧，我偏离了我的问题：你如何实现FSM 的状态？