C#实现NFA到DFA，DFA到MFA的转换算法 - 子集构造算法

// 子集构造算法实现NFA到DFA转换 private void button7_Click(object sender, EventArgs e) { // 初始化DFA Dictionary<string, List> dfa = new Dictionary<string, List>(); List startState = new List(); startState.Add(startSymbol); dfa['0'] = startState;

// 初始化状态集合
List<List<string>> stateSet = new List<List<string>>();
stateSet.Add(startState);

// 初始化符号集合
List<string> symbolList = new List<string>(symbolSet);
symbolList.Remove('&');

// 子集构造算法
int index = 0;
while (index < stateSet.Count)
{
    List<string> currentState = stateSet[index];
    foreach (string symbol in symbolList)
    {
        List<string> nextState = new List<string>();
        foreach (string state in currentState)
        {
            foreach (ListViewItem item in listView1.Items)
            {
                if (item.SubItems[0].Text == state && item.SubItems[1].Text == symbol)
                {
                    if (!nextState.Contains(item.SubItems[2].Text))
                        nextState.Add(item.SubItems[2].Text);
                }
            }
        }
        if (nextState.Count > 0)
        {
            if (!stateSet.Contains(nextState))
            {
                stateSet.Add(nextState);
                dfa[stateSet.IndexOf(currentState).ToString()][symbol] = stateSet.IndexOf(nextState).ToString();
                List<string> endState = endSymbol.Split(',').ToList();
                foreach (string s in nextState)
                {
                    if (endState.Contains(s))
                    {
                        if (!endStates.Contains(stateSet.IndexOf(currentState).ToString()))
                        {
                            endStates += stateSet.IndexOf(currentState).ToString() + ';';
                        }
                    }
                }
            }
            else
            {
                dfa[stateSet.IndexOf(currentState).ToString()][symbol] = stateSet.IndexOf(nextState).ToString();
            }
        }
    }
    index++;
}

// 在listView2中显示DFA
listView2.Items.Clear();
for (int i = 0; i < stateSet.Count; i++)
{
    foreach (string symbol in symbolList)
    {
        if (dfa.ContainsKey(i.ToString()) && dfa[i.ToString()].ContainsKey(symbol))
        {
            string nextState = dfa[i.ToString()][symbol];
            ListViewItem item = new ListViewItem(i.ToString());
            item.SubItems.Add(symbol);
            item.SubItems.Add(nextState);
            listView2.Items.Add(item);
        }
    }
}

// 显示终止状态集合
label7.Text = '终止状态集:';
for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
    label7.Text = label7.Text + endStates[i] + ';';

// 设置按钮状态
button6.Enabled = true;
button7.Enabled = false;
button8.Enabled = true;

}

// 子集构造算法实现DFA到MFA转换 private void button9_Click(object sender, EventArgs e) { // 初始化MFA Dictionary<string, List> mfa = new Dictionary<string, List>(); List startState = new List(); startState.Add(startSymbol); mfa['0'] = startState;

// 初始化状态集合
List<List<string>> stateSet = new List<List<string>>();
stateSet.Add(startState);

// 初始化符号集合
List<string> symbolList = new List<string>(symbolSet);
symbolList.Remove('&');

// 子集构造算法
int index = 0;
while (index < stateSet.Count)
{
    List<string> currentState = stateSet[index];
    Dictionary<string, List<string>> partition = new Dictionary<string, List<string>>();
    foreach (string symbol in symbolList)
    {
        foreach (string state in currentState)
        {
            foreach (ListViewItem item in listView2.Items)
            {
                if (item.SubItems[0].Text == state && item.SubItems[1].Text == symbol)
                {
                    string nextState = item.SubItems[2].Text;
                    if (!partition.ContainsKey(nextState))
                        partition[nextState] = new List<string>();
                    partition[nextState].Add(state);
                }
            }
        }
    }
    foreach (List<string> subset in partition.Values)
    {
        if (!stateSet.Contains(subset))
        {
            stateSet.Add(subset);
            mfa[stateSet.IndexOf(currentState).ToString()][symbolList.IndexOf(symbol)] = stateSet.IndexOf(subset).ToString();
        }
        else
        {
            mfa[stateSet.IndexOf(currentState).ToString()][symbolList.IndexOf(symbol)] = stateSet.IndexOf(subset).ToString();
        }
    }
    index++;
}

// 在listView3中显示MFA
listView3.Items.Clear();
for (int i = 0; i < stateSet.Count; i++)
{
    foreach (string symbol in symbolList)
    {
        if (mfa.ContainsKey(i.ToString()) && mfa[i.ToString()].ContainsKey(symbol))
        {
            string nextState = mfa[i.ToString()][symbolList.IndexOf(symbol)];
            ListViewItem item = new ListViewItem(i.ToString());
            item.SubItems.Add(symbol);
            item.SubItems.Add(nextState);
            listView3.Items.Add(item);
        }
    }
}

// 显示终止状态集合
label10.Text = '终止状态集:';
for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
{
    for (int j = 0; j < stateSet.Count; j++)
    {
        if (stateSet[j].Contains(endStates[i]))
        {
            if (!endStates.Contains(j.ToString()))
            {
                endStates += j.ToString() + ';';
            }
        }
    }
}
for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
    label10.Text = label10.Text + endStates[i] + ';';

// 设置按钮状态
button7.Enabled = true;
button9.Enabled = false;
button10.Enabled = true;

}