F#中的DFA最小化

等于0

我对函数式编程完全陌生,因此选择将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”这两种状态的行为都不同,所以它们是不同的。但是,正如我已经说过的那样,我对如何实现这种比较一无所知。

任何帮助将不胜感激。小心!

即将来临的暴风雨

如上所示,如果您的转换函数存储为三元组,则:

  • 根据字母将它们分为不同的状态对列表
  • 从每个这样的列表中制作一个随机访问数组(或关联映射)

由于您要反转转换函数,因此每个映射的索引/关键字将是目标状态,而内容/值将是字母映射到其的零个或多个原始状态的列表。

确保“与众不同”列表中的所有元素的第一个元素都小于第二个元素(如有必要,通过交换两个元素),并确保列表本身已排序。然后,对于每个数组或映射:

  • 将映射应用于您的“不同”列表,如下所示:
    • 查找每个“不同”对的两个元素
    • 执行给定对中两个“原始状态”列表的笛卡尔积
    • 将所有笛卡尔积的结果对合并到一个列表中
  • 对于此新列表:
    • 过滤出所有具有相同元素的元组
    • 交换第一个元素大于第二个元素的任何元组
    • 排序结果
    • 消除相邻的重复项
  • 用“ distinct”列表进行合并:

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章