C# 使用子集构造算法实现 NFA 到 DFA 和 DFA 到 MFA 的转换

// 子集构造算法实现NFA到DFA的转换 private void button7_Click(object sender, EventArgs e) { // 获取NFA的开始符、终结符、符号集和状态转移表 string startSym = startSymbol; string endSym = endSymbol; string[] symbols = symbolSet; Dictionary<string, Dictionary<string, List>> transitions = new Dictionary<string, Dictionary<string, List>>(); for (int i = 3; i < lines.Length; i++) { string[] parts = lines[i].Split('\t'); string fromState = parts[0].Trim(); string symbol = parts[1].Trim(); string toState = parts[2].Trim(); if (!transitions.ContainsKey(fromState)) { transitions[fromState] = new Dictionary<string, List>(); } if (!transitions[fromState].ContainsKey(symbol)) { transitions[fromState][symbol] = new List(); } transitions[fromState][symbol].Add(toState); }

// 初始化DFA的开始符和状态转移表
List<string> startStates = EpsilonClosure(new List<string> { startSym }, transitions);
Dictionary<string, Dictionary<string, List<string>>> dfaTransitions = new Dictionary<string, Dictionary<string, List<string>>>();
dfaTransitions["{" + string.Join(",", startStates) + "}"] = new Dictionary<string, List<string>>();

// 对DFA的状态集进行迭代
Queue<string> queue = new Queue<string>();
queue.Enqueue("{" + string.Join(",", startStates) + "}");
while (queue.Count > 0)
{
    string currentStateSet = queue.Dequeue();
    Dictionary<string, List<string>> currentTransitions = dfaTransitions[currentStateSet];

    // 对每个符号进行处理
    foreach (string symbol in symbols)
    {
        // 计算当前状态集合在该符号下的转移
        List<string> nextStateSet = new List<string>();
        foreach (string state in currentStateSet.Split(','))
        {
            if (transitions.ContainsKey(state) && transitions[state].ContainsKey(symbol))
            {
                foreach (string nextState in transitions[state][symbol])
                {
                    nextStateSet = nextStateSet.Union(EpsilonClosure(new List<string> { nextState }, transitions)).ToList();
                }
            }
        }

        // 如果转移结果为空，则跳过该符号
        if (nextStateSet.Count == 0)
        {
            continue;
        }

        // 将转移结果加入DFA的状态集中
        string nextStateSetName = "{" + string.Join(",", nextStateSet) + "}";
        if (!dfaTransitions.ContainsKey(currentStateSet))
        {
            dfaTransitions[currentStateSet] = new Dictionary<string, List<string>>();
        }
        currentTransitions[symbol] = new List<string> { nextStateSetName };

        // 如果新的状态集合还未被处理，则加入队列中
        if (!dfaTransitions.ContainsKey(nextStateSetName))
        {
            queue.Enqueue(nextStateSetName);
            dfaTransitions[nextStateSetName] = new Dictionary<string, List<string>>();
        }
    }
}

// 生成DFA的结束符集合
List<string> endStates = new List<string>();
foreach (string stateSet in dfaTransitions.Keys)
{
    if (stateSet.Split(',').Intersect(endSym.Split(',')).Any())
    {
        endStates.Add(stateSet);
    }
}

// 将DFA的状态转移表转换为ListView中的数据
listView2.Items.Clear();
foreach (string stateSet in dfaTransitions.Keys)
{
    foreach (string symbol in dfaTransitions[stateSet].Keys)
    {
        string toStateSet = dfaTransitions[stateSet][symbol][0];
        ListViewItem item = new ListViewItem(new[] { stateSet, symbol, toStateSet });
        listView2.Items.Add(item);
    }
}

// 将DFA的开始符和结束符集合显示在界面上
label5.Text = "初始状态集:" + "{" + string.Join(",", startStates) + "}";
label7.Text = "终止状态集:";
for (int i = 0; i < endStates.Count; i++)
{
    label7.Text += endStates[i];
    if (i < endStates.Count - 1)
    {
        label7.Text += ";";
    }
}

// 启用DFA到MFA的转换按钮
button9.Enabled = true;

}

// 子集构造算法实现DFA到MFA的转换 private void button9_Click(object sender, EventArgs e) { // 获取DFA的开始符、结束符和状态转移表 string startState = startSymbol; string[] endStates = endSymbol.Split(';'); Dictionary<string, Dictionary<string, string>> transitions = new Dictionary<string, Dictionary<string, string>>(); for (int i = 0; i < listView2.Items.Count; i++) { string fromState = listView2.Items[i].SubItems[0].Text; string symbol = listView2.Items[i].SubItems[1].Text; string toState = listView2.Items[i].SubItems[2].Text; if (!transitions.ContainsKey(fromState)) { transitions[fromState] = new Dictionary<string, string>(); } transitions[fromState][symbol] = toState; }

// 初始化MFA的开始符和状态转移表
List<string> startStates = EpsilonClosure(new List<string> { startState }, transitions);
Dictionary<string, Dictionary<string, List<string>>> mfaTransitions = new Dictionary<string, Dictionary<string, List<string>>>();
mfaTransitions["{" + string.Join(",", startStates) + "}"] = new Dictionary<string, List<string>>();

// 对MFA的状态集进行迭代
Queue<string> queue = new Queue<string>();
queue.Enqueue("{" + string.Join(",", startStates) + "}");
while (queue.Count > 0)
{
    string currentStateSet = queue.Dequeue();
    Dictionary<string, List<string>> currentTransitions = mfaTransitions[currentStateSet];

    // 对每个符号进行处理
    foreach (string symbol in symbolSet)
    {
        // 计算当前状态集合在该符号下的转移
        List<string> nextStateSet = new List<string>();
        foreach (string state in currentStateSet.Split(','))
        {
            if (transitions.ContainsKey(state) && transitions[state].ContainsKey(symbol))
            {
                nextStateSet.Add(transitions[state][symbol]);
            }
        }

        // 如果转移结果为空，则跳过该符号
        if (nextStateSet.Count == 0)
        {
            continue;
        }

        // 将转移结果加入MFA的状态集中
        string nextStateSetName = "{" + string.Join(",", nextStateSet) + "}";
        if (!mfaTransitions.ContainsKey(currentStateSet))
        {
            mfaTransitions[currentStateSet] = new Dictionary<string, List<string>>();
        }
        currentTransitions[symbol] = new List<string> { nextStateSetName };

        // 如果新的状态集合还未被处理，则加入队列中
        if (!mfaTransitions.ContainsKey(nextStateSetName))
        {
            queue.Enqueue(nextStateSetName);
            mfaTransitions[nextStateSetName] = new Dictionary<string, List<string>>();
        }
    }
}

// 生成MFA的结束符集合
List<string> mfaEndStates = new List<string>();