我对函数式编程完全陌生,因此选择将F#用于需要解析和最小化DFA的项目。
目前,我的解析器已经完成,并且能够以我想要的任何方式格式化DFA元组的每个元素(状态,字母,转换函数,开始状态,最终状态),并且已经达到了实现该功能的地步最小化算法。使用的算法是:
For some DFA (Q, Σ, δ, S, F) where
Q: The set of states
Σ: The alphabet
δ: The transition function
S: The start state
F: The set of final states
Step 1. For each pair of states
(p, q) ∈ Q x Q
If p ∈ F and q ∉ F (or vice versa), then set distinct(p, q) = 1.
Step 2. Loop until there is no change in the table contents:
For each pair of states (p, q) ∈ Q x Q:
For each alphabet symbol a ∈ alphabet:
If distinct(p, q) = 0 and distinct(δ(p, a), δ(q, a)) = 1, then set
distinct(p, q) = 1.
我将DFA元组元素的格式设置如下:
状态:
["0";"1";"2";"3"]
字母:
["a";"b"]
转换函数(即:[“ 0”;“ a”;“ 1”]读为“ a上的0变为1”]
[["0";"a";"1"];["1";"a";"1"];["1";"b";"2"];["2";"a";"0"];...;["5";"a";"4"]
起始状态:
["0"]
最终状态:
["1";"5"]
我也有distinct
格式化的表格。它基本上是状态x状态的笛卡尔积(QxQ
来自上面的最小化算法),其中任何重复的乘积和重复的元素都被忽略:
[["0";"1"];["0";"2"];["0";"3"];["0";"4"];["0";"5"];["1";"2"];
["1";"3"];["1";"4"];["1";"5"];["2";"3"];["2";"4"];["2";"5"];
["3";"4"];["3";"5"];["4";"5"]]
我最初的策略是制作一个仅包含成对或成对的新列表。(仅有两个条件不符合“步骤1”条件)。
我的问题是:我很难想出一种方法来将结果列表与每对状态的转换函数进行比较。例如,采用一对状态["1";"5"]
。正如算法所指出的,我们必须将每个字母字符与“ 1”发生的事情与每个字母字符与“ 5”发生的事情进行比较。在这种情况下,转换函数说明:
对于1:
["1";"a";"1"];["1";"b";"2"]
-'a'上的'1'变为'1'
-'b'上的'1'转到'2'
对于5:
["5";"a";"4"]
-'a'上的'5'变为'4'
因为当传递相同的字母字符时,“ 5”和“ 1”这两种状态的行为都不同,所以它们是不同的。但是,正如我已经说过的那样,我对如何实现这种比较一无所知。
任何帮助将不胜感激。小心!
如上所示,如果您的转换函数存储为三元组,则:
由于您要反转转换函数,因此每个映射的索引/关键字将是目标状态,而内容/值将是字母映射到其的零个或多个原始状态的列表。
确保“与众不同”列表中的所有元素的第一个元素都小于第二个元素(如有必要,通过交换两个元素),并确保列表本身已排序。然后,对于每个数组或映射:
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句