问题标签 [automata]

我知道这与编程没有直接关系，但我想知道是否有人知道如何将泵引理应用于以下证明：

证明L={(a^n)(b^n)(c^m) : n!=m}不是上下文无关语言

我对应用抽水引理非常有信心，但这真的让我很恼火。你怎么看？

如何将一些常规语言转换为其等效的上下文无关语法？是否有必要构造对应于该正则表达式的 DFA 或者是否有一些规则可以进行这种转换？

例如，考虑以下正则表达式

01+10(11) ^*

如何描述上述RE对应的语法？

我正在研究一个问题（来自Hopcroft、Motwani 和 Ullman的自动机理论、语言和计算机简介0）来编写一个正则表达式，该表达式定义一种由s 和s的所有字符串组成的语言，1不包含 substring 011。

答案(0+1)* - 011正确吗？如果不是，那么正确的答案应该是什么？

我正在开发一个 javascript 游戏，我有一个自动机系统来控制游戏时间和精灵动画，以及帮助路径查找系统进行计时等。我的问题是在慢速浏览器上，我用来计算时间的 javascript 循环不是很准确。它往往会跳来跳去。我有办法强制循环以 30 fps 持续运行吗？

基本上我需要一种方法让我的自动机循环以 1/30 秒的速度运行。

我喜欢我学习的自动机理论和形式语言课程，所以我很自然地开始浏览互联网，了解自从编写该课程所依据的书籍以来发生的事情。

我发现我不熟悉的东西清单似乎很短。例如，从该主题的 Wikipedia 条目中的自动机列表中，课程涵盖了一半，而另一半则主要与课程未涵盖的一种语言有关。

此外，在研究该理论的应用时，我得到了几乎相同的结果：编程语言语法、编译器、文本搜索等等。

那么它真的死了吗？还是会继续发展？该理论有新的应用吗？

你能给我两种不同的语法来输出相同的单词集吗？

插图：

给定字母表 {0,1} 上的语法 A 和 B，如果语法 A 可以产生单词 0101001，那么语法 B 也可以。如果语法 B 可以产生 0101111，那么语法 A 也可以。如果语法 A 不能产生 01001 那么 B 也不能。

但这里的问题是语法 A 和 B 彼此不同，即它们使用完全不同的算法。那么他们产生的输出集合不仅仅是另一个输出的适当子集。意思是说它们对应的一组输出必须具有相同的基数。可能它们具有不同的复杂性等级，但这没关系。如果可以的话，如果您能给我提供字母 {0,1} 上的语法，就像经典的图灵机一样，我将不胜感激。

我有这种语言：

{a ⁿ b ^m | m+n 是偶数}

什么是正确的语法？

我是这么想的，因为上限是 2^n，并且鉴于它们都是有限机器，n 状态 NFA 和具有 2^n 或更少状态的 DFA 的交集将是有效的。

我在这里错了吗？

是否存在用于描述 NFA 或 DFA 的转换表的标准语法？

下午好，

有谁知道 .NET 中的 Levenshtein DFA（确定性有限自动机）的“开箱即用”实现（或易于翻译）？我有一个非常大的字典，其中包含超过 160000 个不同的单词，并且我想给定一个初始单词w ，以有效的方式在 Levenshtein 距离最多 2 个w找到所有已知单词。

当然，有一个函数可以计算给定单词的一个编辑距离处的所有可能的编辑，并将其再次应用于这些编辑中的每一个，可以解决问题（并且以一种非常简单的方式）。问题是效率 --- 给定一个 7 个字母的单词，这已经需要 1 秒多的时间才能完成，我需要更高效的东西---如果可能的话，就像 Levenshtein DFA 一样，一个需要 O( | w| ) 步骤。

编辑：我知道我可以通过一点学习来构建自己的解决方法，但目前我无法阅读 Schulz 和 Mihov 的 60 页长的文章。

非常感谢你。