正则表达式 – DFA最小化

我有一个关于DFA最小化的问题.所以我使用了众所周知的技术将正则表达式转换为NFA,然后使用goto / closure算法从中构造DFA.现在问题是如何最小化它？我在这里看过有关它的内容： http://www.youtube.com/watch?v=T9Z66NF5YRk,我仍然无法理解.什么是DFA最小化？这只是合并IDENTICAL状态(状态在相同的字符上进入相同的状态)还是不同的东西？

所以,我开始使用以下语法：

%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等等……)
>比较获得的哈希值,如果找到两个相同的哈希值,则合并它.在我的例子中,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
}]

}
>继续这个’直到我们没有变化,所以下一步(合并状态1和3)将DFA转换为以下形式：

{
0: [{
    from: 97,shift: 6
}],6: [{
    from: 97,shift: 6
},shift: 5
}]

}
>没有更多相同的州,这意味着我们已经完成了.

第二次更新：

好的,所以给出以下正则表达式：’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有什么问题？

{q0,q1,q2},{q3}

{q0},{q1,{q3}