我正在寻找基于其功能和限制的DFA与NFA引擎之间差异的非技术性解释.
我需要一个库,它将接受两个正则表达式并确定它们是否是同构的(即匹配完全相同的字符串集合)例如a | b与[ab]同构
据我所知,一个正则表达式可被转换为NFA在某些情况下可以有效地转换为DFA.然后可以将DFA转换为最小DFA,如果我理解正确的话,它是唯一的,因此可以比较这些最小DFA的相等性.我意识到并非所有正则表达式NFA都可以有效地转换为DFA(特别是当它们是从Perl Regexps生成而不是真正的"常规"时),在这种情况下理想情况下,库只会返回错误或其他指示转换是不可能.
我在网上看到大量关于这样做的文章和学术论文(甚至是一些课程要求学生这样做的编程任务),但我似乎无法找到实现这一功能的库.我更喜欢Python和/或C/C++库,但是任何语言的库都可以.有谁知道这样的图书馆？如果没有,有人知道我可以用作起点的图书馆吗？
从正则表达式创建NFA时,我遇到了"描述每个步骤"的问题.问题如下:
将以下正则表达式转换为非确定性有限状态自动机(NFA),清楚地描述您使用的算法的步骤:(b | a)*b(a | b)
我已经制作了一个简单的三态机器,但它非常直观.这是我的讲师在过去的考试中提出的一个问题,他也写了Thompson算法的以下解释:http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html
任何人都可以清楚如何"清楚地描述每一步"吗？它看起来像是一组基本规则,而不是一个遵循步骤的算法.
也许我已经在某个地方掩饰了一个算法,但到目前为止,我只是用一个有根据的猜测创建了它们.
我被要求显示DFA图和RegEx作为RegEx的补充(00 + 1)*.在之前的问题中,我必须证明DFA的补充是封闭的并且也是正则表达式,所以我知道要将DFA,M转换为补码,M`,我只需要交换初始接受状态和最终接受国家.
但是,似乎RegEx的初始接受状态是{00, 1, ^},最终接受状态也是{00, 1, ^}如此.因此,交换它们只会产生完全相同的RegEx和DFA,这似乎是相互矛盾的.
我做错了什么,或者这个RegEx应该没有真正的补充？
谢谢
如何在Python代码中实现dfa或nfa解决这个问题？
有什么好方法在python中做到这一点？他们曾经在现实世界的项目中使用过吗？
我知道将正则表达式转换为NFA,有一种算法.
但我想知道是否有算法将NFA转换为正则表达式.如果有,那是什么？
如果没有,我也想知道是否所有NFA都可以转换为正则表达式.是否存在一个无法表示的正则表达式的NFA？
谢谢!:d
有人可以比我更简洁地向SO社区描述NFA到DFA的转换算法吗？(最好是500字以内.)我见过的图表和讲座只会让我以为我曾经认识的东西感到困惑.我最有信心从状态图生成初始NFA转换表,但之后,我丢失了epsilons和子集中的DFA.
1)在转换(delta)表中,哪一列代表新的DFA状态？它是生成状态的第一列吗？
2)在下面我的例子的第{2,3}行中,{2,3}在状态图方面对NFA的意义是什么？(对不起,我必须在图片中思考.)我认为这将是DFA中的"输入0回环"？
3)从表格到DFA或识别所得到的DFA的接受状态的任何简单的"经验法则"？
有限自治
delta | 0 | 1 |
=======+=======+========+
{1} |{1} |{2} |
{2} |{3} |{2,3} |
{3} |{2} |{2,4} |
{2,3} |{2,3} |{2,3,4} |
{2,4} |{3,4} |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4} |{2,4} |{2,4} |
编辑:这是上面的点格式表,欢呼Regexident.
digraph dfa {
rankdir = LR;
size = "8,5"
/* node [shape = doublecircle]; "1";*/
node [shape = circle];
"1" -> "1" [ label = "0" ];
"1" -> "2" [ label = "1" ];
"2" -> "3" [ …我目前正在研发扫描仪发生器.发电机已经正常工作.但是当使用字符类时,算法变得非常慢.
扫描仪生成器为UTF8编码文件生成扫描仪.应支持全范围的字符(0x000000到0x10ffff).
如果我使用大字符集,就像任何运算符'.' 或者unicode属性{L},nfa(以及dfa)包含很多状态(> 10000).因此,将nfa转换为dfa并创建最小dfa需要很长时间(即使输出最小dfa只包含几个状态).
这是我当前创建nfa的字符集部分的实现.
void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
// get the utf8 encoded bytes for the character
byte[] encoded = EncodingHelper.EncodeCharacter(character);
int tStartStateIndex = startStateIndex;
for (int i = 0; i < encoded.Length - 1; i++) {
int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
if (tEndStateIndex == -1) {
tEndStateIndex = CreateState();
transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
}
transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
tStartStateIndex = tEndStateIndex;
}
transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex; …有谁知道在C#中有任何好的NFA和DFA实现,可能实现两者之间的转换？我希望能够构建一个NFA,然后将其自动转换为DFA,但无需编写我自己的代码,这将花费很长时间.有这个 Python代码,也许我可以使用并使用IronPython与C#集成,但Python很慢.
我想在我的词法分析器中实现DFA最小化器,但我似乎无法生成看起来不像它已经是表达式的最小DFA的DFA.
我正在使用来自后缀正则表达式的thomson构造构建的NFA构建DFA.这几乎就是龙书中描述的内容.为了使词法分析器使用来自开始状态的epsilon转换来组合几个NFA.正是在这个组合的NFA上应用了DFA算法.
那么,是否有任何"已知"正则表达式将生成一个DFA,它将为死态消除和状态最小化提供一个很好的测试平台？
我当然可以破解一个奇怪的DFA并在其上应用算法,但它不是一个真正的测试用例吗？如果我正在构建DFA的方法不容易出现死状态,那么这些信息就是有价值的,因为那时我可以完全跳过实现状态消除功能.
编辑:如果您需要实现细节以便准确回答,代码可以在github上获得,特别是NFA.cs和DFA.cs类.另外,我写了一篇关于我正在使用的构造算法的博客文章系列,如果有帮助的话.