C# 实现 NFA 转 DFA 功能：将 NFA 文件转换为 DFA 并显示结果

private void button7_Click(object sender, EventArgs e) { // 读取NFA文件 string[] lines = File.ReadAllLines('NFA.txt'); int startState = int.Parse(lines[0].Split(':')[1]); string[] endStates = lines[1].Split(':')[1].Split(';'); string[] symbols = lines[2].Split(':')[1].Split(';'); Dictionary<int, Dictionary<string, List>> nfa = new Dictionary<int, Dictionary<string, List>>(); for (int i = 3; i < lines.Length; i++) { string[] parts = lines[i].Split(' '); int fromState = int.Parse(parts[0]); string symbol = parts[1]; int toState = int.Parse(parts[2]); if (!nfa.ContainsKey(fromState)) { nfa[fromState] = new Dictionary<string, List>(); } if (!nfa[fromState].ContainsKey(symbol)) { nfa[fromState][symbol] = new List(); } nfa[fromState][symbol].Add(toState); }

// 转换为DFA
List<int> startStates = new List<int>();
startStates.Add(startState);
List<List<int>> dfaStates = new List<List<int>>();
List<int> dfaEndStates = new List<int>();
Dictionary<List<int>, int> dfaStateMap = new Dictionary<List<int>, int>();
dfaStates.Add(startStates);
dfaStateMap[startStates] = 0;
Queue<List<int>> queue = new Queue<List<int>>();
queue.Enqueue(startStates);
while (queue.Count > 0)
{
    List<int> currState = queue.Dequeue();
    foreach (string symbol in symbols)
    {
        List<int> nextState = new List<int>();
        foreach (int state in currState)
        {
            if (nfa.ContainsKey(state) && nfa[state].ContainsKey(symbol))
            {
                foreach (int toState in nfa[state][symbol])
                {
                    if (!nextState.Contains(toState))
                    {
                        nextState.Add(toState);
                    }
                }
            }
        }
        if (nextState.Count > 0)
        {
            if (!dfaStateMap.ContainsKey(nextState))
            {
                dfaStateMap[nextState] = dfaStates.Count;
                dfaStates.Add(nextState);
                queue.Enqueue(nextState);
            }
            if (currState.Count == 1 && endStates.Contains(currState[0].ToString()))
            {
                if (!dfaEndStates.Contains(dfaStateMap[nextState]))
                {
                    dfaEndStates.Add(dfaStateMap[nextState]);
                }
            }
        }
    }
}

// 显示DFA结果
listView2.Items.Clear();
for (int i = 0; i < dfaStates.Count; i++)
{
    List<int> state = dfaStates[i];
    ListViewItem item = new ListViewItem(string.Join(',', state));
    if (startStates.Contains(state[0]))
    {
        item.SubItems.Add('start');
    }
    else if (dfaEndStates.Contains(i))
    {
        item.SubItems.Add('end');
    }
    else
    {
        item.SubItems.Add('');
    }
    List<int> toStates = new List<int>();
    foreach (string symbol in symbols)
    {
        List<int> nextState = new List<int>();
        foreach (int s in state)
        {
            if (nfa.ContainsKey(s) && nfa[s].ContainsKey(symbol))
            {
                foreach (int toState in nfa[s][symbol])
                {
                    if (!nextState.Contains(toState))
                    {
                        nextState.Add(toState);
                    }
                }
            }
        }
        if (nextState.Count > 0)
        {
            toStates.Add(dfaStateMap[nextState]);
        }
        else
        {
            toStates.Add(-1);
        }
    }
    item.SubItems.Add(string.Join(',', toStates));
    listView2.Items.Add(item);
}
label5.Text = string.Join(',', startStates);
label7.Text = string.Join(',', dfaEndStates);

}