F# 中的 DFA 最小化

Question

我完全不熟悉函数式编程，并且选择将 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 table 格式。它基本上是 States x States 的笛卡尔积（来自上述最小化算法的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"]]

我最初的策略是制作一个新列表，其中仅包含非最终对或都是最终对。（只有两个条件未满足 'Step 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”这两个状态在传递相同的字母字符时表现不同，所以它们是不同的。但是，正如我所说的，我完全不清楚如何进行这种比较。

如有任何帮助，我们将不胜感激。保重！

Answer 1

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

根据字母将它们分类到单独的状态对列表中
从每个这样的列表中创建一个随机访问数组（或关联映射）

由于您正在反转转换函数，因此每个映射的 index/key 将是目标状态，而 contents/value 将是字母映射到的零个或多个原始状态的列表它。

确保 "distinct" 列表中的所有元素的第一个元素都小于第二个元素（如有必要，交换两个元素），并确保列表本身已排序。然后，对于每个数组或映射：

将映射应用到您的 "distinct" 列表，如下所示：
- 查找每个"distinct"对两个个元素
- 对给定对
- 将所有笛卡尔积的结果对合并到一个列表中
对于这个新列表：
- 过滤掉任何具有相同元素的结果元组
- 交换第一个元素大于第二个元素的任何元组
- 对结果进行排序
- 消除相邻的重复项
与 "distinct" 列表进行合并：

F# 中的 DFA 最小化

DFA minimization in F#

f#

functional-programming

dfa

f#-4.0