NFA 转 DFA 算法实现 - C# 代码示例

private void button7_Click(object sender, EventArgs e) { // 从 listView1 中读取 NFA 数据 List<string[]> nfaData = new List<string[]>(); foreach (ListViewItem item in listView1.Items) { string[] row = new string[3]; row[0] = item.SubItems[0].Text; // 起始状态 row[1] = item.SubItems[1].Text; // 接受符号 row[2] = item.SubItems[2].Text; // 到达状态 nfaData.Add(row); }

// 将 NFA 转换为 DFA
List<string[]> dfaData = ConvertNFAToDFA(nfaData);

// 将 DFA 数据显示在 listView2 中
listView2.Items.Clear();
foreach (string[] row in dfaData)
{
    ListViewItem item = new ListViewItem(row);
    listView2.Items.Add(item);
}

}

// 将 NFA 数据转换为 DFA 数据 private List<string[]> ConvertNFAToDFA(List<string[]> nfaData) { List<string[]> dfaData = new List<string[]>();

// 获取所有状态和字母表
List<string> states = GetAllStates(nfaData);
List<string> alphabet = GetAlphabet(nfaData);

// 初始化 DFA 初始状态
string dfaStartState = GetEpsilonClosure(new List<string> { states[0] }, nfaData);
List<string> dfaStartStateList = new List<string> { dfaStartState };
dfaData.Add(new string[] { dfaStartState, "", dfaStartState });

// 初始化 DFA 状态集合
List<List<string>> dfaStates = new List<List<string>> { dfaStartStateList };

// 循环处理 DFA 状态集合
for (int i = 0; i < dfaStates.Count; i++)
{
    List<string> dfaState = dfaStates[i];

    // 遍历字母表
    foreach (string symbol in alphabet)
    {
        // 获取当前状态通过 symbol 可到达的所有状态
        List<string> nfaNextStates = GetNextStates(dfaState, symbol, nfaData);

        // 如果没有可到达的状态，则跳过
        if (nfaNextStates.Count == 0)
            continue;

        // 获取当前状态通过 epsilon 可到达的所有状态
        List<string> epsilonClosure = GetEpsilonClosure(nfaNextStates, nfaData);

        // 如果该状态已经存在于 DFA 状态集合中，则不需要添加
        int index = dfaStates.FindIndex(x => x.SequenceEqual(epsilonClosure));
        if (index == -1)
        {
            // 添加新状态到 DFA 状态集合中
            dfaStates.Add(epsilonClosure);

            // 记录新状态到 DFA 数据中
            string dfaStateName = string.Join(",", epsilonClosure);
            dfaData.Add(new string[] { dfaStateName, symbol, GetEpsilonClosure(epsilonClosure, nfaData) });
        }
        else
        {
            // 记录已存在的状态到 DFA 数据中
            string dfaStateName = string.Join(",", dfaStates[index]);
            dfaData.Add(new string[] { dfaStateName, symbol, GetEpsilonClosure(dfaStates[index], nfaData) });
        }
    }
}

return dfaData;

}

// 获取所有状态（包括起始状态和到达状态） private List GetAllStates(List<string[]> nfaData) { List states = new List(); foreach (string[] row in nfaData) { if (!states.Contains(row[0])) states.Add(row[0]); if (!states.Contains(row[2])) states.Add(row[2]); } return states; }

// 获取字母表 private List GetAlphabet(List<string[]> nfaData) { List alphabet = new List(); foreach (string[] row in nfaData) { if (!alphabet.Contains(row[1]) && row[1] != "") alphabet.Add(row[1]); } return alphabet; }

// 获取某个状态通过某个符号能到达的所有状态 private List GetNextStates(List states, string symbol, List<string[]> nfaData) { List nextStates = new List(); foreach (string state in states) { foreach (string[] row in nfaData) { if (row[0] == state && row[1] == symbol) { if (!nextStates.Contains(row[2])) nextStates.Add(row[2]); } } } return nextStates; }

// 获取某个状态通过 epsilon 能到达的所有状态 private List GetEpsilonClosure(List states, List<string[]> nfaData) { List closure = new List(states); bool changed = true; while (changed) { changed = false; foreach (string state in closure) { foreach (string[] row in nfaData) { if (row[0] == state && row[1] == "") { if (!closure.Contains(row[2])) { closure.Add(row[2]); changed = true; } } } } } closure.Sort(); return closure;