C#实现NFA到DFA、DFA到MFA转换算法

// 子集构造算法实现NFA到DFA转换 private Dictionary<string, HashSet> EpsilonClosure(Dictionary<string, HashSet> nfa, HashSet states) { HashSet closure = new HashSet(states); Stack stack = new Stack(states); while (stack.Count > 0) { string state = stack.Pop(); if (nfa.ContainsKey(state) && nfa[state].Contains('')) { foreach (string nextState in nfa[state]) { if (!closure.Contains(nextState)) { closure.Add(nextState); stack.Push(nextState); } } } } return closure.ToDictionary(x => x, x => nfa.ContainsKey(x) ? nfa[x] : new HashSet()); }

private Dictionary<string, HashSet> Move(Dictionary<string, HashSet> nfa, HashSet states, string symbol) { HashSet moveStates = new HashSet(); foreach (string state in states) { if (nfa.ContainsKey(state) && nfa[state].Contains(symbol)) { foreach (string nextState in nfa[state]) { moveStates.Add(nextState); } } } return EpsilonClosure(nfa, moveStates); }

private void button7_Click(object sender, EventArgs e) { // 获取NFA中的状态集、符号集、开始符、终结符 HashSet nfaStates = new HashSet(listView1.Items.Cast().Select(x => x.SubItems[0].Text)); string[] nfaSymbols = symbolSet; string nfaStartState = startSymbol; HashSet nfaEndStates = new HashSet(endSymbol.Split(';'));

// 初始化DFA中的状态集、符号集、开始符、终结符
Dictionary<string, HashSet<string>> dfa = new Dictionary<string, HashSet<string>>();
string[] dfaSymbols = nfaSymbols.Where(x => x != '').ToArray();
string dfaStartState = nfaStartState;
HashSet<string> dfaEndStates = new HashSet<string>();

// 计算NFA中的ε闭包
Dictionary<string, HashSet<string>> nfaEpsilonClosure = new Dictionary<string, HashSet<string>>();
foreach (string state in nfaStates)
{
    nfaEpsilonClosure[state] = EpsilonClosure(nfa, new HashSet<string>() { state });
}

// 初始化DFA的开始状态
dfa[dfaStartState] = nfaEpsilonClosure[dfaStartState];
Queue<string> queue = new Queue<string>();
queue.Enqueue(dfaStartState);

// 开始子集构造算法
while (queue.Count > 0)
{
    string currentState = queue.Dequeue();
    foreach (string symbol in dfaSymbols)
    {
        HashSet<string> nextState = EpsilonClosure(nfa, Move(nfa, dfa[currentState], symbol).ToHashSet());
        if (nextState.Count > 0 && !dfa.ContainsKey(string.Join(',', nextState)))
        {
            string nextStateName = string.Join(',', nextState);
            dfa[nextStateName] = nextState;
            queue.Enqueue(nextStateName);
        }
    }
}

// 计算DFA的终结状态集
foreach (string state in dfa.Keys)
{
    if (dfa[state].Intersect(nfaEndStates).Any())
    {
        dfaEndStates.Add(state);
    }
}

// 将DFA的转移表添加到listView2中
listView2.Items.Clear();
foreach (string state in dfa.Keys)
{
    foreach (string symbol in dfaSymbols)
    {
        HashSet<string> nextState = EpsilonClosure(nfa, Move(nfa, dfa[state], symbol).ToHashSet());
        if (nextState.Count > 0)
        {
            string nextStateName = string.Join(',', nextState);
            ListViewItem item = new ListViewItem(new string[] { state, symbol, nextStateName });
            listView2.Items.Add(item);
        }
    }
}

// 更新界面显示
label5.Text = '初始状态集:' + dfaStartState;
label7.Text = '终止状态集:';
foreach (string state in dfaEndStates)
{
    label7.Text += state + ';';
}
button9.Enabled = true;

}

// 子集构造算法实现DFA到MFA转换 private Dictionary<string, HashSet> GetEquivalentStates(Dictionary<string, HashSet> dfa) { Dictionary<string, HashSet> equivalentStates = new Dictionary<string, HashSet>(); HashSet visitedStates = new HashSet(); HashSet finalStates = new HashSet(dfa.Where(x => x.Value.Intersect(dfaEndStates).Any()).Select(x => x.Key)); HashSet nonFinalStates = new HashSet(dfa.Where(x => !finalStates.Contains(x.Key)).Select(x => x.Key)); equivalentStates['{' + string.Join(',', finalStates) + ''}'] = finalStates; equivalentStates['{' + string.Join(',', nonFinalStates) + ''}'] = nonFinalStates; Queue queue = new Queue(); queue.Enqueue('{' + string.Join(',', finalStates) + ''}'); queue.Enqueue('{' + string.Join(',', nonFinalStates) + ''}'); while (queue.Count > 0) { string currentState = queue.Dequeue(); if (visitedStates.Contains(currentState)) { continue; } visitedStates.Add(currentState); foreach (string symbol in symbolSet) { HashSet nextState = new HashSet(); foreach (string state in equivalentStates[currentState]) { HashSet nextStates = new HashSet(dfa[state].Where(x => x == symbol)); if (nextStates.Count > 0) { nextState.UnionWith(nextStates); } } if (nextState.Count == 0) { continue; } string nextStateName = '{' + string.Join(',', nextState) + ''}'; if (!equivalentStates.ContainsKey(nextStateName)) { equivalentStates[nextStateName] = nextState; queue.Enqueue(nextStateName); } } } return equivalentStates; }

private void button9_Click(object sender, EventArgs e) { // 获取DFA中的状态集、符号集、开始符、终结符 Dictionary<string, HashSet> dfa = listView2.Items.Cast().GroupBy(x => x.SubItems[0].Text).ToDictionary(x => x.Key, x => x.Select(y => y.SubItems[2].Text).ToHashSet()); string[] dfaSymbols = symbolSet.Where(x => x != '').ToArray(); string dfaStartState = label5.Text.Substring(label5.Text.IndexOf(':') + 1); HashSet dfaEndStates = new HashSet(label7.Text.Substring(label7.Text.IndexOf(':') + 1).Split(';'));

// 计算等价状态
Dictionary<string, HashSet<string>> equivalentStates = GetEquivalentStates(dfa);

// 构造MFA的状态集、符号集、开始符、终结符
Dictionary<string, HashSet<string>> mfa = new Dictionary<string, HashSet<string>>();
string[] mfaSymbols = dfaSymbols;
string mfaStartState = equivalentStates.Where(x => x.Value.Contains(dfaStartState)).Select(x => x.Key).FirstOrDefault();
HashSet<string> mfaEndStates = new HashSet<string>(equivalentStates.Where(x => x.Value.Intersect(dfaEndStates).Any()).Select(x => x.Key));

// 构造MFA的转移表
foreach (string state in equivalentStates.Keys)
{
    foreach (string symbol in mfaSymbols)
    {
        HashSet<string> nextState = new HashSet<string>();
        foreach (string s in equivalentStates[state])
        {
            if (dfa.ContainsKey(s) && dfa[s].Contains(symbol))
            {
                nextState.UnionWith(dfa[s].Where(x => x == symbol));
            }
        }
        if (nextState.Count > 0)
        {
            string nextStateName = '{\' + string.Join(',', nextState) + '\'}';
            if (!mfa.ContainsKey(state))
            {
                mfa[state] = new HashSet<string>();
            }
            mfa[state].Add(symbol + '->' + nextStateName);
        }
    }
}

// 将MFA的转移表添加到listView3中
listView3.Items.Clear();
foreach (string state in mfa.Keys)
{
    foreach (string transition in mfa[state])
    {
        ListViewItem item = new ListViewItem(new string[] { state, transition });
        listView3.Items.Add(item);
    }
}

// 更新界面显示
label9.Text = '初始状态集:' + mfaStartState;
label10.Text = '终止状态集:';
foreach (string state in mfaEndStates)
{
    label10.Text += state + ';';
}

}