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

/* 子集构造算法实现NFA到DFA的转换 */ private void button7_Click(object sender, EventArgs e) { // 初始化DFA的状态集合和转移表 List dfaStates = new List(); Dictionary<string, Dictionary<string, string>> dfaTransitions = new Dictionary<string, Dictionary<string, string>>();

// 获取NFA的状态集合和转移表
List<string> nfaStates = new List<string>();
Dictionary<string, Dictionary<string, List<string>>> nfaTransitions = new Dictionary<string, Dictionary<string, List<string>>>();
foreach (ListViewItem item in listView1.Items)
{
    string startState = item.SubItems[0].Text;
    string symbol = item.SubItems[1].Text;
    string endState = item.SubItems[2].Text;

    if (!nfaStates.Contains(startState))
    {
        nfaStates.Add(startState);
    }
    if (!nfaStates.Contains(endState))
    {
        nfaStates.Add(endState);
    }

    if (!nfaTransitions.ContainsKey(startState))
    {
        nfaTransitions[startState] = new Dictionary<string, List<string>>();
    }
    if (!nfaTransitions[startState].ContainsKey(symbol))
    {
        nfaTransitions[startState][symbol] = new List<string>();
    }
    nfaTransitions[startState][symbol].Add(endState);
}

// 初始化DFA的初始状态
List<string> startStates = new List<string>();
startStates.Add(startSymbol);
string dfaStartState = string.Join(',', startStates);
dfaStates.Add(dfaStartState);

// 初始化DFA的终止状态
List<string> dfaEndStates = new List<string>();

// 开始进行子集构造算法
Queue<string> queue = new Queue<string>();
queue.Enqueue(dfaStartState);

while (queue.Count > 0)
{
    string currentState = queue.Dequeue();
    Dictionary<string, string> currentTransitions = new Dictionary<string, string>();

    // 遍历当前状态集合中的每个状态
    string[] currentStates = currentState.Split(',');
    foreach (string state in currentStates)
    {
        // 遍历当前状态的每个转移
        if (nfaTransitions.ContainsKey(state))
        {
            foreach (string symbol in nfaTransitions[state].Keys)
            {
                // 将当前状态的转移加入到currentTransitions中
                List<string> endStates = nfaTransitions[state][symbol];
                foreach (string endState in endStates)
                {
                    if (!currentTransitions.ContainsKey(symbol))
                    {
                        currentTransitions[symbol] = endState;
                    }
                    else
                    {
                        currentTransitions[symbol] += ',' + endState;
                    }
                }
            }
        }
    }

    // 遍历currentTransitions中的每个转移
    foreach (string symbol in currentTransitions.Keys)
    {
        string endState = currentTransitions[symbol];
        string[] endStates = endState.Split(',');
        string newState = string.Join(',', endStates);

        // 如果新状态不在dfaStates中，将其加入到dfaStates中，并将其加入到队列中
        if (!dfaStates.Contains(newState))
        {
            dfaStates.Add(newState);
            queue.Enqueue(newState);
        }

        // 将当前状态和新状态的转移加入到dfaTransitions中
        if (!dfaTransitions.ContainsKey(currentState))
        {
            dfaTransitions[currentState] = new Dictionary<string, string>();
        }
        dfaTransitions[currentState][symbol] = newState;
    }

    // 如果当前状态集合中包含NFA的终止状态，将其加入到DFA的终止状态集合中
    foreach (string state in currentStates)
    {
        if (endStates.Contains(state) && !dfaEndStates.Contains(currentState))
        {
            dfaEndStates.Add(currentState);
        }
    }
}

// 将DFA的状态集合和转移表显示在listView2中
listView2.Items.Clear();
foreach (string state in dfaStates)
{
    foreach (string symbol in symbolSet)
    {
        if (dfaTransitions.ContainsKey(state) && dfaTransitions[state].ContainsKey(symbol))
        {
            string toState = dfaTransitions[state][symbol];
            ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
            listView2.Items.Add(item);
        }
    }
}

// 更新DFA的初始状态和终止状态
startSymbol = dfaStartState;
endStates = dfaEndStates.ToArray();

label5.Text = '初始状态集:' + startSymbol;
label7.Text = '终止状态集:';
for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
     label7.Text = label7.Text + endStates[i] + ';';

button6.Enabled = true;
button8.Enabled = true;

}

/* DFA到MFA的转换 */ private void button9_Click(object sender, EventArgs e) { // 初始化MFA的状态集合和转移表 List mfaStates = new List(); Dictionary<string, Dictionary<string, string>> mfaTransitions = new Dictionary<string, Dictionary<string, string>>();

// 获取DFA的状态集合和转移表
List<string> dfaStates = new List<string>();
Dictionary<string, Dictionary<string, string>> dfaTransitions = new Dictionary<string, Dictionary<string, string>>();
foreach (ListViewItem item in listView2.Items)
{
    string startState = item.SubItems[0].Text;
    string symbol = item.SubItems[1].Text;
    string endState = item.SubItems[2].Text;

    if (!dfaStates.Contains(startState))
    {
        dfaStates.Add(startState);
    }
    if (!dfaStates.Contains(endState))
    {
        dfaStates.Add(endState);
    }

    if (!dfaTransitions.ContainsKey(startState))
    {
        dfaTransitions[startState] = new Dictionary<string, string>();
    }
    dfaTransitions[startState][symbol] = endState;
}

// 初始化MFA的初始状态
List<string> startStates = new List<string>();
startStates.Add(startSymbol);
string mfaStartState = string.Join(',', startStates);
mfaStates.Add(mfaStartState);

// 初始化MFA的终止状态
List<string> mfaEndStates = new List<string>();

// 开始进行MFA的转换
Queue<string> queue = new Queue<string>();
queue.Enqueue(mfaStartState);

while (queue.Count > 0)
{
    string currentState = queue.Dequeue();
    Dictionary<string, string> currentTransitions = new Dictionary<string, string>();

    // 遍历当前状态集合中的每个状态
    string[] currentStates = currentState.Split(',');
    foreach (string state in currentStates)
    {
        // 遍历当前状态的每个转移
        if (dfaTransitions.ContainsKey(state))
        {
            foreach (string symbol in dfaTransitions[state].Keys)
            {
                string endState = dfaTransitions[state][symbol];
                if (!currentTransitions.ContainsKey(symbol))
                {
                    currentTransitions[symbol] = endState;
                }
                else
                {
                    currentTransitions[symbol] += ',' + endState;
                }
            }
        }
    }

    // 遍历currentTransitions中的每个转移
    foreach (string symbol in currentTransitions.Keys)
    {
        string endState = currentTransitions[symbol];
        string[] endStates = endState.Split(',');
        string newState = string.Join(',', endStates);

        // 如果新状态不在mfaStates中，将其加入到mfaStates中，并将其加入到队列中
        if (!mfaStates.Contains(newState))
        {
            mfaStates.Add(newState);
            queue.Enqueue(newState);
        }

        // 将当前状态和新状态的转移加入到mfaTransitions中
        if (!mfaTransitions.ContainsKey(currentState))
        {
            mfaTransitions[currentState] = new Dictionary<string, string>();
        }
        mfaTransitions[currentState][symbol] = newState;
    }

    // 如果当前状态集合中包含DFA的终止状态，将其加入到MFA的终止状态集合中
    foreach (string state in currentStates)
    {
        if (endStates.Contains(state) && !mfaEndStates.Contains(currentState))
        {
            mfaEndStates.Add(currentState);
        }
    }
}

// 将MFA的状态集合和转移表显示在listView3中
listView3.Items.Clear();
foreach (string state in mfaStates)
{
    foreach (string symbol in symbolSet)
    {
        if (mfaTransitions.ContainsKey(state) && mfaTransitions[state].ContainsKey(symbol))
        {
            string toState = mfaTransitions[state][symbol];
            ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
            listView3.Items.Add(item);
        }
    }
}

// 更新MFA的初始状态和终止状态
startSymbol = mfaStartState;
endStates = mfaEndStates.ToArray();

label9.Text = '初始状态集:' + startSymbol;
label11.Text = '终止状态集:';
for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
     label11.Text = label11.Text + endStates[i] + ';';

button10.Enabled = true;
button12.Enabled = true;

}