C#实现NFA数据生成DFA文件数据功能

private void button7_Click(object sender, EventArgs e) { // 获取NFA数据 List<string[]> nfaData = new List<string[]>(); foreach (ListViewItem item in listView1.Items) { string[] data = new string[3]; data[0] = item.SubItems[0].Text; data[1] = item.SubItems[1].Text; data[2] = item.SubItems[2].Text; nfaData.Add(data); }

// 获取符号集
string[] symbolSet = lines[2].Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries)[1].Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries);

// 构建NFA状态转移表
Dictionary<string, Dictionary<string, List<string>>> nfaTable = new Dictionary<string, Dictionary<string, List<string>>>();
foreach (string[] data in nfaData)
{
    string fromState = data[0];
    string symbol = data[1];
    string toState = data[2];

    if (!nfaTable.ContainsKey(fromState))
    {
        nfaTable.Add(fromState, new Dictionary<string, List<string>>());
    }

    if (!nfaTable[fromState].ContainsKey(symbol))
    {
        nfaTable[fromState].Add(symbol, new List<string>());
    }

    nfaTable[fromState][symbol].Add(toState);
}

// 构建DFA状态转移表
Dictionary<string, Dictionary<string, string>> dfaTable = new Dictionary<string, Dictionary<string, string>>();
List<string> unmarkedStates = new List<string>();
Dictionary<string, string> startState = new Dictionary<string, string>();
startState.Add(lines[0].Split(':')[1], "");
unmarkedStates.Add(DictionaryToString(startState));

while (unmarkedStates.Count > 0)
{
    string currentState = unmarkedStates[0];
    unmarkedStates.RemoveAt(0);

    if (!dfaTable.ContainsKey(currentState))
    {
        dfaTable.Add(currentState, new Dictionary<string, string>());
    }

    Dictionary<string, string> currentDfaState = StringToDictionary(currentState);
    foreach (string symbol in symbolSet)
    {
        List<string> nfaStates = new List<string>();
        foreach (KeyValuePair<string, string> entry in currentDfaState)
        {
            List<string> toStates;
            if (nfaTable.TryGetValue(entry.Key, out Dictionary<string, List<string>> symbolTable) && symbolTable.TryGetValue(symbol, out toStates))
            {
                nfaStates.AddRange(toStates);
            }
        }

        if (nfaStates.Count > 0)
        {
            Dictionary<string, string> dfaState = new Dictionary<string, string>();
            foreach (string nfaState in nfaStates)
            {
                foreach (KeyValuePair<string, List<string>> entry in nfaTable[nfaState])
                {
                    if (entry.Key != "#")
                    {
                        foreach (string toState in entry.Value)
                        {
                            if (!dfaState.ContainsKey(toState))
                            {
                                dfaState.Add(toState, "");
                            }
                        }
                    }
                }
            }

            string dfaStateStr = DictionaryToString(dfaState);
            dfaTable[currentState][symbol] = dfaStateStr;

            if (!dfaTable.ContainsKey(dfaStateStr))
            {
                unmarkedStates.Add(dfaStateStr);
            }
        }
    }
}

// 获取起始状态集和终止状态集
string startStateStr = DictionaryToString(startState);
string[] endStates = lines[1].Split(':')[1].Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);

// 显示DFA数据
listView2.Columns.Add("起始状态");
listView2.Columns.Add("接受符号");
listView2.Columns.Add("到达状态");

foreach (KeyValuePair<string, Dictionary<string, string>> entry in dfaTable)
{
    string fromState = entry.Key;
    Dictionary<string, string> symbolTable = entry.Value;

    foreach (string symbol in symbolSet)
    {
        string toState;
        if (symbolTable.TryGetValue(symbol, out toState))
        {
            ListViewItem item = new ListViewItem(fromState);
            item.SubItems.Add(symbol);
            item.SubItems.Add(toState);

            if (fromState == startStateStr)
            {
                item.BackColor = Color.LightGreen;
            }

            foreach (string endState in endStates)
            {
                if (toState.Contains(endState))
                {
                    item.BackColor = Color.LightBlue;
                    break;
                }
            }

            listView2.Items.Add(item);
        }
    }
}

}

private string DictionaryToString(Dictionary<string, string> dict) { List list = new List(); foreach (KeyValuePair<string, string> entry in dict) { list.Add(entry.Key); } list.Sort(); return string.Join(",", list.ToArray()); }

private Dictionary<string, string> StringToDictionary(string str) { Dictionary<string, string> dict = new Dictionary<string, string>(); string[] states = str.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries); foreach (string state in states) { dict.Add(state, ""); } return dict;