我需要学习如何设计DFA,以便给定任何数字'n',它接受二进制字符串{0,1},其十进制等效数可以被'n'整除.
不同的'n'会有不同的DFA,但有人可以给出一个基本的方法,我应该遵循任何数字0 <n <10.
我正在寻找基于其功能和限制的DFA与NFA引擎之间差异的非技术性解释.
我正在分析一个大型公共数据集,其中包含大量冗长的人类可读字符串,这些字符串是由一些常规(在形式语言理论意义上)语法明确生成的.
一个接一个地查看这些字符串集来查看模式并不太难; 不幸的是,大约有24,000个这些独特的字符串分为33个类别和1714个子类别,因此手动执行此操作有点痛苦.
基本上,我正在寻找一个现有的算法(最好使用现有的参考实现)来获取任意的字符串列表,并尝试推断一些可用于生成的正则表达式的最小化(对于一些合理的最小化定义)它们(即从该语法生成的语言中推导出一组有限字符串中的常规语法).
我已经考虑过重复贪婪最长的常见子串消除,但这只是到目前为止,因为除了完全匹配之外它不会崩溃,所以不会检测到,例如,在特定位置的变化数字串的常见模式语法.
暴力强迫任何不会脱离常见子串消除的东西是可能的,但可能在计算上不可行.(另外,我想过这个问题,有可能是一个"阶段排序"和/或子淘汰"当地最低"的问题,因为你可能会做出最终迫使最终语法贪婪的字符串匹配要少压缩/即使它看起来是最好的减少最小).
我无法理解如何计算LR(1)-items的前瞻.
让我们说我有这个语法:
S -> AB
A -> aAb | a
B -> d
LR(1)-item是具有前瞻的LR(0)项.所以我们将为状态0得到以下LR(0)-item:
S -> .AB , {lookahead}
A -> .aAb, {lookahead}
A -> .a, {lookahead}
州:1
A -> a.Ab, {lookahead}
A -> a. ,{lookahead}
A -> .aAb ,{lookahead}
A ->.a ,{lookahead}
有人可以解释如何计算前瞻吗？一般方法是什么？
先感谢您
我被要求显示DFA图和RegEx作为RegEx的补充(00 + 1)*.在之前的问题中,我必须证明DFA的补充是封闭的并且也是正则表达式,所以我知道要将DFA,M转换为补码,M`,我只需要交换初始接受状态和最终接受国家.
但是,似乎RegEx的初始接受状态是{00, 1, ^},最终接受状态也是{00, 1, ^}如此.因此,交换它们只会产生完全相同的RegEx和DFA,这似乎是相互矛盾的.
我做错了什么,或者这个RegEx应该没有真正的补充？
谢谢
如何在Python代码中实现dfa或nfa解决这个问题？
有什么好方法在python中做到这一点？他们曾经在现实世界的项目中使用过吗？
我想知道如何找到一组具有有限数量匹配的给定正则表达式的所有匹配.
例如:
所有这些例子都可以假设他们从一开始就^结束$
`hello?` -> (hell, hello)
`[1-9][0-9]{0,3}` -> (1,2,3 ..., 9998, 9999)
`My (cat|dog) is awesome!` -> (My cat is awesome!, My dog is awesome!)
`1{1,10}` -> (1,11, ..., 111111111, 1111111111)
`1*` -> //error
`1+` -> //error
`(1|11){2}` -> (1,11,111,1111) //notice how it doesn't repeat any of the possibilities
如果有一种方法可以检索计算正则表达式的唯一解,或者是否有办法确定正则表达式是否具有有限解,那么我也会感兴趣.
如果算法可以解析任何正则表达式会很好,但正则表达式的强大的子集将是好的.
我对这个问题的PHP解决方案感兴趣,但其他语言也没问题.
编辑:
我在我的Formal Theory课程中学到了可以用来实现正则表达式(以及其他常规语言)的DFA.如果我可以将正则表达式转换为DFA,那么解决方案对我来说似乎相当直接,但这种转变对我来说似乎相当棘手.
编辑2:
感谢所有建议,请参阅我关于公共github项目的帖子,我正在努力"回答"这个问题.
我指的是Sedgewick的书"Algorithms"(第4版)中用于子串搜索的Knuth-Morris-Pratt(KMP)算法的概述.
KMP算法在子串搜索中使用基于确定性有限自动机(DFA)的备份.我了解DFA如何输入算法,但我不明白如何构建 DFA,这由以下代码片段完成:
dfa[pat.charAt(0)][0] = 1;
for (int X = 0; j = 1; j< M; j++) {
for (int c = 0; c < R; c++) {
dfa[c][j] = dfa[c][X];
}
dfa[pat.charAt(j)][j] = j+1;
X = dfa[pat.charAt(j)][X];
}
M模式的长度pat和R字母的大小在哪里.该charAt()函数返回相应位置的字符的整数值.
有人能解释这段代码构造dfa的方式吗？我迷失在内部for循环的实际直觉意义上.
有人可以比我更简洁地向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" [ …