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] + ';';

// 构造状态转移表
List<string> dfaStates = new List<string>();
Dictionary<string, Dictionary<string, string>> dfaTransitions = new Dictionary<string, Dictionary<string, string>>();
Dictionary<string, HashSet<string>> nfaStates = new Dictionary<string, HashSet<string>>();
nfaStates[startSymbol] = new HashSet<string>();
nfaStates[startSymbol].Add('0');
dfaStates.Add(startSymbol);
while (true)
{
    bool newStatesAdded = false;
    for (int i = 0; i < dfaStates.Count; i++)
    {
        string dfaState = dfaStates[i];
        if (!dfaTransitions.ContainsKey(dfaState))
        {
            dfaTransitions[dfaState] = new Dictionary<string, string>();
        }
        foreach (string symbol in symbolSet)
        {
            HashSet<string> nfaNextStates = new HashSet<string>();
            foreach (string state in nfaStates[dfaState])
            {
                foreach (ListViewItem item in listView1.Items)
                {
                    if (item.SubItems[0].Text == state && item.SubItems[1].Text == symbol)
                    {
                        nfaNextStates.Add(item.SubItems[2].Text);
                    }
                }
            }
            string nfaNextStateString = string.Join(',', nfaNextStates.OrderBy(x => x));
            if (!string.IsNullOrEmpty(nfaNextStateString))
            {
                if (!dfaStates.Contains(nfaNextStateString))
                {
                    dfaStates.Add(nfaNextStateString);
                    newStatesAdded = true;
                }
                dfaTransitions[dfaState][symbol] = nfaNextStateString;
            }
        }
    }
    if (!newStatesAdded)
    {
        break;
    }
    nfaStates = new Dictionary<string, HashSet<string>>();
    foreach (string dfaState in dfaStates)
    {
        string[] nfaStateStrings = dfaState.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries);
        HashSet<string> nfaStatesSet = new HashSet<string>();
        foreach (string nfaStateString in nfaStateStrings)
        {
            nfaStatesSet.Add(nfaStateString);
        }
        nfaStates[dfaState] = nfaStatesSet;
    }
}

// 生成DFA文件内容
string dfaContent = startSym + '\n' + endSym + '\n';
dfaContent += '最大状态数:' + dfaStates.Count + ';\n';
dfaContent += '符号集:' + string.Join(';', symbolSet) + ';\n';
foreach (string dfaState in dfaStates)
{
    string stateType = '中间状态';
    if (dfaState.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries).Intersect(endStates).Any())
    {
        stateType = '终止状态';
    }
    if (dfaState == startSymbol)
    {
        stateType = '初始状态';
    }
    dfaContent += dfaState + '\t' + stateType + '\n';
}
foreach (string dfaState in dfaStates)
{
    foreach (string symbol in symbolSet)
    {
        if (dfaTransitions.ContainsKey(dfaState) && dfaTransitions[dfaState].ContainsKey(symbol))
        {
            string nextState = dfaTransitions[dfaState][symbol];
            dfaContent += dfaState + '\t' + symbol + '\t' + nextState + '\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);
}

}