NFA 到 DFA 到 MFA 的转换：子集构造算法实现

// 子集构造算法实现NFA到DFA的转换 private void button7_Click(object sender, EventArgs e) { // 初始化DFA的开始符和终结符 string dfaStartSymbol = startSymbol; string dfaEndSymbol = "";

// 初始化DFA的状态集合
List<string> dfaStates = new List<string>();
dfaStates.Add(dfaStartSymbol);

// 初始化DFA的符号集合
List<string> dfaSymbolSet = new List<string>();
foreach (string symbol in symbolSet)
{
    dfaSymbolSet.Add(symbol);
}

// 初始化DFA的转换表
Dictionary<string, Dictionary<string, string>> dfaTransitions = new Dictionary<string, Dictionary<string, string>>();

// 初始化NFA的状态集合
List<string> nfaStates = new List<string>();
nfaStates.Add(startSymbol);

// 初始化NFA的状态栈
Stack<List<string>> stateStack = new Stack<List<string>>();
stateStack.Push(nfaStates);

// 开始子集构造算法
while (stateStack.Count > 0)
{
    // 取出一个状态集合
    List<string> currState = stateStack.Pop();

    // 遍历所有的符号集合
    foreach (string symbol in dfaSymbolSet)
    {
        // 计算当前状态集合在该符号下的转换状态集合
        List<string> nextState = new List<string>();
        foreach (string state in currState)
        {
            // 查找该状态在NFA中对应的转换状态
            foreach (ListViewItem item in listView1.Items)
            {
                if (item.SubItems[0].Text == state && item.SubItems[1].Text == symbol)
                {
                    string next = item.SubItems[2].Text;
                    if (!nextState.Contains(next))
                    {
                        nextState.Add(next);
                    }
                }
            }
        }

        // 如果该状态集合在该符号下无转换状态，则跳过
        if (nextState.Count == 0)
        {
            continue;
        }

        // 如果该状态集合在该符号下有转换状态，则加入DFA状态集合
        string nextStateStr = string.Join(",", nextState);
        if (!dfaStates.Contains(nextStateStr))
        {
            dfaStates.Add(nextStateStr);
            stateStack.Push(nextState);
        }

        // 更新DFA转换表
        string currStateStr = string.Join(",", currState);
        if (!dfaTransitions.ContainsKey(currStateStr))
        {
            dfaTransitions[currStateStr] = new Dictionary<string, string>();
        }
        dfaTransitions[currStateStr][symbol] = nextStateStr;
    }
}

// 更新DFA的终结符
foreach (string state in dfaStates)
{
    string[] stateArr = state.Split(',');
    foreach (string s in stateArr)
    {
        if (endSymbol.Contains(s) && !dfaEndSymbol.Contains(state))
        {
            dfaEndSymbol += state + ";";
            break;
        }
    }
}

// 清空DFA转换表
listView2.Items.Clear();

// 添加DFA转换表内容
foreach (string state in dfaTransitions.Keys)
{
    Dictionary<string, string> transition = dfaTransitions[state];
    foreach (string symbol in transition.Keys)
    {
        string nextState = transition[symbol];
        ListViewItem item = new ListViewItem(new string[] { state, symbol, nextState });
        listView2.Items.Add(item);
    }
}

// 更新DFA的开始符和终结符
label5.Text = "初始状态集:" + dfaStartSymbol;
label7.Text = "终止状态集:" + dfaEndSymbol;

// 更新按钮状态
button7.Enabled = false;
button9.Enabled = true;

}

// DFA到MFA的转换 private void button9_Click(object sender, EventArgs e) { // 初始化MFA的开始符和终结符 string mfaStartSymbol = startSymbol; string mfaEndSymbol = "";

// 初始化MFA的状态集合
List<string> mfaStates = new List<string>();
mfaStates.Add(mfaStartSymbol);

// 初始化MFA的符号集合
List<string> mfaSymbolSet = new List<string>();
foreach (string symbol in symbolSet)
{
    mfaSymbolSet.Add(symbol);
}

// 初始化MFA的转换表
Dictionary<string, Dictionary<string, string>> mfaTransitions = new Dictionary<string, Dictionary<string, string>>();

// 初始化DFA的状态集合
List<string> dfaStates = new List<string>();
foreach (ListViewItem item in listView2.Items)
{
    string fromState = item.SubItems[0].Text;
    string toState = item.SubItems[2].Text;
    if (!dfaStates.Contains(fromState))
    {
        dfaStates.Add(fromState);
    }
    if (!dfaStates.Contains(toState))
    {
        dfaStates.Add(toState);
    }
}

// 开始MFA转换算法
foreach (string state in dfaStates)
{
    // 初始化MFA的状态集合
    List<string> mfaState = new List<string>();
    mfaState.Add(state);

    // 初始化MFA的状态栈
    Stack<List<string>> stateStack = new Stack<List<string>>();
    stateStack.Push(mfaState);

    // 开始子集构造算法
    while (stateStack.Count > 0)
    {
        // 取出一个状态集合
        List<string> currState = stateStack.Pop();

        // 遍历所有的符号集合
        foreach (string symbol in mfaSymbolSet)
        {
            // 计算当前状态集合在该符号下的转换状态集合
            List<string> nextState = new List<string>();
            foreach (string s in currState)
            {
                // 查找该状态在DFA中对应的转换状态
                foreach (ListViewItem item in listView2.Items)
                {
                    if (item.SubItems[0].Text == s && item.SubItems[1].Text == symbol)
                    {
                        string next = item.SubItems[2].Text;
                        if (!nextState.Contains(next))
                        {
                            nextState.Add(next);
                        }
                    }
                }
            }

            // 如果该状态集合在该符号下无转换状态，则跳过
            if (nextState.Count == 0)
            {
                continue;
            }

            // 如果该状态集合在该符号下有转换状态，则加入MFA状态集合
            string nextStateStr = string.Join(",", nextState);
            if (!mfaStates.Contains(nextStateStr))
            {
                mfaStates.Add(nextStateStr);
                stateStack.Push(nextState);
            }

            // 更新MFA转换表
            string currStateStr = string.Join(",", currState);
            if (!mfaTransitions.ContainsKey(currStateStr))
            {
                mfaTransitions[currStateStr] = new Dictionary<string, string>();
            }
            mfaTransitions[currStateStr][symbol] = nextStateStr;
        }
    }
}

// 更新MFA的终结符
foreach (string state in mfaStates)
{
    string[] stateArr = state.Split(',');
    foreach (string s in stateArr)
    {
        if (dfaEndSymbol.Contains(s) && !mfaEndSymbol.Contains(state))