C# 使用NFA数据生成DFA文件数据 - VS软件实现

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); }

// 获取符号集
List<string> symbolSet = new List<string>();
foreach (string symbol in lines[2].Split(','))
{
    symbolSet.Add(symbol);
}

// 构建DFA数据
List<string[]> dfaData = new List<string[]>();
List<string> dfaStates = new List<string>();
List<string> dfaEndStates = new List<string>();
List<string> dfaSymbols = new List<string>();
string startState = lines[0];
string endStates = lines[1];

// 初始化DFA状态集
List<string> nfaStartStates = new List<string>();
nfaStartStates.Add(startState);
List<string> startClosure = EpsilonClosure(nfaStartStates, nfaData);
string startDfaState = string.Join(',', startClosure);
dfaStates.Add(startDfaState);
if (startClosure.Contains(endStates))
{
    dfaEndStates.Add(startDfaState);
}

// 构建DFA数据
Queue<string> queue = new Queue<string>();
queue.Enqueue(startDfaState);
while (queue.Count > 0)
{
    string currentState = queue.Dequeue();
    foreach (string symbol in symbolSet)
    {
        List<string> nfaStates = new List<string>();
        foreach (string state in currentState.Split(','))
        {
            List<string> transitions = GetTransitions(state, symbol, nfaData);
            nfaStates = nfaStates.Union(transitions).ToList();
        }
        List<string> closure = EpsilonClosure(nfaStates, nfaData);
        if (closure.Count > 0)
        {
            string nextState = string.Join(',', closure);
            if (!dfaStates.Contains(nextState))
            {
                dfaStates.Add(nextState);
                if (closure.Contains(endStates))
                {
                    dfaEndStates.Add(nextState);
                }
                queue.Enqueue(nextState);
            }
            string[] dfaRow = new string[3];
            dfaRow[0] = currentState;
            dfaRow[1] = symbol;
            dfaRow[2] = nextState;
            dfaData.Add(dfaRow);
            if (!dfaSymbols.Contains(symbol))
            {
                dfaSymbols.Add(symbol);
            }
        }
    }
}

// 显示DFA数据
listView2.Columns.Add('起始状态');
listView2.Columns.Add('接受符号');
listView2.Columns.Add('到达状态');
foreach (string dfaState in dfaStates)
{
    ListViewItem item = new ListViewItem(dfaState);
    item.SubItems.Add('');
    item.SubItems.Add('');
    listView2.Items.Add(item);
}
foreach (string[] row in dfaData)
{
    int index = dfaStates.IndexOf(row[0]);
    ListViewItem item = listView2.Items[index];
    item.SubItems[1].Text += row[1] + ',';
    item.SubItems[2].Text += row[2] + ',';
}
foreach (ListViewItem item in listView2.Items)
{
    item.SubItems[1].Text = item.SubItems[1].Text.TrimEnd(',');
    item.SubItems[2].Text = item.SubItems[2].Text.TrimEnd(',');
}
string dfaStartState = dfaStates[0];
string dfaEndStateStr = string.Join(';', dfaEndStates);
string dfaSymbolStr = string.Join(';', dfaSymbols);
string dfaDataStr = '开始符:' + dfaStartState + ';;\n';
dfaDataStr += '终结符:' + dfaEndStateStr + ';;\n';
foreach (string[] row in dfaData)
{
    dfaDataStr += row[0] + '\t' + row[1] + '\t' + row[2] + '\n';
}
richTextBox1.Text = dfaDataStr;

}

// 获取某个状态通过某个符号可以到达的状态集合 private List GetTransitions(string state, string symbol, List<string[]> nfaData) { List transitions = new List(); foreach (string[] row in nfaData) { if (row[0] == state && row[1] == symbol) { transitions.Add(row[2]); } } return transitions; }

// 获取某个状态通过ε可以到达的状态集合 private List EpsilonClosure(List states, List<string[]> nfaData) { List closure = new List(); Queue queue = new Queue(); foreach (string state in states) { closure.Add(state); queue.Enqueue(state); } while (queue.Count > 0) { string currentState = queue.Dequeue(); List transitions = GetTransitions(currentState, '#', nfaData); foreach (string nextState in transitions) { if (!closure.Contains(nextState)) { closure.Add(nextState); queue.Enqueue(nextState); } } } return closure;