automata

4热度

2回答

我希望能够通过给定的java.util.regex.Pattern实例来计算可能匹配的所有字符的集合，作为第一个字符。更正式地说，如果DFA等同于某个正则表达式，我想要从开始状态开始的所有传出转换的集合。一个例子： Pattern p = Pattern.compile("[abc]def|daniel|chris|\\s+"); Set<Character> first = getFirst

3热度

2回答

设计一个图灵机的状态表

如果你已经有了算法的伪代码，它们是否有用来描述图灵机做什么的有用指导？我正在学习复杂性理论课程，它花了我一段时间来描述决定或接受某种语言（状态，转换等）的图灵机，即使我知道如何在类似的东西C甚至组装。我想我只是没有足够的练习图灵机（工作），但我很欣赏任何建议。编辑我不想做一个图灵机模拟器，我想描述在纸上（字母，状态，转换）图灵机来决定一些语言。下面是我的意思的一个简单例子，比如说我需要编写

3热度

2回答

如果语言（L）被n状态NFA识别，它是否也可以被不超过2^n个状态的DFA识别？

我在这么想，因为上限是2^n，并且考虑到这些都是有限机器，n状态NFA和2^n或更少状态的DFA的交集将是有效的。我错了吗？

4热度

1回答

用于描述DFA或NFA的语法

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

6热度

6回答

莱文斯坦DFA在.NET

下午好，有谁知道在.NET中的“乱用”的实施莱文斯坦的DFA（确定性有限自动机）的（或容易翻译吧）？我有一本超过160000个不同单词的非常大的字典，我想要给出一个原始单词w，以有效的方式找到所有已知单词在Levenshtein距离最多为2的w。当然，通过编辑距离计算给定单词的所有可能编辑并将其应用于每个编辑的功能可以解决问题（并且以非常简单的方式）。问题是效率 - 给定一个7个字母的单词，

0热度

1回答

BNF语法衍生

我想应用BNF语法的规则来产生以下衍生：a_Num

4热度

4回答

自动机理论书籍

请给我一些关于“形式语言和自动机理论”的好书。谢谢！

7热度

3回答

将正则表达式转换为CFG

如何将某些常规语言转换为其等效的上下文无关语法？是否有必要构造与该正则表达式对应的DFA，或者是否存在用于这种转换的一些规则？例如，考虑以下正则表达式 01 + 10（11）* 如何可以描述对应于上述RE语法？

0热度

2回答

在一组输出上的两个不同语法

你能给我2个不同的语法输出相同的一组字吗？插图：鉴于在字母表{0,1}语法A和B，如果语法A可以产生字0101001，语法B可以为好。如果语法B可以产生0101111，那么语法A也可以。如果语法A不能产生01001，那么B既不能。但是这里的事情是语法A和B彼此不同，即它们使用完全不同的算法。那么他们产生的这组输出不仅仅是另一个的一个合适的子集。说他们相应的一组输出的含义必须具有相同的基数。可

0热度

2回答

我在哪里可以找到样本自动机和图灵机？

我正在学习一个基于jflap的课程的自动机测试。麻烦的是，我们没有太多文档，我在jlap上找到的样本自动机（如this和this）不足以为即将到来的测试做准备。我在哪里可以找到更多？带有转换图的任何其他带有示例图灵机的资源也会有所帮助。