NFA到DFA，DFA到MFA转换算法实现 - C# 代码示例

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

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

// 获取NFA中的所有符号集
List<string> symbolList = new List<string>();
for (int i = 0; i < listView1.Items.Count; i++)
{
    string symbol = listView1.Items[i].SubItems[1].Text;
    if (!symbolList.Contains(symbol))
    {
        symbolList.Add(symbol);
    }
}

// 计算NFA的ε闭包
List<string> eClosure = new List<string>();
for (int i = 0; i < nfaStates.Count; i++)
{
    eClosure.Add(nfaStates[i]);
}
for (int i = 0; i < eClosure.Count; i++)
{
    string state = eClosure[i];
    for (int j = 0; j < listView1.Items.Count; j++)
    {
        string startState = listView1.Items[j].SubItems[0].Text;
        string symbol = listView1.Items[j].SubItems[1].Text;
        string endState = listView1.Items[j].SubItems[2].Text;
        if (startState == state && symbol == 'ε' && !eClosure.Contains(endState))
        {
            eClosure.Add(endState);
        }
    }
}

// 将NFA的ε闭包作为DFA的一个状态
dfaStates.Add(eClosure);

// 循环计算DFA的状态集合
for (int i = 0; i < dfaStates.Count; i++)
{
    List<string> dfaState = dfaStates[i];
    for (int j = 0; j < symbolList.Count; j++)
    {
        string symbol = symbolList[j];
        List<string> nextState = new List<string>();
        for (int k = 0; k < dfaState.Count; k++)
        {
            string state = dfaState[k];
            for (int l = 0; l < listView1.Items.Count; l++)
            {
                string startState = listView1.Items[l].SubItems[0].Text;
                string inputSymbol = listView1.Items[l].SubItems[1].Text;
                string endState = listView1.Items[l].SubItems[2].Text;
                if (startState == state && inputSymbol == symbol && !nextState.Contains(endState))
                {
                    nextState.Add(endState);
                }
            }
        }
        // 计算新状态的ε闭包
        List<string> newDfaState = new List<string>();
        for (int k = 0; k < nextState.Count; k++)
        {
            newDfaState.Add(nextState[k]);
        }
        for (int k = 0; k < newDfaState.Count; k++)
        {
            string state = newDfaState[k];
            for (int l = 0; l < listView1.Items.Count; l++)
            {
                string startState = listView1.Items[l].SubItems[0].Text;
                string inputSymbol = listView1.Items[l].SubItems[1].Text;
                string endState = listView1.Items[l].SubItems[2].Text;
                if (startState == state && inputSymbol == 'ε' && !newDfaState.Contains(endState))
                {
                    newDfaState.Add(endState);
                }
            }
        }
        // 将新状态加入DFA状态集合
        if (newDfaState.Count > 0 && !dfaStates.Contains(newDfaState))
        {
            dfaStates.Add(newDfaState);
        }
        // 将新状态和转移加入DFA转移表
        if (newDfaState.Count > 0)
        {
            string fromState = string.Join(',', dfaState);
            string toState = string.Join(',', newDfaState);
            ListViewItem item = new ListViewItem(new[] { fromState, symbol, toState });
            listView2.Items.Add(item);
        }
    }
}
button8.Enabled = true;

}

// 子集构造算法实现DFA到MFA的转换 private void button9_Click(object sender, EventArgs e) { // 初始化MFA状态集合 List<List> mfaStates = new List<List>();

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

// 获取DFA中的所有符号集
List<string> symbolList = new List<string>();
for (int i = 0; i < listView2.Items.Count; i++)
{
    string symbol = listView2.Items[i].SubItems[1].Text;
    if (!symbolList.Contains(symbol))
    {
        symbolList.Add(symbol);
    }
}

// 将DFA状态集合中的每个状态拆分成若干个等价类
List<List<string>> dfaClasses = new List<List<string>>();
for (int i = 0; i < dfaStates.Count; i++)
{
    string state = dfaStates[i];
    bool found = false;
    for (int j = 0; j < dfaClasses.Count; j++)
    {
        List<string> dfaClass = dfaClasses[j];
        string firstState = dfaClass[0];
        bool equivalent = true;
        for (int k = 0; k < symbolList.Count; k++)
        {
            string symbol = symbolList[k];
            string nextState1 = '';
            string nextState2 = '';
            for (int l = 0; l < listView2.Items.Count; l++)
            {
                string fromState = listView2.Items[l].SubItems[0].Text;
                string inputSymbol = listView2.Items[l].SubItems[1].Text;
                string toState = listView2.Items[l].SubItems[2].Text;
                if (fromState == firstState && inputSymbol == symbol)
                {
                    nextState1 = toState;
                }
                if (fromState == state && inputSymbol == symbol)
                {
                    nextState2 = toState;
                }
            }
            bool found1 = false;
            bool found2 = false;
            for (int l = 0; l < dfaClass.Count; l++)
            {
                string s = dfaClass[l];
                if (s == nextState1)
                {
                    found1 = true;
                }
                if (s == nextState2)
                {
                    found2 = true;
                }
            }
            if (found1 != found2)
            {
                equivalent = false;
                break;
            }
        }
        if (equivalent)
        {
            dfaClass.Add(state);
            found = true;
            break;
        }
    }
    if (!found)
    {
        List<string> dfaClass = new List<string>();
        dfaClass.Add(state);
        dfaClasses.Add(dfaClass);
    }
}

// 将等价类作为MFA的一个状态
for (int i = 0; i < dfaClasses.Count; i++)
{
    mfaStates.Add(dfaClasses[i]);
}

// 循环计算MFA的状态集合和转移表
for (int i = 0; i < mfaStates.Count; i++)
{
    List<string> mfa