正规式转NFA代码详解：子集构造与等价类划分

这段代码实现了将正规式转换为NFA的过程，利用了Thompson算法、子集构造和等价类划分等技术，最终得到一个等价的NFA图。

public void Sameless()
{
    List<List<int>> result = new List<List<int>>();
    List<int> e = new List<int>();
    for (int i = 0; i < dfa_list.Count; i++)
    {
        if (!end_list.Contains(dfa_list[i].start) && !e.Contains(dfa_list[i].start))
        {
            e.Add(dfa_list[i].start);
        }
    }
    e.Sort();
    if (e.Count != 0)
        result.Add(e);
    result.Add(end_list);
    int count = 0;
    while (count < result.Count)
    {
        List<int> E = new List<int>();
        E = result[count];
        if (count == result.Count - 1) // 终结状态
        {
            num_end = findtype(result, E[0]);
        }
        List<int> L = new List<int>();
        for (int i = 0; i < sign_list.Count; i++)
        {
            int x = findtype(result, findlast(E[0], sign_list[i]));
            for (int j = 0; j < E.Count; j++)
            {
                if (findlast(E[j], sign_list[i]) != -1 && findtype(result, findlast(E[j], sign_list[i])) != x && !L.Contains(E[j]))
                {
                    L.Add(E[j]);
                }
            }
        }
        if (L.Count == 0)
        {
            count++;
        }
        else
        {
            List<int> J = new List<int>();
            for (int x = 0; x < E.Count; x++)
            {
                if (!L.Contains(E[x]))
                {
                    J.Add(E[x]);
                }
            }
            result.RemoveAt(count);
            result.Insert(count, J);
            result.Insert(count + 1, L);
        }
    }

    for (int i = 0; i < result.Count; i++)
    {
        for (int j = 0; j < dfa_list.Count; j++)
        {
            if (dfa_list[j].start == result[i][0])
            {
                FA fa = new FA();
                fa.start = findtype(result, dfa_list[j].start);
                fa.to = dfa_list[j].to;
                fa.end = findtype(result, dfa_list[j].end);
                if (!mfa_list.Contains(fa))
                    mfa_list.Add(fa);
            }
        }
    }
}

代码原理

Thompson算法： 代码首先利用Thompson算法将正规式转换为NFA，得到包含起始状态、终止状态和转移条件的NFA图。
子集构造： 然后，对NFA图进行子集构造，得到一个包含起始状态、终止状态和转移条件的DFA图。
等价类划分： 最后，对DFA图进行等价类划分，得到一个最小化的DFA图。

代码解析

Sameless() 函数： 该函数实现了整个正规式转NFA的过程。
e 列表： 存放所有非终止状态的集合。
result 列表： 用于存储等价类划分的结果。
count 变量： 控制遍历result列表的指针。
E 列表： 当前遍历的等价类。
L 列表： 存放与E中有相同转移条件的状态集合。
J 列表： 存放E中与L不相交的状态集合。

总结

这段代码通过Thompson算法、子集构造和等价类划分等步骤，实现了将正规式转换为NFA的过程。代码中使用了列表、哈希表等数据结构，以及循环和条件判断等控制结构。

补充说明

代码中的 dfa_list、end_list、sign_list、mfa_list 以及 findtype、findlast 等函数需要根据实际情况进行定义。
代码中使用了 FA 类来表示NFA中的状态，其包含 start、to、end 等属性。
该代码仅为示例代码，实际应用中可能需要根据具体需求进行调整。