NFA to DFA Conversion in C# - Implementation and Explanation

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.TreeView;

namespace WindowsFormsApp1.Resources.function_cs
{
    class NFA_DFA
    {
        DFA dfa = null;

        public NFA_DFA(NFA nfa)
        {
            dfa = new DFA(nfa);
        }

        public DFA get_dfa()
        {
            return dfa;
        }
    }

    public class DFA
    {
        int stateNum;                   // 状态数
        int initialState = 1;           //初始状态
        List<int> finalStates;          // 终止状态集合
        List<char> alphabet;            // 字母表
        List<List<Tuple<int, char>>> graph;    // 状态关系图
        public List<List<Tuple<int, char>>> get_graph()
        {
            return graph;
        }

        public List<int> get_finalStates()
        {
            return finalStates;
        }

        public int get_initialState()
        {
            return initialState;
        }

        public int get_stateNum()
        {
            return stateNum;
        }

        public List<char> get_alphabet()
        {
            return alphabet;
        }

        //public void set_graph(List<List<Tuple<int, char>>> graph)
        //{
        //    this.graph = graph;
        //}

        //public void set_stateNum(int n)
        //{
        //    this.stateNum = n;
        //}

        //public void set_finalStates(List<int> finalStates)
        //{
        //    this.finalStates = finalStates;
        //}

        //public void set_initialState(int initialState)
        //{
        //    this.initialState = initialState;
        //}

        //public void set_alphabet(List<char> alphabet)
        //{
        //    this.alphabet = alphabet;
        //}

        public DFA(int stateNum, int initialState, List<int> finalStates, List<char> alphabet, List<List<Tuple<int, char>>> graph)
        {
            this.stateNum = stateNum;
            this.initialState = initialState;
            this.graph = graph;
            this.alphabet = alphabet;
            this.finalStates = finalStates;
        }

        public DFA(NFA nfa)
        {
            stateNum = 1;
            finalStates = new List<int>();
            graph = new List<List<Tuple<int, char>>>();
            graph.Add(new List<Tuple<int, char>>());
            alphabet = new List<char>();

            // 1.确定字母表
            foreach (var state in nfa.get_graph())
            {
                foreach (var tuple in state)
                {
                    if (tuple.Item2 != '#' && !alphabet.Contains(tuple.Item2))
                        alphabet.Add(tuple.Item2);
                }
            }

            // 2.对初始状态进行 e-closure 运算，得到 DFA 起始状态
            List<int> start = EpsilonClosure(nfa.get_se().Item1, nfa);

            // 3.开始子集构造
            HashSet<List<int>> markedSet = new HashSet<List<int>>();        // 标记已经加入到 DFA 中的状态
            Queue<List<int>> unmarkedSet = new Queue<List<int>>();           // 待处理的状态集合队列
            unmarkedSet.Enqueue(start);
            markedSet.Add(start);
            AddNewState(start,nfa);

            while (unmarkedSet.Count > 0)
            {
                List<int> T = unmarkedSet.Dequeue();
                foreach (var alpha in alphabet)
                {
                    List<int> U = EpsilonClosure(NFAmove(T, alpha, nfa), nfa);
                    if (U != null && U.Count!=0)
                    {
                        int index = isexit(markedSet, U);
                        if (index == 0)
                        {
                            AddNewState(U, nfa);
                            markedSet.Add(U);
                            unmarkedSet.Enqueue(U);
                        }
                        graph[isexit(markedSet, T)].Add(Tuple.Create(isexit(markedSet, U), alpha));
                    }
                }
            }
        }

        //判断markedSet中是否已经存在U
        int isexit(HashSet<List<int>> markedSet, List<int> U)
        {
            List<int> u= U;
            u.Sort();
            for (int i=0; i< markedSet.Count;i++)
            {
                var state = markedSet.ElementAt(i);
                List<int> v = state;
                v.Sort();
                if (u.SequenceEqual(v))
                    return i+1;
            }
            return 0;
        }

        // 生成新状态
        void AddNewState(List<int> state, NFA nfa)
        {
            graph.Add(new List<Tuple<int, char>>());
            if (IsFinalState(state, nfa))
                finalStates.Add(stateNum);
            stateNum++;
        }

        // 判断一个状态集合是否为终止状态
        bool IsFinalState(List<int> stateSet, NFA nfa)
        {
            foreach (var s in stateSet)
            {
                if (nfa.get_se().Item2 == s)
                    return true;
            }
            return false;
        }

        // 获取某个状态集合通过 symbol 转移的结果
        List<int> NFAmove(List<int> T, char symbol, NFA nfa)
        {
            List<int> result = new List<int>();
            foreach (var t in T)
            {
                foreach (var tuple in nfa.get_graph()[t])
                {
                    if (tuple.Item2 == symbol && !result.Contains(tuple.Item1))
                        result.Add(tuple.Item1);
                }
            }
            return result;
        }

        // e-closure 运算
        List<int> EpsilonClosure(int state, NFA nfa)
        {
            HashSet<int> visited = new HashSet<int>();
            Stack<int> stack = new Stack<int>();
            stack.Push(state);
            visited.Add(state);
            while (stack.Count > 0)
            {
                int s = stack.Pop();
                foreach (var tuple in nfa.get_graph()[s])
                {
                    if (tuple.Item2 == '#' && !visited.Contains(tuple.Item1))
                    {
                        visited.Add(tuple.Item1);
                        stack.Push(tuple.Item1);
                    }
                }
            }
            return visited.ToList();
        }

        // e-closure 运算
        List<int> EpsilonClosure(List<int> T, NFA nfa)
        {
            HashSet<int> visited = new HashSet<int>();
            Stack<int> stack = new Stack<int>();
            foreach (var t in T)
            {
                stack.Push(t);
                visited.Add(t);
            }

            while (stack.Count > 0)
            {
                int s = stack.Pop();
                foreach (var tuple in nfa.get_graph()[s])
                {
                    if (tuple.Item2 == '#' && !visited.Contains(tuple.Item1))
                    {
                        visited.Add(tuple.Item1);
                        stack.Push(tuple.Item1);
                    }
                }
            }
            return visited.ToList();
        }
    }
}

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
        {
            // Define your NFA data structures (NFA class) here
            NFA nfa = new NFA(startSymbol, endSymbol, symbolSet.ToList(), listView1);
            DFA dfa = new NFA_DFA(nfa).get_dfa();

            // Display the DFA state transition diagram
            List<List<Tuple<int, char>>> graph = dfa.get_graph();
            for (int i = 0; i < graph.Count; i++)
            {
                for (int j = 0; j < graph[i].Count; j++)
                {
                    string startState = i.ToString();
                    string symbol = graph[i][j].Item2.ToString();
                    string endState = graph[i][j].Item1.ToString();
                    ListViewItem item = new ListViewItem(new[] { startState, symbol, endState });
                    listView2.Items.Add(item);
                }
            }

            // Display the initial state and set of final states for the DFA
            label5.Text = '初始状态集:' + dfa.get_initialState().ToString();
            label7.Text = '终止状态集:';
            foreach (var state in dfa.get_finalStates())
            {
                label7.Text += state.ToString() + ';';
            }

            button7.Enabled = false;
            button9.Enabled = true;
        }


    }
}

Explanation

1. NFA to DFA Conversion:

   • The code first creates an NFA object using the input data (start symbol, end symbol, symbol set, and the NFA transition table from listView1).
   • It then constructs an NFA_DFA object and uses it to convert the NFA to a DFA. The conversion logic is encapsulated within the DFA class.
   • The converted DFA object is accessed using get_dfa().

2. Displaying DFA Information:

   • The state transition graph of the DFA is displayed in listView2. It iterates through the DFA's graph to extract start state, symbol, and end state information for each transition.
   • The DFA's initial state is displayed in label5. The final states are displayed in label7, separated by semicolons.

3. Button Enabling:

   • After conversion, button7 (NFA to DFA conversion button) is disabled. button9 (potentially related to DFA operations) is enabled.

Note:

• This code assumes that you have already defined the NFA class and its necessary methods (e.g., get_graph(), get_se()). You will need to implement these based on your specific NFA representation.
• This code provides a basic implementation of the conversion process. You may need to modify or expand it depending on your specific requirements and the complexity of your NFA.