所以,我开始使用以下语法：
%digit = '0'..'9'
%letter = 'a'..'z' | 'A'..'Z'
%exponent = ("e" | "E") ("+" | "-")? digit+
T_INT = digit+
T_FLOAT = T_INT exponent
T_IDENTIFIER = (letter | "$" | "_") (letter | "$" | "_" | digit)*
最终得到以下DFA(表示为JSON)：
{
"START": [{
"type": "range","from": 36,"to": 36,"shift": "1"
},{
"type": "range","from": 48,"to": 57,"shift": "2"
},"from": 65,"to": 90,"from": 95,"to": 95,"from": 97,"to": 122,"shift": "1"
}],"1": [{
"type": "range",{
"shift": ["t_identifier"]
}],"2": [{
"type": "range","from": 69,"to": 69,"shift": "3"
},"from": 101,"to": 101,{
"shift": ["t_int"]
}],"3": [{
"type": "range","from": 43,"to": 43,"shift": "5"
},"from": 45,"to": 45,"shift": "4"
}],"4": [{
"type": "range","shift": "4"
},{
"shift": ["t_float"]
}],"5": [{
"type": "range","shift": "4"
}]
}
那么我该如何最小化呢？
更新：
好的,这是我的算法.鉴于以下DFA：
{
0: [{
from: 97,to: 97,shift: 1
}],1: [{
from: 97,shift: 3
},{
from: 98,to: 98,shift: 2
}],2: [{
from: 98,shift: 4
}],3: [{
from: 97,4: [{
from: 98,shift: 4
}]
}
这是我做的最小化它：
>对于每个状态(在我的示例中编号为0,1,2,3,4)获取标识此类状态的唯一哈希(例如,对于state0,这将是：from = 97,to = 97,shift = 1,for state1这将是：from = 97,shift = 3& from = 98,to = 98,shift = 2等等……)@H_502_34@>比较获得的哈希值,如果找到两个相同的哈希值,则合并它.在我的例子中,state2 hash将是：from = 98& shift = 4& to = 98,state4 hash将是：from = 98& shift = 4& to = 98,它们是相同的,所以我们可以将它们合并到新的state5,之后DFA将如下所示：
{
0: [{
from: 97,shift: 1
}],1: [{
from: 97,shift: 3
},{
from: 98,shift: 5
}],3: [{
from: 97,5: [{
from: 98,shift: 5
}]
}@H_502_34@>继续这个’直到我们没有变化,所以下一步(合并状态1和3)将DFA转换为以下形式：
{
0: [{
from: 97,shift: 6
}],6: [{
from: 97,shift: 6
},shift: 5
}]
}@H_502_34@>没有更多相同的州,这意味着我们已经完成了.
第二次更新：
好的,所以给出以下正则表达式：’a'(‘ce’)*(‘d’|’xa’|”AFe’)| ‘b'(‘ce’)*(‘d’|’xa’|”AFe’)’ce’我有以下DFA(START – >开始状态,[“接受”] – >所以到说过渡到接受状态)：
{
"START": [{
"type": "range","from": 98,"to": 98,"shift": "1.2"
},"to": 97,"shift": "17.18"
}],"1.2": [{
"type": "range","from": 120,"to": 120,"shift": "10"
},"from": 100,"to": 100,"shift": "6.7"
},"to": 65,"shift": "8"
},"from": 99,"to": 99,"10": [{
"type": "range","shift": "6.7"
}],"6.7": [{
"type": "range","shift": "15"
},"shift": "13"
},"shift": "11"
}],"15": [{
"type": "range","shift": "14.accept"
}],"14.accept": [{
"type": "range","shift": "16"
},{
"shift": ["accept"]
}],"16": [{
"type": "range","13": [{
"type": "range","11": [{
"type": "range","from": 70,"to": 70,"shift": "12"
}],"12": [{
"type": "range","8": [{
"type": "range","shift": "9"
}],"9": [{
"type": "range","shift": "2.3"
}],"2.3": [{
"type": "range","shift": "5"
}],"17.18": [{
"type": "range","shift": "25"
},"shift": "22.accept"
},"shift": "23"
},"shift": "20"
}],"25": [{
"type": "range","shift": "22.accept"
}],"22.accept": [{
"type": "range","shift": "28"
},"shift": "26"
},"28": [{
"type": "range","26": [{
"type": "range","shift": "27"
}],"27": [{
"type": "range","23": [{
"type": "range","shift": "24"
}],"24": [{
"type": "range","20": [{
"type": "range","shift": "18.19"
}],"18.19": [{
"type": "range","shift": "21"
}],"21": [{
"type": "range","shift": "18.19"
}]
}
故事是一样的,我该如何最小化它？如果我遵循经典的Hopcroft算法与所有这些表构造,确定不可区分的状态,将它们合并在一起等等,那么我将得到包含15个状态的DFA(使用此工具：http://regexvisualizer.apphb.com/与此正则表达式a(ce)( d | xa | AFe)| b(ce)(d | xa | AFe)ce检查).以下是使用Hopcroft算法进行缩小后DFA的样子：
在我重新思考Hopcroft的算法之后,我提出的算法构建的DFA小于您上面看到的DFA(对于图像质量而言,我不得不一步一步地重新绘制它以了解为什么它更小)：
以下是它的工作原理,关于“状态等价”的决定是基于给定状态的哈希函数的结果(例如“START”)构建短字符串,如果我们从该状态开始,可以从DFA构造.给定上面的DFA和START状态,我们可以构造以下字符串：98-> 120,98-> 100,98-> 65,98-> 99,97-> 120,97-> 100,97-> 65,97-> 99因此,它是START状态的散列函数的结果.如果我们为DFA中的每个状态运行此函数,我们将看到对于某些状态,此函数给出了相同的结果(“1.2”,“6.7”,“2.3”和“10”,“13”和“15”,“16”和“11”,“8”,“26”,“23”和“12”,“9”,“4”,“5”,“20”,“21”和“17.18”,“ 18.19“AND”25“,”28“和”27“,”24“)所以我们需要做的就是将这些状态合并在一起.
我发现我在某处错了,但不明白我的算法产生的最小化DFA有什么问题？
解决方法
最小化将结合q1和q2,但概述的算法无法管理.
与此相反,Hopcroft的算法最初会像这样分区：
{q0,q1,q2},{q3}
然后拆分第一组,因为q0没有转换到q3：
{q0},{q1,{q3}
而不是进一步分裂,因为q1和q2表现相同.
