NFA 转 DFA 功能实现 - C# 代码示例

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.TreeView;

namespace WindowsFormsApp1.Resources.function_cs
{
    class NFA_DFA
    {
        DFA dfa = null;

        public NFA_DFA(NFA nfa)
        {
            dfa = new DFA(nfa);
        }

        public DFA get_dfa()
        {
            return dfa;
        }
    }

    public class DFA
    {
        int stateNum;                   // 状态数
        int initialState = 1;           //初始状态
        List<int> finalStates;          // 终止状态集合
        List<char> alphabet;            // 字母表
        List<List<Tuple<int, char>>> graph;    // 状态关系图
        public List<List<Tuple<int, char>>> get_graph()
        {
            return graph;
        }

        public List<int> get_finalStates()
        {
            return finalStates;
        }

        public int get_initialState()
        {
            return initialState;
        }

        public int get_stateNum()
        {
            return stateNum;
        }

        public List<char> get_alphabet()
        {
            return alphabet;
        }

        //public void set_graph(List<List<Tuple<int, char>>> graph)
        //{
        //    this.graph = graph;
        //}

        //public void set_stateNum(int n)
        //{
        //    this.stateNum = n;
        //}

        //public void set_finalStates(List<int> finalStates)
        //{
        //    this.finalStates = finalStates;
        //}

        //public void set_initialState(int initialState)
        //{
        //    this.initialState = initialState;
        //}

        //public void set_alphabet(List<char> alphabet)
        //{
        //    this.alphabet = alphabet;
        //}

        public DFA(int stateNum, int initialState, List<int> finalStates, List<char> alphabet, List<List<Tuple<int, char>>> graph)
        {
            this.stateNum = stateNum;
            this.initialState = initialState;
            this.graph = graph;
            this.alphabet = alphabet;
            this.finalStates = finalStates;
        }

        public DFA(NFA nfa)
        {
            stateNum = 1;
            finalStates = new List<int>();
            graph = new List<List<Tuple<int, char>>>();
            graph.Add(new List<Tuple<int, char>>());
            alphabet = new List<char>();

            // 1.确定字母表
            foreach (var state in nfa.get_graph())
            {
                foreach (var tuple in state)
                {
                    if (tuple.Item2 != '#' && !alphabet.Contains(tuple.Item2))
                        alphabet.Add(tuple.Item2);
                }
            }

            // 2.对初始状态进行 e-closure 运算，得到 DFA 起始状态
            List<int> start = EpsilonClosure(nfa.get_se().Item1, nfa);

            // 3.开始子集构造
            HashSet<List<int>> markedSet = new HashSet<List<int>>();        // 标记已经加入到 DFA 中的状态
            Queue<List<int>> unmarkedSet = new Queue<List<int>>();           // 待处理的状态集合队列
            unmarkedSet.Enqueue(start);
            markedSet.Add(start);
            AddNewState(start,nfa);

            while (unmarkedSet.Count > 0)
            {
                List<int> T = unmarkedSet.Dequeue();
                foreach (var alpha in alphabet)
                {
                    List<int> U = EpsilonClosure(NFAmove(T, alpha, nfa), nfa);
                    if (U != null && U.Count!=0)
                    {
                        int index = isexit(markedSet, U);
                        if (index == 0)
                        {
                            AddNewState(U, nfa);
                            markedSet.Add(U);
                            unmarkedSet.Enqueue(U);
                        }
                        graph[isexit(markedSet, T)].Add(Tuple.Create(isexit(markedSet, U), alpha));
                    }
                }
            }
        }

        //判断markedSet中是否已经存在U
        int isexit(HashSet<List<int>> markedSet, List<int> U)
        {
            List<int> u= U;
            u.Sort();
            for (int i=0; i< markedSet.Count;i++)
            {
                var state = markedSet.ElementAt(i);
                List<int> v = state;
                v.Sort();
                if (u.SequenceEqual(v))
                    return i+1;
            }
            return 0;
        }

        // 生成新状态
        void AddNewState(List<int> state, NFA nfa)
        {
            graph.Add(new List<Tuple<int, char>>());
            if (IsFinalState(state, nfa))
                finalStates.Add(stateNum);
            stateNum++;
        }

        // 判断一个状态集合是否为终止状态
        bool IsFinalState(List<int> stateSet, NFA nfa)
        {
            foreach (var s in stateSet)
            {
                if (nfa.get_se().Item2 == s)
                    return true;
            }
            return false;
        }

        // 获取某个状态集合通过 symbol 转移的结果
        List<int> NFAmove(List<int> T, char symbol, NFA nfa)
        {
            List<int> result = new List<int>();
            foreach (var t in T)
            {
                foreach (var tuple in nfa.get_graph()[t])
                {
                    if (tuple.Item2 == symbol && !result.Contains(tuple.Item1))
                        result.Add(tuple.Item1);
                }
            }
            return result;
        }

        // e-closure 运算
        List<int> EpsilonClosure(int state, NFA nfa)
        {
            HashSet<int> visited = new HashSet<int>();
            Stack<int> stack = new Stack<int>();
            stack.Push(state);
            visited.Add(state);
            while (stack.Count > 0)
            {
                int s = stack.Pop();
                foreach (var tuple in nfa.get_graph()[s])
                {
                    if (tuple.Item2 == '#' && !visited.Contains(tuple.Item1))
                    {
                        visited.Add(tuple.Item1);
                        stack.Push(tuple.Item1);
                    }
                }
            }
            return visited.ToList();
        }

        // e-closure 运算
        List<int> EpsilonClosure(List<int> T, NFA nfa)
        {
            HashSet<int> visited = new HashSet<int>();
            Stack<int> stack = new Stack<int>();
            foreach (var t in T)
            {
                stack.Push(t);
                visited.Add(t);
            }

            while (stack.Count > 0)
            {
                int s = stack.Pop();
                foreach (var tuple in nfa.get_graph()[s])
                {
                    if (tuple.Item2 == '#' && !visited.Contains(tuple.Item1))
                    {
                        visited.Add(tuple.Item1);
                        stack.Push(tuple.Item1);
                    }
                }
            }
            return visited.ToList();
        }
    }
}

private void button7_Click(object sender, EventArgs e)//NFA->DFA
{
    // 获取NFA
    NFA nfa = new NFA();
    nfa.set_graph(listView1_to_graph(listView1));
    nfa.set_alphabet(symbolSet);
    nfa.set_se(startSymbol, endSymbol);

    // NFA转DFA
    NFA_DFA nfa_dfa = new NFA_DFA(nfa);
    DFA dfa = nfa_dfa.get_dfa();

    // 将DFA显示在listView2上
    listView2.Items.Clear();
    foreach (var state in dfa.get_graph())
    {
        foreach (var tuple in state)
        {
            string startState = (tuple.Item1 + 1).ToString();
            string inputSymbol = tuple.Item2.ToString();
            string endState = (state.IndexOf(tuple) + 1).ToString();

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

            listView2.Items.Add(item);
        }
    }
    label5.Text = "初始状态集:" + dfa.get_initialState().ToString();
    label7.Text = "终止状态集:";
    foreach (var state in dfa.get_finalStates())
        label7.Text += " " + (state + 1).ToString();
    button6.Enabled = true;
}