NFA 转 DFA 算法实现：子集构造法 - 使用 VSC# 语言

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Reflection.Emit;
using System.Security.Cryptography;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;

namespace byyljxfzxt
{
    public partial class Form3 : Form
    {
        public Form3()
        {
            InitializeComponent();
        }

        string[] lines;
        string startSymbol;
        string endSymbol;
        string[] symbolSet;
        string[] endStates;
        
        private void button5_Click(object sender, EventArgs e)
        {
            // 获取开始符和终结符
            string startSym = '开始符:' + startSymbol;
            string endSym = '终结符:' + endSymbol;

            // 初始化NFA文件内容
            string nfaContent = startSym + "\n" + endSym + "\n";

            // 遍历listView1中的数据，生成NFA文件内容
            for (int i = 0; i < listView1.Items.Count; i++)
            {
                string startState = listView1.Items[i].SubItems[0].Text;
                string symbol = listView1.Items[i].SubItems[1].Text;
                string endState = listView1.Items[i].SubItems[2].Text;

                // 拼接NFA文件内容
                nfaContent += startState + "\t" + symbol + "\t" + endState + "\n";
            }

            // 保存NFA文件
            SaveFileDialog saveFileDialog = new SaveFileDialog();
            saveFileDialog.Filter = "NFA文件(*.nfa)|*.nfa";
            saveFileDialog.FileName = "NFA.txt";
            if (saveFileDialog.ShowDialog() == DialogResult.OK)
            {
                string fileName = saveFileDialog.FileName;
                File.WriteAllText(fileName, nfaContent, Encoding.UTF8);
            }
        }

        private void label7_Click(object sender, EventArgs e)
        {

        }

        private void listView1_SelectedIndexChanged(object sender, EventArgs e)
        {
            ListViewItem item = new ListViewItem();
            item.Text = Convert.ToString(listView1.Items.Count + 1);
            item.SubItems.Add("0");
            item.SubItems.Add("1");
            item.SubItems.Add("2");
            listView1.Items.Add(item);
        }

        private void button3_Click(object sender, EventArgs e)
        {
            OpenFileDialog openFileDialog1 = new OpenFileDialog();
            openFileDialog1.Filter = "NFA Files|*.nfa";
            openFileDialog1.Title = "Select an NFA File";

            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            {
                lines = File.ReadAllLines(openFileDialog1.FileName);
                startSymbol = lines[0].Substring(lines[0].IndexOf(':') + 1).Trim();
                endSymbol = lines[1].Substring(lines[1].IndexOf(':') + 1).Trim();
                symbolSet = lines[2].Substring(lines[2].IndexOf(':') + 1).Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);

                for (int i = 3; i < lines.Length; i++)
                {
                    string[] tokens = lines[i].Split(new char[] { '\t' }, StringSplitOptions.RemoveEmptyEntries);
                    string startState = tokens[0];
                    string inputSymbol = tokens[1];
                    string nextState = tokens[2];

                    ListViewItem item = new ListViewItem(startState);
                    item.SubItems.Add(inputSymbol);
                    item.SubItems.Add(nextState);

                    listView1.Items.Add(item);
                }
            }
            label3.Text = "初始状态集:" + startSymbol;
            label4.Text = "终止状态集:" + endSymbol;
            button6.Enabled = false;
            button7.Enabled = true;
        }

        private void button6_Click(object sender, EventArgs e)
        {
            OpenFileDialog openFileDialog1 = new OpenFileDialog();
            openFileDialog1.Filter = "DFA文件|*.dfa";
            openFileDialog1.Title = "选择DFA文件";
            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            {
                lines = File.ReadAllLines(openFileDialog1.FileName);
                startSymbol = lines[0].Split(':').Last().Trim();
                endStates = lines[1].Split(':').Last().Split(';').Select(x => x.Trim()).ToArray();
                int maxState = int.Parse(lines[2].Split(':').Last().Trim());
                string[] symbols = lines[3].Split(':').Last().Split(';').Select(x => x.Trim()).ToArray();
                Dictionary<string, Dictionary<string, string>> transitions = new Dictionary<string, Dictionary<string, string>>();
                for (int i = 4; i < lines.Length; i++)
                {
                    string[] parts = lines[i].Split('\t');
                    string fromState = parts[0].Trim();
                    string symbol = parts[1].Trim();
                    string toState = parts[2].Trim();
                    if (!transitions.ContainsKey(fromState))
                    {
                        transitions[fromState] = new Dictionary<string, string>();
                    }
                    transitions[fromState][symbol] = toState;
                }
                listView2.Items.Clear();
                foreach (string state in transitions.Keys)
                {
                    foreach (string symbol in transitions[state].Keys)
                    {
                        string toState = transitions[state][symbol];
                        ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
                        listView2.Items.Add(item);
                    }
                }
            }
            label5.Text = "初始状态集:" + startSymbol;
            label7.Text = "终止状态集:";
            for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
                 label7.Text = label7.Text + endStates[i] + ";";
            button7.Enabled = false;
            button9.Enabled = true;
        }

        private void button7_Click(object sender, EventArgs e)//NFA->DFA
        {
            // 获取NFA信息
            string startState = startSymbol;
            string[] endStates = endSymbol.Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);
            List<string> symbolSet = new List<string>(this.symbolSet);

            // 初始化DFA
            Dictionary<string, Dictionary<string, string>> dfa = new Dictionary<string, Dictionary<string, string>>();
            List<string> dfaStates = new List<string>();
            List<string> unmarkedStates = new List<string>();
            List<List<string>> stateSets = new List<List<string>>();

            // 计算开始状态集
            List<string> startStateSet = E_closure(new List<string>() { startState });
            stateSets.Add(startStateSet);
            dfaStates.Add("{" + string.Join(",", startStateSet) + "}");
            unmarkedStates.Add("{" + string.Join(",", startStateSet) + "}");

            // 计算其他状态集
            while (unmarkedStates.Count > 0)
            {
                string currentStateSet = unmarkedStates[0];
                unmarkedStates.RemoveAt(0);

                foreach (string s in symbolSet)
                {
                    List<string> moveStates = Move(currentStateSet, s);
                    List<string> nextStateSet = E_closure(moveStates);

                    if (nextStateSet.Count > 0)
                    {
                        string nextStateSetName = "{" + string.Join(",", nextStateSet) + "}";

                        if (!dfaStates.Contains(nextStateSetName))
                        {
                            dfaStates.Add(nextStateSetName);
                            unmarkedStates.Add(nextStateSetName);
                            stateSets.Add(nextStateSet);
                        }

                        if (!dfa.ContainsKey(currentStateSet))
                        {
                            dfa[currentStateSet] = new Dictionary<string, string>();
                        }
                        dfa[currentStateSet][s] = nextStateSetName;
                    }
                }
            }

            // 计算终止状态集
            List<string> endStateSet = new List<string>();
            foreach (List<string> stateSet in stateSets)
            {
                foreach (string endState in endStates)
                {
                    if (stateSet.Contains(endState))
                    {
                        endStateSet.Add("{" + string.Join(",", stateSet) + "}");
                        break;
                    }
                }
            }

            // 生成DFA文件内容
            string dfaContent = "开始符:" + dfaStates[0] + "\n";
            dfaContent += "终结符:" + string.Join(";", endStateSet) + "\n";
            dfaContent += "状态数:" + dfaStates.Count + "\n";
            dfaContent += "符号集:" + string.Join(";", symbolSet) + "\n";

            foreach (string state in dfaStates)
            {
                foreach (string symbol in symbolSet)
                {
                    if (dfa.ContainsKey(state) && dfa[state].ContainsKey(symbol))
                    {
                        string nextState = dfa[state][symbol];
                        dfaContent += state + "\t" + symbol + "\t" + nextState + "\n";
                    }
                }
            }

            // 保存DFA文件
            SaveFileDialog saveFileDialog = new SaveFileDialog();
            saveFileDialog.Filter = "DFA文件(*.dfa)|*.dfa";
            saveFileDialog.FileName = "DFA.txt";
            if (saveFileDialog.ShowDialog() == DialogResult.OK)
            {
                string fileName = saveFileDialog.FileName;
                File.WriteAllText(fileName, dfaContent, Encoding.UTF8);
            }
        }

        // 计算状态集的ε闭包
        private List<string> E_closure(List<string> states)
        {
            List<string> result = new List<string>(states);

            Stack<string> stack = new Stack<string>(states);
            while (stack.Count > 0)
            {
                string state = stack.Pop();

                foreach (ListViewItem item in listView1.Items)
                {
                    if (item.SubItems[0].Text == state && item.SubItems[1].Text == "ε")
                    {
                        string nextState = item.SubItems[2].Text;
                        if (!result.Contains(nextState))
                        {
                            result.Add(nextState);
                            stack.Push(nextState);
                        }
                    }
                }
            }

            return result;
        }

        // 计算状态集在输入符号下的后继状态集
        private List<string> Move(string stateSet, string symbol)
        {
            List<string> result = new List<string>();

            string[] states = stateSet.Substring(1, stateSet.Length - 2).Split(',');
            foreach (string state in states)
            {
                foreach (ListViewItem item in listView1.Items)
                {
                    if (item.SubItems[0].Text == state && item.SubItems[1].Text == symbol)
                    {
                        string nextState = item.SubItems[2].Text;
                        if (!result.Contains(nextState))
                        {
                            result.Add(nextState);
                        }
                    }
                }
            }

            return result;
        }
    }
}