问题标签 [automata]

我想应用 BNF 语法的规则来产生推导：a_Num

我有一个问题，我真的需要能够使用有限自动机作为关联容器的键。每个键实际上应该代表一个自动机的等价类，因此当我搜索时，我会找到一个等价的自动机（如果存在这样的键），即使该自动机在结构上并不相同。

一个明显的最后手段当然是使用线性搜索和对每个检查的键进行等价测试。我希望有可能做得比这更好。

我一直在考虑试图强加一个任意但一致的排序，并推导出一个有序的比较算法。第一原则涉及自动机表示的字符串集。评估每个自动机可能的第一个标记集，并根据这两个集合应用排序。如有必要，继续检查可能的第二个标记集、第三个标记集等。天真地这样做的明显问题是，在证明等价之前要检查无数个标记集。

我一直在考虑一些模糊的想法——首先最小化输入自动机并使用某种闭包算法，或者转换回常规语法，一些涉及生成树的想法。我得出的结论是我需要放弃标记集的词汇排序，但到目前为止我得出的最重要的结论是，这不是微不足道的，我可能最好继续阅读别人的解决方案。

我从 CiteSeerX 下载了一篇论文——子群和陪集的总排序——但我的抽象代数还不足以知道这是否相关。

我还想到可能有某种方法可以从自动机中导出散列，但我还没有考虑这么多。

谁能推荐一篇好论文来阅读？- 或者至少让我知道我下载的是否是红鲱鱼？

请向我推荐一些关于“形式语言和自动机理论”的好书。

谢谢！

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

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

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

我手头有一个问题，我不知道要使用哪种设计模式。问题是这样的：

我必须构建一个具有“N”个状态的系统，并且我的系统必须根据某些条件从任何状态转换到任何其他状态。例如：在条件 1 下，从状态 1 移动到 3，在条件 2 下从状态 1 移动到 4。

甚至从一种状态到另一种状态的转换也可以在 2 个或更多不同的条件下完成。

例如，从状态 1 到状态 3 的转换可以在以下情况下完成：
条件 1：“星期天”
条件 2：“下雨”
条件 3：“下雨和星期天”
在每个条件下，状态 3 的处理可以是不同的。

我希望我能够清楚地理解这个问题。请帮忙。

非常感谢

如果您已经拥有算法的伪代码，它们是否有助于描述图灵机的功能？

我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态、转换等）的图灵机，即使我知道如何用 C 甚至汇编之类的东西对其进行编码. 我想我只是没有对图灵机进行足够的练习（正在研究它），但我很感激任何建议。

编辑

我不想制作图灵机模拟器，我想在纸上描述图灵机（字母、状态、转换）以决定某种语言。

这是我的意思的一个简单示例，假设我需要编写一个图灵机，它会遍历一串 0 和 1，并将其中的所有 0 更改为 1。例如，如果您从磁带上的 11010（输入）开始，它会以磁带上的 11111（输出）停止。现在在高级语言中你知道它是这样的：

图灵机的描述非正式地类似于：

你有两个状态，q 和 halt。当你处于状态 q 并且你看到一个 1 时，向右走而不改变它。如果您看到 0，请将其更改为 1 并向右走。如果您看到空白符号（磁带结尾），则进入停止状态。

正式地，您将有类似 {q, halt} 的状态。{((q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (halt, 0, L) )} 用于转换。

现在这个问题是微不足道的，但还有其他更复杂的问题（添加一元数或识别具有相同数量的 a、b 和 c 的语言）。我可以轻松地为他们编写伪代码，但编写图灵机更具挑战性（花了我很长时间），我想知道是否有一些技巧、资源或指南可以帮助我更好地解决此类问题。

有些语言是图灵机可以处理而 LBA 不能处理的，但是否有任何 LBA 无法解决但 TM 可以解决的有用的实际问题？

LBA 只是一个带有有限磁带的图灵机，而实际的计算机具有有限的存储空间，所以在我看来，没有什么是 LBA 做不到的。 除了线性有界自动机不仅有一个有限的磁带，还有一个大小是输入大小的线性函数的磁带。有限性的线性是否以某种方式限制了 LBA？

是否存在 LBA 无法解决的问题，但指数有界自动机可以（如果存在此类问题）？

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

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

/foo/**/bar/*.baz

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

有任何想法吗？

谢谢，迈克

编辑：

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

请帮我找到语法或自动机来决定以下语言：

a ⁿ b ⁿ c ⁿ其中 n≥1

（有向）图表示有限自动机。到目前为止，我的测试程序一直在写出点文件进行测试。这对于回归测试（将经过验证的输出文件保存在 subversion 中，询问它是否有变化）和可视化都非常好。不过，也有一些问题...

基本上，我想要一些可从 C++ 调用的东西，它为我的状态和转换计划一个布局，但把绘图留给我——这将允许我随心所欲地绘制东西并在 GUI (wxWidgets) 窗口上绘制。

我还想要一个允许商业使用的许可证——我目前不需要，我很可能会作为开源发布，但我不想限制我的选项 ATM。

GraphViz 的问题是（1）关于在 Windows 上从源代码构建的警告，（2）所有不必要的渲染和解析依赖项，以及（3）（假定）缺乏专门用于布局的文档化 API。

基本上，我希望能够指定我的状态（带有边界矩形大小）和转换，并读出每个转换的状态和航点的位置，然后自己根据这些坐标进行绘制。我还没有真正弄清楚应该如何处理关于转换的注释，但是应该有一些规定可以为它们指定边界框大小，将它们与转换相关联，并读出位置。

有谁知道可以处理这些要求的库？

我不一定反对为自己实现某些东西，但在这种情况下，如果可能的话，我宁愿避免它。