C# 使用 VS 实现 NFA 到 DFA 转换功能

首先，需要对 NFA 数据进行解析，将其存储为图的形式，方便后续的转换操作。可以定义一个 NFAState 类来代表 NFA 中的一个状态，其中包含该状态的编号、是否为起始状态、是否为接受状态、以及该状态对应的转移关系。转移关系可以用一个字典来表示，将输入符号作为键，将能够到达的状态集合作为值。代码如下：

class NFAState
{
    public int Num; //状态编号
    public bool IsStart; //是否为起始状态
    public bool IsAccept; //是否为接受状态
    public Dictionary<string, HashSet<int>> Transitions; //转移关系

    public NFAState(int num, bool isStart = false, bool isAccept = false)
    {
        Num = num;
        IsStart = isStart;
        IsAccept = isAccept;
        Transitions = new Dictionary<string, HashSet<int>>();
    }
}

class NFA
{
    private List<NFAState> states; //状态集合
    private int startState; //起始状态编号
    private HashSet<int> acceptStates; //接受状态编号集合
    private HashSet<string> symbols; //符号集合

    public NFA()
    {
        states = new List<NFAState>();
        startState = -1;
        acceptStates = new HashSet<int>();
        symbols = new HashSet<string>();
    }

    //解析NFA数据
    public void ParseData(string[] lines)
    {
        //1. 解析起始状态编号和终结符数量
        string[] firstLine = lines[0].Split(':');
        startState = int.Parse(firstLine[1]);
        int symbolCount = int.Parse(lines[1].Split(':')[1]);

        //2. 解析符号集合
        string[] symbolLine = lines[2].Split(':');
        if (symbolLine[0] == "符号集")
        {
            string[] symbolStrings = symbolLine[1].Split(';');
            foreach (string symbolString in symbolStrings)
            {
                symbols.Add(symbolString);
            }
        }

        //3. 解析转移关系
        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 (states.Count <= fromState)
            {
                for (int j = states.Count; j <= fromState; j++)
                {
                    states.Add(new NFAState(j));
                }
            }
            if (states.Count <= toState)
            {
                for (int j = states.Count; j <= toState; j++)
                {
                    states.Add(new NFAState(j));
                }
            }

            //添加转移关系
            if (!states[fromState].Transitions.ContainsKey(symbol))
            {
                states[fromState].Transitions.Add(symbol, new HashSet<int>());
            }
            states[fromState].Transitions[symbol].Add(toState);
        }

        //4. 解析起始状态和接受状态
        states[startState].IsStart = true;
        for (int i = 0; i < states.Count; i++)
        {
            if (states[i].Transitions.ContainsKey("#"))
            {
                foreach (int toState in states[i].Transitions["#"])
                {
                    states[toState].IsAccept = true;
                    acceptStates.Add(toState);
                }
            }
        }
    }

    //将NFA转换为DFA
    public DFA ToDFA()
    {
        //使用子集构造法将NFA转换为DFA
        //首先构造起始状态的ε闭包
        HashSet<int> startClosure = EpsilonClosure(startState);

        //创建DFA的起始状态
        Dictionary<HashSet<int>, int> dfaStates = new Dictionary<HashSet<int>, int>();
        int dfaStartState = AddDFAState(dfaStates, startClosure);

        //遍历DFA的所有状态，逐个处理它们的转移关系
        Queue<HashSet<int>> queue = new Queue<HashSet<int>>();
        queue.Enqueue(startClosure);
        while (queue.Count > 0)
        {
            HashSet<int> currentSet = queue.Dequeue();
            int currentState = dfaStates[currentSet];

            //对于每个输入符号，计算当前状态的转移结果
            foreach (string symbol in symbols)
            {
                //计算当前状态在输入符号下的ε闭包
                HashSet<int> nextSet = new HashSet<int>();
                foreach (int nfaState in currentSet)
                {
                    if (states[nfaState].Transitions.ContainsKey(symbol))
                    {
                        foreach (int toState in states[nfaState].Transitions[symbol])
                        {
                            nextSet.UnionWith(EpsilonClosure(toState));
                        }
                    }
                }

                //如果新状态还不存在，则创建一个新的状态
                if (nextSet.Count > 0 && !dfaStates.ContainsKey(nextSet))
                {
                    int newState = AddDFAState(dfaStates, nextSet);
                    queue.Enqueue(nextSet);
                }

                //将当前状态和输入符号下的转移结果添加到DFA的状态转移表中
                if (nextSet.Count > 0)
                {
                    int nextState = dfaStates[nextSet];
                    dfaStates[currentSet].Transitions[symbol] = nextState;
                }
            }
        }

        //创建DFA对象并返回
        DFA dfa = new DFA();
        dfa.SetStates(dfaStartState, acceptStates, dfaStates);
        return dfa;
    }

    //计算一个状态的ε闭包
    private HashSet<int> EpsilonClosure(int state)
    {
        HashSet<int> closure = new HashSet<int>();
        Stack<int> stack = new Stack<int>();
        closure.Add(state);
        stack.Push(state);
        while (stack.Count > 0)
        {
            int currentState = stack.Pop();
            if (states[currentState].Transitions.ContainsKey("#"))
            {
                foreach (int toState in states[currentState].Transitions["#"])
                {
                    if (!closure.Contains(toState))
                    {
                        closure.Add(toState);
                        stack.Push(toState);
                    }
                }
            }
        }
        return closure;
    }

    //将一个状态集合添加到DFA中，并返回它的编号
    private int AddDFAState(Dictionary<HashSet<int>, int> dfaStates, HashSet<int> stateSet)
    {
        int stateNum = dfaStates.Count;
        dfaStates.Add(stateSet, stateNum);
        return stateNum;
    }
}

class DFAState
{
    public int Num; //状态编号
    public bool IsStart; //是否为起始状态
    public bool IsAccept; //是否为接受状态
    public Dictionary<string, int> Transitions; //转移关系

    public DFAState(int num, bool isStart = false, bool isAccept = false)
    {
        Num = num;
        IsStart = isStart;
        IsAccept = isAccept;
        Transitions = new Dictionary<string, int>();
    }
}

class DFA
{
    private List<DFAState> states; //状态集合
    private int startState; //起始状态编号
    private HashSet<int> acceptStates; //接受状态编号集合

    public DFA()
    {
        states = new List<DFAState>();
        startState = -1;
        acceptStates = new HashSet<int>();
    }

    //设置DFA的状态集合、起始状态和接受状态
    public void SetStates(int startState, HashSet<int> acceptStates, Dictionary<HashSet<int>, int> dfaStates)
    {
        //创建DFA的所有状态
        foreach (KeyValuePair<HashSet<int>, int> pair in dfaStates)
        {
            int stateNum = pair.Value;
            bool isStart = (stateNum == startState);
            bool isAccept = acceptStates.Contains(stateNum);
            DFAState state = new DFAState(stateNum, isStart, isAccept);
            states.Add(state);
        }

        //设置转移关系
        foreach (KeyValuePair<HashSet<int>, int> pair in dfaStates)
        {
            HashSet<int> stateSet = pair.Key;
            int stateNum = pair.Value;
            DFAState state = states[stateNum];
            foreach (string symbol in NFA.symbols)
            {
                HashSet<int> nextSet = new HashSet<int>();
                foreach (int nfaState in stateSet)
                {
                    if (NFA.states[nfaState].Transitions.ContainsKey(symbol))
                    {
                        foreach (int toState in NFA.states[nfaState].Transitions[symbol])
                        {
                            nextSet.Add(toState);
                        }
                    }
                }
                if (nextSet.Count > 0)
                {
                    int nextState = dfaStates[nextSet];
                    state.Transitions[symbol] = nextState;
                }
            }
        }

        //设置起始状态和接受状态
        this.startState = startState;
        this.acceptStates = acceptStates;
    }

    //将DFA显示在ListView中
    public void Display(ListView listView)
    {
        //添加表头
        listView.Columns.Add("初始状态");
        listView.Columns.Add("接受符号");
        listView.Columns.Add("到达状态");

        //添加每个状态的信息
        foreach (DFAState state in states)
        {
            ListViewItem item = new ListViewItem(state.IsStart ? "->" + state.Num.ToString() : state.Num.ToString());
            item.SubItems.Add(state.IsAccept ? "*" : "");
            foreach (KeyValuePair<string, int> pair in state.Transitions)
            {
                item.SubItems.Add(pair.Key + "=>" + pair.Value.ToString());
            }
            listView.Items.Add(item);
        }
    }
}

在 button7_Click 函数中，首先需要解析 NFA 数据，然后将 NFA 转换为 DFA，并将 DFA 显示在 listView2 中。代码如下：

private void button7_Click(object sender, EventArgs e)
{
    if (openFileDialog1.ShowDialog() == DialogResult.OK)
    {
        string[] lines = File.ReadAllLines(openFileDialog1.FileName);

        //解析NFA数据
        NFA nfa = new NFA();
        nfa.ParseData(lines);

        //将NFA转换为DFA
        DFA dfa = nfa.ToDFA();

        //将DFA显示在ListView中
        dfa.Display(listView2);
    }
}