NFA生成DFAC#sharpe代码

以下是将NFA转换为DFA的C#代码示例：

using System;
using System.Collections.Generic;

namespace NFAtoDFA
{
    class Program
    {
        static void Main(string[] args)
        {
            // 输入NFA转移函数
            Dictionary<Tuple<int, char>, List<int>> nfaDelta = new Dictionary<Tuple<int, char>, List<int>>();
            nfaDelta.Add(Tuple.Create(1, 'a'), new List<int> { 1, 2 });
            nfaDelta.Add(Tuple.Create(1, 'b'), new List<int> { 1 });
            nfaDelta.Add(Tuple.Create(2, 'a'), new List<int> { 3 });
            nfaDelta.Add(Tuple.Create(2, 'b'), new List<int> { 2 });
            nfaDelta.Add(Tuple.Create(3, 'a'), new List<int> { 3 });
            nfaDelta.Add(Tuple.Create(3, 'b'), new List<int> { 3 });

            // 输入NFA终态集合
            List<int> nfaFinalStates = new List<int> { 2, 3 };

            // 将NFA转换为DFA
            Dictionary<Tuple<int, char>, int> dfaDelta = new Dictionary<Tuple<int, char>, int>();
            List<int> dfaStartState = EpsilonClosure(new List<int> { 1 }, nfaDelta);
            List<List<int>> dfaStates = new List<List<int>> { dfaStartState };
            List<int> dfaFinalStates = new List<int>();
            Queue<List<int>> queue = new Queue<List<int>>();
            queue.Enqueue(dfaStartState);
            while (queue.Count > 0)
            {
                List<int> dfaState = queue.Dequeue();
                foreach (char symbol in new char[] { 'a', 'b' })
                {
                    List<int> nfaDestinations = new List<int>();
                    foreach (int nfaState in dfaState)
                    {
                        if (nfaDelta.ContainsKey(Tuple.Create(nfaState, symbol)))
                        {
                            nfaDestinations.AddRange(nfaDelta[Tuple.Create(nfaState, symbol)]);
                        }
                    }
                    List<int> dfaDestination = EpsilonClosure(nfaDestinations, nfaDelta);
                    if (!dfaStates.Contains(dfaDestination))
                    {
                        dfaStates.Add(dfaDestination);
                        queue.Enqueue(dfaDestination);
                        if (dfaDestination.Exists(x => nfaFinalStates.Contains(x)))
                        {
                            dfaFinalStates.Add(dfaStates.IndexOf(dfaDestination));
                        }
                    }
                    dfaDelta[Tuple.Create(dfaStates.IndexOf(dfaState), symbol)] = dfaStates.IndexOf(dfaDestination);
                }
            }

            // 输出DFA转移函数
            Console.WriteLine("DFA Delta:");
            foreach (KeyValuePair<Tuple<int, char>, int> entry in dfaDelta)
            {
                Console.WriteLine($"({entry.Key.Item1}, {entry.Key.Item2}) -> {entry.Value}");
            }

            // 输出DFA状态集合
            Console.WriteLine("DFA States:");
            for (int i = 0; i < dfaStates.Count; i++)
            {
                Console.WriteLine($"{i}: {string.Join(",", dfaStates[i])}");
            }

            // 输出DFA终态集合
            Console.WriteLine("DFA Final States:");
            Console.WriteLine(string.Join(",", dfaFinalStates));
            Console.ReadLine();
        }

        // 计算nfaStates的ε闭包
        static List<int> EpsilonClosure(List<int> nfaStates, Dictionary<Tuple<int, char>, List<int>> nfaDelta)
        {
            List<int> result = new List<int>(nfaStates);
            Queue<int> queue = new Queue<int>(nfaStates);
            while (queue.Count > 0)
            {
                int nfaState = queue.Dequeue();
                if (nfaDelta.ContainsKey(Tuple.Create(nfaState, 'ε')))
                {
                    foreach (int nextState in nfaDelta[Tuple.Create(nfaState, 'ε')])
                    {
                        if (!result.Contains(nextState))
                        {
                            result.Add(nextState);
                            queue.Enqueue(nextState);
                        }
                    }
                }
            }
            return result;
        }
    }
}
``