C# 实现正则表达式转NFA：求解 Epsilon 闭包代码解析

C# 实现正则表达式转 NFA：求解 Epsilon 闭包代码解析

public List<int> closure(List<int> list)
{
    Queue<int> state_queue = new Queue<int>();
    List<int> closure_result_list = new List<int>();
    for (int i = 0; i < list.Count; i++)
    {
        state_queue.Enqueue(list[i]);
        closure_result_list.Add(list[i]);
    }
    while (state_queue.Count != 0)
    {
        int now_state = state_queue.Peek();
        state_queue.Dequeue();
        for (int i = 0; i < nfa.Count; i++)
        {
            if (nfa[i].start == now_state && nfa[i].to == '#' && find(closure_result_list, nfa[i].end) == -1)
            {
                state_queue.Enqueue(nfa[i].end);
                closure_result_list.Add(nfa[i].end);
            }
        }
    }
    closure_result_list.Sort();
    return closure_result_list;
}

代码解析：

上述代码实现了正则表达式转 NFA 的一个重要步骤——求解 Epsilon 闭包。Epsilon 闭包是指从一个状态出发，可以通过任意个空转换到达的状态集合。在 NFA 中，空转换用 '#' 表示。

求解 Epsilon 闭包的过程如下：

初始化队列和闭包结果列表： 使用 Queue<int> state_queue 存储当前状态能够到达的所有状态，使用 List<int> closure_result_list 存储已经加入到 Epsilon 闭包中的状态。
遍历初始状态： 遍历初始状态列表 list，将每个状态加入队列和闭包结果列表。
循环遍历队列： 当队列不为空时，循环进行以下步骤：
- 从队列中取出一个状态 now_state。
- 遍历 NFA 边 nfa，查找从 now_state 出发，通过空转换 '#' 能到达的未加入到闭包中的状态。
- 如果找到这样的状态，将该状态加入队列和闭包结果列表。
排序闭包结果： 循环结束后，对闭包结果列表 closure_result_list 进行排序，并返回结果。

原理：

Epsilon 闭包是正则表达式转 NFA 过程中一个重要的概念。它能够将 NFA 中所有能够通过空转换到达的状态集合求出来，为后续的状态转移和 DFA 构造打下了基础。

总结：

该代码通过队列和循环的方式，实现了从初始状态出发，不断扩展 Epsilon 闭包，最终得到所有能够通过空转换到达的状态集合。这是一个正则表达式转 NFA 过程中的重要步骤，为后续的 DFA 构造提供了基础。