• 日期: 2025-03-07
  • 标签: 常规

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Reflection.Emit; using System.Security.Cryptography; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using System.Windows.Forms; using static System.Windows.Forms.VisualStyles.VisualStyleElement;

namespace byyljxfzxt { public partial class Form3 : Form { public Form3() { InitializeComponent(); }

    string[] lines;
    string startSymbol;
    string endSymbol;
    string[] symbolSet;
    string[] endStates;

    private void button5_Click(object sender, EventArgs e)
    {
        // 获取开始符和终结符
        string startSym = '开始符:' + startSymbol;
        string endSym = '终结符:' + endSymbol;

        // 初始化NFA文件内容
        string nfaContent = startSym + "\n" + endSym + "\n";

        // 遍历listView1中的数据，生成NFA文件内容
        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;

            // 拼接NFA文件内容
            nfaContent += startState + "\t" + symbol + "\t" + endState + "\n";
        }

        // 保存NFA文件
        SaveFileDialog saveFileDialog = new SaveFileDialog();
        saveFileDialog.Filter = "NFA文件(*.nfa)|*.nfa";
        saveFileDialog.FileName = "NFA.txt";
        if (saveFileDialog.ShowDialog() == DialogResult.OK)
        {
            string fileName = saveFileDialog.FileName;
            File.WriteAllText(fileName, nfaContent, Encoding.UTF8);
        }
    }

    private void label7_Click(object sender, EventArgs e)
    {

    }


    private void button3_Click(object sender, EventArgs e)
    {
        OpenFileDialog openFileDialog1 = new OpenFileDialog();
        openFileDialog1.Filter = "NFA Files|*.nfa";
        openFileDialog1.Title = "Select an NFA File";

        if (openFileDialog1.ShowDialog() == DialogResult.OK)
        {
            lines = File.ReadAllLines(openFileDialog1.FileName);
            startSymbol = lines[0].Substring(lines[0].IndexOf(':') + 1).Trim();
            endSymbol = lines[1].Substring(lines[1].IndexOf(':') + 1).Trim();
            symbolSet = lines[2].Substring(lines[2].IndexOf(':') + 1).Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);

            for (int i = 3; i < lines.Length; i++)
            {
                string[] tokens = lines[i].Split(new char[] { '\t' }, StringSplitOptions.RemoveEmptyEntries);
                string startState = tokens[0];
                string inputSymbol = tokens[1];
                string nextState = tokens[2];

                ListViewItem item = new ListViewItem(startState);
                item.SubItems.Add(inputSymbol);
                item.SubItems.Add(nextState);

                listView1.Items.Add(item);
            }
        }
        label3.Text = "初始状态集:" + startSymbol;
        label4.Text = "终止状态集:" + endSymbol;
        button6.Enabled = false;
        button7.Enabled = true;
    }

    private void button6_Click(object sender, EventArgs e)
    {
        OpenFileDialog openFileDialog1 = new OpenFileDialog();
        openFileDialog1.Filter = "DFA文件|*.dfa";
        openFileDialog1.Title = "选择DFA文件";
        if (openFileDialog1.ShowDialog() == DialogResult.OK)
        {
            lines = File.ReadAllLines(openFileDialog1.FileName);
            startSymbol = lines[0].Split(':').Last().Trim();
            endStates = lines[1].Split(':').Last().Split(';').Select(x => x.Trim()).ToArray();
            int maxState = int.Parse(lines[2].Split(':').Last().Trim());
            string[] symbols = lines[3].Split(':').Last().Split(';').Select(x => x.Trim()).ToArray();
            Dictionary<string, Dictionary<string, string>> transitions = new Dictionary<string, Dictionary<string, string>>();
            for (int i = 4; i < lines.Length; i++)
            {
                string[] parts = lines[i].Split('\t');
                string fromState = parts[0].Trim();
                string symbol = parts[1].Trim();
                string toState = parts[2].Trim();
                if (!transitions.ContainsKey(fromState))
                {
                    transitions[fromState] = new Dictionary<string, string>();
                }
                transitions[fromState][symbol] = toState;
            }
            listView2.Items.Clear();
            foreach (string state in transitions.Keys)
            {
                foreach (string symbol in transitions[state].Keys)
                {
                    string toState = transitions[state][symbol];
                    ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
                    listView2.Items.Add(item);
                }
            }
        }
        label5.Text = "初始状态集:" + startSymbol;
        label7.Text = "终止状态集:";
        for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
             label7.Text = label7.Text + endStates[i] + ";";
        button7.Enabled = false;
        button9.Enabled = true;
    }

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

        // 初始化DFA文件内容
        string nfaContent = startSym + "\n" + endSym + "\n";

        // 遍历listView1中的数据，生成DFA文件内容
        for (int i = 0; i < listView2.Items.Count; i++)
        {
            string startState = listView2.Items[i].SubItems[0].Text;
            string symbol = listView2.Items[i].SubItems[1].Text;
            string endState = listView2.Items[i].SubItems[2].Text;

            // 拼接DFA文件内容
            nfaContent += startState + "\t" + symbol + "\t" + endState + "\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, nfaContent, Encoding.UTF8);
        }
    }


    private void button7_Click(object sender, EventArgs e)//NFA->DFA
    {
        // 1.确定字母表
        // 2.对初始状态进行 e-closure 运算，得到 DFA 起始状
        // 3.开始子集构造
        // 标记已经加入到 DFA 中的状态
        // 待处理的状态集合队列

        //判断markedSet中是否已经存在U
        // 生成新状态
        // 判断一个状态集合是否为终止状态
    
        // 获取某个状态集合通过 symbol 转移的结果
    
        // e-closure 运算
         // e-closure 运算
    }


}

} 补全函数private void button7_Click(object sender, EventArgs e)//NFA->DFA内容：private void button7_Click(object sender, EventArgs e)//NFA->DFA { // 1.确定字母表 List alphabet = new List(symbolSet); alphabet.Remove(endSymbol);

// 2.对初始状态进行 e-closure 运算，得到 DFA 起始状态
List<string> startStateSet = new List<string>(startSymbol.Split(';'));
List<string> startDFAStateSet = new List<string>();
foreach (string startState in startStateSet)
{
    List<string> closure = EClosure(startState);
    foreach (string state in closure)
    {
        if (!startDFAStateSet.Contains(state))
        {
            startDFAStateSet.Add(state);
        }
    }
}

// 3.开始子集构造
List<List<string>> markedSets = new List<List<string>>();
List<List<string>> unmarkedSets = new List<List<string>>();
markedSets.Add(startDFAStateSet);
unmarkedSets.Add(startDFAStateSet);

while (unmarkedSets.Count > 0)
{
    List<string> T = unmarkedSets[0];
    unmarkedSets.RemoveAt(0);

    foreach (string symbol in alphabet)
    {
        List<string> U = new List<string>();
        foreach (string state in T)
        {
            List<string> transitions = GetTransitions(state, symbol);
            foreach (string nextState in transitions)
            {
                List<string> closure = EClosure(nextState);
                foreach (string state2 in closure)
                {
                    if (!U.Contains(state2))
                    {
                        U.Add(state2);
                    }
                }
            }
        }

        if (U.Count == 0)
        {
            continue;
        }

        bool isMarked = false;
        foreach (List<string> set in markedSets)
        {
            if (set.SequenceEqual(U))
            {
                isMarked = true;
                break;
            }
        }

        if (!isMarked)
        {
            markedSets.Add(U);
            unmarkedSets.Add(U);
        }

        string fromState = string.Join(";", T);
        string toState = string.Join(";", U);

        ListViewItem item = new ListViewItem(new[] { fromState, symbol, toState });
        listView3.Items.Add(item);
    }
}

// 4.确定终态
List<string> endDFAStateSet = new List<string>();
foreach (List<string> set in markedSets)
{
    foreach (string endState in endStates)
    {
        if (set.Contains(endState))
        {
            endDFAStateSet.Add(string.Join(";", set));
            break;
        }
    }
}

// 更新界面
label9.Text = "初始状态集:" + string.Join(";", startDFAStateSet);
label11.Text = "终止状态集:";
for (int i = 0; i < endDFAStateSet.Count; i++)
{
    label11.Text += endDFAStateSet[i];
    if (i < endDFAStateSet.Count - 1)
    {
        label11.Text += ";";
    }
}
button8.Enabled = true;

}

// 获取某个状态集合通过 symbol 转移的结果 private List GetTransitions(string state, string symbol) { List result = new List(); for (int i = 0; i < listView1.Items.Count; i++) { string startState = listView1.Items[i].SubItems[0].Text; string inputSymbol = listView1.Items[i].SubItems[1].Text; string endState = listView1.Items[i].SubItems[2].Text;

    if (startState == state && inputSymbol == symbol)
    {
        result.Add(endState);
    }
}
return result;

}

// e-closure 运算 private List EClosure(string state) { List result = new List(); result.Add(state);

bool changed = true;
while (changed)
{
    changed = false;
    for (int i = 0; i < listView1.Items.Count; i++)
    {
        string startState = listView1.Items[i].SubItems[0].Text;
        string inputSymbol = listView1.Items[i].SubItems[1].Text;
        string endState = listView1.Items[i].SubItems[2].Text;

        if (inputSymbol == "ε" && result.Contains(startState) && !result.Contains(endState))
        {
            result.Add(endState);
            changed = true;
        }
    }
}

return result;

}

NFA 到 DFA 的转换工具：自动生成 DFA 文件

原文地址: https://www.cveoy.top/t/topic/kqQq 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录