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

private void button7_Click(object sender, EventArgs e)
{
    // 读取NFA文件
    string[] lines = File.ReadAllLines("NFA.txt");
    int start = int.Parse(lines[0].Split(':')[1]); // 获取开始符号
    string[] terminals = lines[1].Split(':')[1].Split(';'); // 获取终结符
    List<string> symbols = new List<string>(); // 存储所有符号
    List<State> states = new List<State>(); // 存储所有状态
    for (int i = 2; i < lines.Length; i++)
    {
        string[] tokens = lines[i].Split('	');
        int from = int.Parse(tokens[0]);
        string symbol = tokens[1];
        int to = int.Parse(tokens[2]);
        if (!symbols.Contains(symbol))
        {
            symbols.Add(symbol);
        }
        State state = states.Find(s => s.Id == from);
        if (state == null)
        {
            state = new State(from);
            states.Add(state);
        }
        state.AddTransition(symbol, to);
    }

    // 获取NFA的初始状态集和终止状态集
    List<int> initialStates = new List<int>();
    List<int> finalStates = new List<int>();
    initialStates.Add(start);
    foreach (State state in states)
    {
        if (state.IsFinal())
        {
            finalStates.Add(state.Id);
        }
    }
    label3.Text = string.Join(",", initialStates);
    label4.Text = string.Join(",", finalStates);

    // 将NFA转换为DFA
    List<State> dfaStates = new List<State>();
    List<string> dfaSymbols = new List<string>(symbols);
    List<int> dfaInitialStates = new List<int>();
    List<int> dfaFinalStates = new List<int>();
    List<Tuple<List<int>, string, List<int>>> dfaTransitions = new List<Tuple<List<int>, string, List<int>>>();
    List<List<int>> dfaStateSets = new List<List<int>>();
    dfaStateSets.Add(EpsilonClosure(initialStates, states)); // 初始化DFA的初始状态集
    dfaInitialStates.Add(0); // DFA的初始状态为0
    int dfaStateIndex = 0;
    while (dfaStateIndex < dfaStateSets.Count)
    {
        List<int> dfaStateSet = dfaStateSets[dfaStateIndex];
        State dfaState = new State(dfaStateIndex);
        dfaStates.Add(dfaState);
        foreach (string symbol in dfaSymbols)
        {
            List<int> nextStates = EpsilonClosure(Move(dfaStateSet, symbol, states), states);
            if (nextStates.Count == 0)
            {
                continue;
            }
            int nextDfaStateIndex = dfaStateSets.IndexOf(nextStates);
            if (nextDfaStateIndex == -1)
            {
                nextDfaStateIndex = dfaStateSets.Count;
                dfaStateSets.Add(nextStates);
            }
            dfaTransitions.Add(new Tuple<List<int>, string, List<int>>(dfaStateSet, symbol, nextStates));
            dfaState.AddTransition(symbol, nextDfaStateIndex);
        }
        if (dfaStateSet.Intersect(finalStates).Count() > 0)
        {
            dfaFinalStates.Add(dfaStateIndex);
        }
        dfaStateIndex++;
    }

    // 获取DFA的初始状态集和终止状态集
    dfaInitialStates = dfaInitialStates.Intersect(dfaFinalStates).ToList();
    label5.Text = string.Join(",", dfaInitialStates);
    label7.Text = string.Join(",", dfaFinalStates);

    // 将DFA显示在listView2中
    listView2.Columns.Add("起始状态");
    listView2.Columns.Add("接受符号");
    listView2.Columns.Add("到达状态");
    foreach (Tuple<List<int>, string, List<int>> transition in dfaTransitions)
    {
        ListViewItem item = new ListViewItem(string.Join(",", transition.Item1));
        item.SubItems.Add(transition.Item2);
        item.SubItems.Add(string.Join(",", transition.Item3));
        listView2.Items.Add(item);
    }
}

// 获取状态集的epsilon闭包
private List<int> EpsilonClosure(List<int> stateSet, List<State> states)
{
    List<int> closure = new List<int>(stateSet);
    Queue<int> queue = new Queue<int>(stateSet);
    while (queue.Count > 0)
    {
        int stateId = queue.Dequeue();
        State state = states.Find(s => s.Id == stateId);
        foreach (int next in state.GetTransitions(""))
        {
            if (!closure.Contains(next))
            {
                closure.Add(next);
                queue.Enqueue(next);
            }
        }
    }
    return closure;
}

// 获取状态集在symbol下的转移状态集
private List<int> Move(List<int> stateSet, string symbol, List<State> states)
{
    List<int> nextStates = new List<int>();
    foreach (int stateId in stateSet)
    {
        State state = states.Find(s => s.Id == stateId);
        nextStates.AddRange(state.GetTransitions(symbol));
    }
    return nextStates;
}

// 状态类
class State
{
    public int Id { get; set; }
    private Dictionary<string, List<int>> transitions;

    public State(int id)
    {
        Id = id;
        transitions = new Dictionary<string, List<int>>();
    }

    public void AddTransition(string symbol, int to)
    {
        if (!transitions.ContainsKey(symbol))
        {
            transitions[symbol] = new List<int>();
        }
        transitions[symbol].Add(to);
    }

    public List<int> GetTransitions(string symbol)
    {
        if (transitions.ContainsKey(symbol))
        {
            return transitions[symbol];
        }
        else
        {
            return new List<int>();
        }
    }

    public bool IsFinal()
    {
        return transitions.ContainsKey("");
    }
}