NFA 转 DFA：使用子集构造法和 VSC# 代码实现

private void button7_Click(object sender, EventArgs e) { // 获取开始符和终结符 string startSym = '开始符:' + startSymbol + ';'; string endSym = '终结符:'; for (int i = 0; i < endStates.Length - 1; i++) endSym = endSym + endStates[i] + ';';

// 构造 NFA 的状态集合
List<string> nfaStates = new List<string>();
for (int i = 0; i < listView1.Items.Count; i++)
{
    string startState = listView1.Items[i].SubItems[0].Text;
    string symbol = listView1.Items[i].SubItems[1].Text;
    string endState = listView1.Items[i].SubItems[2].Text;

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

// 构造 DFA 的状态集合
List<string> dfaStates = new List<string>();
List<string> unmarkedStates = new List<string>();
dfaStates.Add(startSymbol);
unmarkedStates.Add(startSymbol);

// 构造 DFA 的符号集合
List<string> dfaSymbols = new List<string>();
foreach (string symbol in symbolSet)
{
    dfaSymbols.Add(symbol);
}

// 构造 DFA 的转移函数
Dictionary<string, Dictionary<string, string>> dfaTransitions = new Dictionary<string, Dictionary<string, string>>();
while (unmarkedStates.Count > 0)
{
    string dfaState = unmarkedStates[0];
    unmarkedStates.RemoveAt(0);

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

    foreach (string symbol in dfaSymbols)
    {
        List<string> nfaDestStates = new List<string>();
        foreach (string nfaState in dfaState.Split(';'))
        {
            foreach (ListViewItem item in listView1.Items)
            {
                if (item.SubItems[0].Text == nfaState && item.SubItems[1].Text == symbol)
                {
                    nfaDestStates.Add(item.SubItems[2].Text);
                }
            }
        }

        if (nfaDestStates.Count > 0)
        {
            string nfaDestStatesStr = string.Join(';', nfaDestStates.OrderBy(x => x));
            if (!dfaStates.Contains(nfaDestStatesStr))
            {
                dfaStates.Add(nfaDestStatesStr);
                unmarkedStates.Add(nfaDestStatesStr);
            }
            dfaTransitions[dfaState][symbol] = nfaDestStatesStr;
        }
    }
}

// 构造 DFA 的终止状态集合
List<string> dfaEndStates = new List<string>();
foreach (string dfaState in dfaStates)
{
    foreach (string endState in endStates)
    {
        if (dfaState.Split(';').Contains(endState))
        {
            dfaEndStates.Add(dfaState);
            break;
        }
    }
}

// 初始化 DFA 文件内容
string dfaContent = '开始符:' + startSymbol + '\n';
dfaContent += '终结符:' + string.Join(';', dfaEndStates.OrderBy(x => x)) + '\n';
dfaContent += '状态数:' + dfaStates.Count + '\n';
dfaContent += '符号集:' + string.Join(';', dfaSymbols) + '\n';

// 遍历 DFA 的转移函数，生成 DFA 文件内容
foreach (string state in dfaTransitions.Keys)
{
    foreach (string symbol in dfaTransitions[state].Keys)
    {
        string toState = dfaTransitions[state][symbol];
        dfaContent += state + '\t' + symbol + '\t' + toState + '\n';
    }
}

// 保存 DFA 文件
SaveFileDialog saveFileDialog = new SaveFileDialog();
saveFileDialog.Filter = 'DFA 文件 (*.dfa)|*.dfa';
saveFileDialog.FileName = 'DFA.txt';
if (saveFileDialog.ShowDialog() == DialogResult.OK)
{
    string fileName = saveFileDialog.FileName;
    File.WriteAllText(fileName, dfaContent, Encoding.UTF8);
}

}