NFA转DFA：使用C#实现NFA到DFA的转换并显示结果

private void button7_Click(object sender, EventArgs e) { // 初始化DFA数据 List dfaStates = new List(); // DFA状态集合 List dfaAccepts = new List(); // DFA接受符号集合 List dfaTransitions = new List(); // DFA转移集合 List<List> dfaTable = new List<List>(); // DFA转移表 List dfaStartState = new List(); // DFA初始状态集合 List dfaFinalStates = new List(); // DFA终止状态集合

// 获取NFA数据
string[] lines = {'开始符:7', '终结符:26', '符号集:a;b;', '1	a	2', '3	b	4', '5	#	3', '5	#	1', '4	#	6', '2	#	6', '7	#	5', '6	#	8', '6	#	5', '7	#	8', '9	a	10', '11	a	12', '10	#	11', '13	b	14', '15	b	16', '14	#	15', '17	#	13', '17	#	9', '16	#	18', '12	#	18', '8	#	17', '19	a	20', '21	b	22', '23	#	21', '23	#	19', '22	#	24', '20	#	24', '25	#	23', '24	#	26', '24	#	23', '25	#	26', '18	#	25'};

// 解析NFA数据
int startState = int.Parse(lines[0].Split(':')[1]);
int endState = int.Parse(lines[1].Split(':')[1]);
string[] symbols = lines[2].Split(':')[1].Split(';');
Dictionary<string, List<string>> transitions = new Dictionary<string, List<string>>();
for (int i = 3; i < lines.Length; i++)
{
    string[] parts = lines[i].Split('	');
    string fromState = parts[0];
    string symbol = parts[1];
    string toState = parts[2];
    string key = fromState + "," + symbol;
    if (!transitions.ContainsKey(key))
    {
        transitions[key] = new List<string>();
    }
    transitions[key].Add(toState);
}

// 初始化DFA初始状态集合
dfaStartState.Add(startState.ToString());

// 构造DFA状态集合和转移集合
Queue<List<string>> unmarkedStates = new Queue<List<string>>();
unmarkedStates.Enqueue(dfaStartState);
while (unmarkedStates.Count > 0)
{
    List<string> currState = unmarkedStates.Dequeue();
    if (!dfaStates.Contains(string.Join(",", currState)))
    {
        dfaStates.Add(string.Join(",", currState));
        foreach (string symbol in symbols)
        {
            List<string> toStates = new List<string>();
            foreach (string state in currState)
            {
                string key = state + "," + symbol;
                if (transitions.ContainsKey(key))
                {
                    toStates.AddRange(transitions[key]);
                }
            }
            if (toStates.Count > 0)
            {
                dfaTransitions.Add(string.Join(",", currState) + "," + symbol + "," + string.Join(",", toStates));
                if (!dfaStates.Contains(string.Join(",", toStates)))
                {
                    unmarkedStates.Enqueue(toStates);
                }
            }
        }
    }
}

// 构造DFA接受符号集合和终止状态集合
foreach (string state in dfaStates)
{
    bool isAccept = false;
    foreach (string s in state.Split(','))
    {
        if (int.Parse(s) == endState)
        {
            isAccept = true;
            break;
        }
    }
    if (isAccept)
    {
        dfaAccepts.Add(state);
        dfaFinalStates.Add(state);
    }
}

// 显示DFA数据
listView2.Columns.Add("起始状态");
listView2.Columns.Add("接受符号");
listView2.Columns.Add("到达状态");
foreach (string transition in dfaTransitions)
{
    string[] parts = transition.Split(',');
    ListViewItem item = new ListViewItem(parts[0]);
    item.SubItems.Add(parts[1]);
    item.SubItems.Add(parts[2]);
    listView2.Items.Add(item);
}
label5.Text = string.Join(",", dfaStartState);
label7.Text = string.Join(",", dfaFinalStates);

}