NFA 转 DFA 实现：单函数方法

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); }

// 转换为 DFA 数据
List<string[]> dfaData = new List<string[]>();

// 初始化 DFA 的起始状态集合为 NFA 的起始状态集合的 ε-闭包
List<string> dfaStartState = EpsilonClosure(new List<string>() { nfaData[0][0] }, nfaData);
dfaData.Add(new string[] { string.Join(',', dfaStartState), '', '' });

// 依次处理每个 DFA 状态集合
for (int i = 0; i < dfaData.Count; i++)
{
    string[] dfaRow = dfaData[i];
    string dfaState = dfaRow[0];
    // 对于每个接受符号，计算新的 DFA 状态集合
    foreach (char symbol in GetAcceptSymbols(nfaData))
    {
        List<string> nfaStateSet = new List<string>();
        // 对于当前 DFA 状态集合中的每个 NFA 状态，计算接受该符号转移的 NFA 状态集合
        foreach (string nfaState in dfaState.Split(','))
        {
            List<string> transitionStates = GetTransitionStates(nfaData, nfaState, symbol);
            // 将转移状态加入集合
            nfaStateSet.AddRange(transitionStates);
        }
        // 计算新的 DFA 状态集合
        List<string> dfaNewState = EpsilonClosure(nfaStateSet, nfaData);
        // 如果该状态集合还未被加入 DFA 数据中，将其加入
        string newStateStr = string.Join(',', dfaNewState);
        if (!dfaData.Any(row => row[0] == newStateStr))
        {
            dfaData.Add(new string[] { newStateStr, '', '' });
        }
        // 添加转移边
        dfaRow[1] += symbol;
        dfaRow[2] += newStateStr;
    }
}

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

}

// 获取所有接受符号 private List GetAcceptSymbols(List<string[]> nfaData) { List symbols = new List(); foreach (string[] row in nfaData) { if (row[1] != '' && !symbols.Contains(row[1][0])) { symbols.Add(row[1][0]); } } return symbols; }

// 获取从某个状态经过某个符号可以到达的状态集合 private List GetTransitionStates(List<string[]> nfaData, string state, char symbol) { List states = new List(); foreach (string[] row in nfaData) { if (row[0] == state && row[1] == symbol.ToString()) { states.Add(row[2]); } } return states; }

// 获取某个状态的 ε-闭包 private List EpsilonClosure(List states, List<string[]> nfaData) { List closure = new List(states); Queue queue = new Queue(states); while (queue.Count > 0) { string state = queue.Dequeue(); foreach (string[] row in nfaData) { if (row[0] == state && row[1] == '' && !closure.Contains(row[2])) { closure.Add(row[2]); queue.Enqueue(row[2]); } } } return closure;