Java实现NFA的确定化（编译原理实验）

该程序包含两个类，一个主类封装了用于确定化NFA的方法以及用于存储数据的数据结构，另一个为测试类，约束了怎样的输入格式以及结果的输出格式。
主类结构如下：

源码如下：

package experiment1;

import java.util.*;

public class DFA {

    /**测试
    public static void main(String[] args) {
        char[] letter = {'a','b'};//字母表
        List<Integer> K0 = Arrays.asList(0);//初态
        char[][] f = new char[11][11];//转换函数
        for(int i = 0;i<11;i++) f[i][i] = 'ε';
        f[0][1] = 'ε';f[0][7] = 'ε';f[1][2] = 'ε';f[1][4] = 'ε';f[2][3] = 'a';f[3][6] = 'ε';f[4][5] = 'b';
        f[5][6] = 'ε';f[6][1] = 'ε';f[6][7] = 'ε';f[7][8] = 'a';f[8][9] = 'b';f[9][10] = 'b';
        StringBuilder D = new StringBuilder();
        Set<List<Integer>> set = new DFA().subSet(letter,f,K0,D);
        System.out.println(D);
        for (List list : set){
            list.forEach(System.out::print);
            System.out.println();
        }
    }

     0 ε 1
     0 ε 7
     1 ε 2
     1 ε 4
     2 a 3
     3 ε 6
     4 b 5
     5 ε 6
     6 ε 1
     6 ε 7
     7 a 8
     8 b 9
     9 b 10
     100

    /**
     * 子集法
     * @param letter 字母表
     * @param f 转换函数
     * @param K0 初态集
     */
    public Set<List<Integer>> subSet(char[] letter,char[][] f,List<Integer> K0,StringBuilder D){
        if (letter == null || f == null || K0 == null)
            throw new RuntimeException("确定化失败！");
        Set<List<Integer>> set = new LinkedHashSet<>();//最终结果
        ArrayDeque<List<Integer>> C = new ArrayDeque<>();//临时队列,广度优先搜索BFS
        //1、计算ε-closure(K0)
        List<Integer> T0 = closure(K0,f),cT;
        T0.sort(Comparator.naturalOrder());
        C.addLast(T0);
        set.add(T0);
        int i = 0,j = 1,k;
        //2、构造子集
        do {
            T0 = C.removeFirst();
            for (char c : letter){
                cT = closure(move(T0,c,f),f);
                cT.sort(Comparator.naturalOrder());
                if (!set.contains(cT)){
                    set.add(cT);
                    C.addLast(cT);
                    k = j++;
                }else {
                    int idx = 0;
                    for (List list : set){
                        if (list.equals(cT)) break;
                        else idx++;
                    }
                    k = idx;
                }
                D.append("D([T"+(i)+"],"+c+")=[T"+k+"]").append("\n");
            }i++;
        }while(!C.isEmpty());
        return set;
    }

    /**
     *
     * @param I 状态集
     * @param f 转换函数
     * @return ε-closure(I)
     */
    public List<Integer> closure(List<Integer> I, char[][] f){
        if (I == null || f == null)
            throw new RuntimeException("确定化失败！");
        List<Integer> rs = new ArrayList<>();//最终结果
        ArrayDeque<Integer> ad = new ArrayDeque<>();//临时队列，广度优先搜索BFS
        for(Integer it : I){
            if (rs.indexOf(it)==-1){
                ad.addLast(it);
                do {
                    int tp = ad.removeFirst();
                    for(int i = 0;i<f.length;i++){
                        if (f[tp][i]=='ε'){
                            if (rs.indexOf(i)==-1) rs.add(i);
                            if(i!=tp) ad.addLast(i);
                        }
                    }
                }while (ad.size()>0);
            }
        }
        return rs;
    }

    /**
     *
     * @param I 状态集
     * @param c 字母
     * @param f 转换函数
     * @return move(I,a)
     */
    public List<Integer> move(List<Integer> I, char c, char[][] f){
        if(I == null || f == null)
            throw new RuntimeException("确定化失败！");
        List<Integer> rs = new ArrayList<>();
        for(Integer it : I){
            for(int i = 0;i<f.length;i++){
                if(f[it][i]==c && !rs.contains(i)){
                    rs.add(i);
                }
            }
        }
        return rs;
    }
}

测试类结构如下：

源码如下：

package experiment1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Test {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //输入NAF相关元组：字母表∑、状态集K、初态集K0、转换函数f
        System.out.println("请输入字母表∑（连续字符串）：");
        char[] letter = br.readLine().toCharArray();

        System.out.println("请输入状态集K的个数：");
        int n = Integer.parseInt(br.readLine());
        char[][] f = new char[n][n];
        for(int i = 0;i<n;i++) f[i][i] = 'ε';//任意状态经一条ε弧能到达自身状态

        System.out.println("请输入初态集K0（形如0,1...,n）：");
        String[] strings = br.readLine().split(",");
        List<Integer> K0 = new ArrayList<>();
        for(String string : strings) K0.add(Integer.parseInt(string));

        System.out.println("请输入转换函数f（形如：0 ε 1）：");
        String line = "";
        while (!(line = br.readLine().trim()).equals("100")){
            strings = line.trim().split("\\s+");
            if(strings.length!=3) throw new RuntimeException("非法输入！确定化失败！");
            f[Integer.parseInt(strings[0])][Integer.parseInt(strings[2])] = strings[1].charAt(0);
        }
        StringBuilder D = new StringBuilder();//存储确定化NFA后，即DFA的转换函数


        //确定化NFA
        Set<List<Integer>> set = new DFA().subSet(letter,f,K0,D);//存储状态集K的子集

        //输出DFA相关元组状态集S、转换函数D
        System.out.println("子集个数为："+set.size());
        System.out.println("输出DFA的状态集S：");
        StringBuilder T = new StringBuilder(),cT = new StringBuilder();
        int i = 0;
        for (List<Integer> t : set){
            for (Integer it : t) cT.append(","+it);
            T.append("T"+(i++)+"={").append(cT.substring(1)).append("}");
            System.out.println(T);
            T.setLength(0);cT.setLength(0);
        }
        System.out.println("DFA的转换函数D如下：");
        System.out.println(D);
    }
}

实验结果如下：
输入结果

最终结果