编译原理——实现NFA到DFA 的转换(子集构造法)

一、实验内容

利用⼦集构造法的实现任意NFA到DFA 的转换。

二、编程思路：

1. 建立一个NFA类，包括初始状态，输入，下一状态；
2. 建立一个DFA类，包括初始状态，输入，下一状态；
3. 建立init()函数，主要功能是将NFA输入，包括初态、终态，边数，输入的字符集，转换函数（若输入为空则用“*”代替），保存在NFA类构建的对象数组中；
4. 建立definite()函数,首先找到初状态集，寻找初状态能通过空到达状态将其保存在一个字符串中形成初状态集合，将初状态压入栈，放入队列。
5. 取出队列中的字符串，逐个状态分别找到输入“a”（“0”）能到达的状态放入一个字符串形成状态集，再逐个状态判断能通过空到达的状态，放入字符串形成状态集（输入为“b”（“1”）同理）；
6. 找到状态集之后，对该状态集字符串排序，再判断该状态集字符串是否已经存在栈中（即是否为一个新的状态），若不在栈中则将其压入栈中，并放入队列中，保存在DFA类构建的对象数组中；
7. 重复（5）（6）操作，当队列为空时，证明已经没有新状态产生了，停止循环。
8. 依次取出栈中的字符串状态集，将其转化成新的状态名，并修改DFA类构建的对象数组，输出。

package NFACHDFA;
import java.io.IOException;
import java.util.*;
/*
测试案例一：
请输入初态和终态：
A C
请输入边数：
6
请输入输入字符集：
01
请输入转换函数 按照如下格式（a1b）若有空则用“*”代替：
A0A
A1A
A1B
A0C
B1D
C0D



 */

/*
测试案例二：

请输入初态和终态：
A F
请输入边数：
10
请输入输入字符集：
01
请输入转换函数 按照如下格式（a1b）若有空则用“*”代替：
A0A
A1A
A0B
A1D
B0C
D1E
C0F
E1F
F0F
F1F
  
  
  
 */

/*
测试案例三：

请输入初态和终态：
i f
请输入边数：
12
请输入输入字符集：
ab
请输入转换函数 按照如下格式（a1b）若有空则用“*”代替：
i*1
1a1
1b1
1*2
2a3
2b4
3a5
4b5
5*6
6a6
6b6
6*f
 */


class NFAf {    //NFA转换
	char former;//前一状态
	char in;    //输入
	char latter;//后一状态
	public NFAf(char former,char in,char latter) {
		this.former=former;
		this.in=in;
		this.latter=latter;
	}
}
class DFAf {        //DFA转换
	String former;  //前一状态集
	char in;        //输入
	String latter; //后一状态集
	public DFAf(String former,char in,String latter) {
		this.former=former;
		this.in=in;
		this.latter=latter;
	}
	public void set(String former,String latter) {
		this.former=former;
		this.latter=latter;
	}
}

public class NFACHDFA {
	
	Scanner sc=new Scanner(System.in);
	
	NFAf []nfa=new NFAf[100];//最多为100条边
	DFAf []dfa=new DFAf[100];//最多边数为100条
	
	public char S;                //初态
	public char Z;                //终态
	public String DZ;             //DFA的终态
	public int len;               //NFA边数
	public int lend=0;            //DFA边数
	public char[] put=new char[2];//输入集
	
	
	public static Stack<String> stack=new Stack<String>();//存放DFA状态集
	public static Queue<String> queue = new LinkedList<String>();//队列为空时结束
	
	public void init() throws IOException {  //初始化
		
		System.out.println("请输入初态和终态：");
		S=(char)System.in.read();
		System.in.read();      //清除空格
		Z=(char)System.in.read();
		//System.out.print(S+" "+Z);
		
		System.out.println("请输入边数：");
		len=sc.nextInt();
		
		System.out.println("请输入输入字符集：");
		put[0]=(char)System.in.read();
		put[1]=(char)System.in.read();
		
		String ss[]=new String[len];
		System.out.println("请输入转换函数 按照如下格式（a1b）若有空则用“*”代替：");
		
		for(int i=0;i<len;i++){
			ss[i]=sc.next();
		}
		
		/*for(int i=0;i<len;i++){
			System.out.println(ss[i]);
		}*/
		
		for(int i=0;i<len;i++){
			char f=ss[i].charAt(0);
			char m=ss[i].charAt(1);
			char n=ss[i].charAt(2);
			nfa[i]=new NFAf(f,m,n);
		}
		
		/*for(int i=0;i<len;i++) {
			System.out.println(nfa[i].former+" "+nfa[i].in+" "+nfa[i].latter);
		}*/
	}
	
	//找出状态的集合
	public void definite() {
		
		String a="";//输入a的状态集
		String b="";//输入b的状态集
		String begin="";//第一个状态集
		
		begin=begin+S;
		//System.out.println(begin);
		for(int i=0;i<begin.length();i++) {
			for(int j=0;j<len;j++) {
				if(begin.contains(String.valueOf(nfa[j].former))&&
						!begin.contains(String.valueOf(nfa[j].latter))&&nfa[j].in=='*') {
					begin=begin+nfa[j].latter;
						//System.out.println(begin.length());
				}
			}
		}
		begin=sort(begin); //对状态集排序
		
		stack.add(begin);
		queue.add(begin);
		
		while(!queue.isEmpty()) {
			String temp=queue.poll();//返回第一个元素，并在队列中删除
			a="";
			b="";
			for(int i=0;i<temp.length();i++) {
				for(int j=0;j<len;j++) {
					if(nfa[j].former==temp.charAt(i)&&nfa[j].in==put[0]) {
						String c=String.valueOf(nfa[j].latter);
						if(!a.contains(c)){
							a=a+nfa[j].latter;
						}
					}
					else if(nfa[j].former==temp.charAt(i)&&nfa[j].in==put[1]) {
						String c=String.valueOf(nfa[j].latter);
						if(!b.contains(c)) {
							b=b+nfa[j].latter;
						}
					}
				}
				
			}
			for(int i=0;i<a.length();i++) {
				for(int j=0;j<len;j++) {
					if(a.contains(String.valueOf(nfa[j].former))&&nfa[j].in=='*') {
						String c=String.valueOf(nfa[j].latter);
						if(!a.contains(c)){
							a=a+nfa[j].latter;
						}
				
					}
				}
			}
			for(int i=0;i<b.length();i++) {
				for(int j=0;j<len;j++) {
					if(b.contains(String.valueOf(nfa[j].former))&&nfa[j].in=='*') {
						String c=String.valueOf(nfa[j].latter);
						if(!b.contains(c)) {
							b=b+nfa[j].latter;
						}
					}
				}
			}
			
			a=sort(a);
			b=sort(b);
			
			
			dfa[lend]=new DFAf(temp,put[0],a);
			lend=lend+1;
			dfa[lend]=new DFAf(temp,put[1],b);
			lend=lend+1;
			//System.out.println(former+" "+latter);
			if(!stack.contains(a)) {
				stack.add(a);
				queue.add(a);
			}
			if(!stack.contains(b)) {
				stack.add(b);
				queue.add(b);
			}
			/*for(String q : queue){
	            System.out.print(q+" ");
	        }
			System.out.println();
			*/
		}
		/*for(int i=0;i<lend;i++) {
			System.out.println(dfa[i].former+" "+dfa[i].in+" "+dfa[i].latter);
		}*/
	}
	
	public void change() {
		String[][] ss=new String[stack.size()][3];
		int le=0;
		char c=(char)('A'+stack.size()-1);
		//System.out.println(stack.size());
		while(!stack.isEmpty()) {
			ss[le][0]=stack.pop();
			ss[le][1]=String.valueOf(c);
			if(ss[le][0].contains(String.valueOf(Z))){
				ss[le][2]="1";
			}
			else {
				ss[le][2]="0";
			}
			c=(char) (c-1);
			le=le+1;
		}
		//System.out.print(le);
		
		/*for(int j=0;j<le;j++) {
			System.out.println(ss[j][0]+" "+ss[j][1]+" "+ss[j][2]);
		}*/
		String tempf="";
		String tempn="";
		for(int i=0;i<lend;i++) {
			for(int j=0;j<le;j++) {
				if(dfa[i].former.equals(ss[j][0])) {
					tempf=ss[j][1];
				}
				if(dfa[i].latter.equals(ss[j][0])) {
					tempn=ss[j][1];
				}
			}
			dfa[i].set(tempf,tempn);
		}
		System.out.println("转换后的DFA为：");
		for(int i=0;i<lend;i++) {
			System.out.println(dfa[i].former+" "+dfa[i].in+" "+dfa[i].latter);
		}
		
		System.out.println("转换后的DFA初态为：");
		System.out.println(ss[le-1][1]+" ");
		
		System.out.println("转换后的DFA终态集为：");
		for(int i=0;i<le;i++) {
			if(ss[i][2].equals("1")) {
				System.out.print(ss[i][1]+" ");
			}
		}
		
	}
	
	public static String sort(String str){
        //利用toCharArray可将字符串转换为char型的数组
        char[] s1 = str.toCharArray();
        for(int i=0;i<s1.length;i++){
            for(int j=0;j<i;j++){
                if(s1[i]<s1[j]){
                    char temp = s1[i];
                    s1[i] = s1[j];
                    s1[j] = temp;
                }
            }
        }
        //再次将字符数组转换为字符串，也可以直接利用String.valueOf(s1)转换
        String st = new String(s1);
        return st;
    }
	
	
	public static void main(String args[]) {
		NFACHDFA dfa=new NFACHDFA();
		try {
			dfa.init();
		}
		catch(Exception e) {
			
		}
		dfa.definite();
		dfa.change();
	}
}