编译原理实验报告实验名称NFA转换为DFA实验时间2014-5-18院系计算机科学与技术学院班级学号姓名1.试验目的不确定有限状态自动机的确定化（Affirmation of the indefinitely finite automata）2.实验原理一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：（1）K是一个有穷非空集，集合中的每个元素称为一个状态；（2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号；（3）F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态；（4）S∈K，是惟一的初态；（5）Z⊆K，是一个终态集。

由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。

对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。

若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。

一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：（1）k是一个有穷非空集，集合中的每个元素称为一个状态；（2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号；（3）F是一个从K×∑→K的子集的转换函数；（4）S⊆K，是一个非空的初态集；（5）Z⊆K，是一个终态集。

由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。

即DFA中的F是单值函数，而NFA中的F是多值函数。

因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。

和DFA一样，NFA也可以用矩阵和状态转换图来表示。

对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M所接受。

NFA M所能接受的全部字符串（字）组成的集合记作L（M）。

由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。

设M1和M2是同一个字母集∑上的有限自动机，若L（M1）＝L（M2），则称有限自动机M1和M2等价。

由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。

DFA是NFA的特例，因此对于每一个NFA M1总存在一个DFA M2，使得L（M1）＝L（M2）。

即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。

NFA确定化为DFA同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA 确定化为DFA。

下面介绍一种NFA的确定化算法，这种算法称为子集法：（1）若NFA的全部初态为S1，S2，…，S n，则令DFA的初态为：S＝[S1，S2，…，S n]，其中方括号用来表示若干个状态构成的某一状态。

（2）设DFA的状态集K中有一状态为[S i，S i+1，…，S j]，若对某符号a∈∑，在NFA 中有F（{ S i，S i+1，…，S j }，a）={ S i’，S i+1’，…，S k’ }则令F（{ S i，S i+1，…，S j}，a）={ S i’，S i+1’，…，S k’}为DFA的一个转换函数。

若[ S i’，S i+1’，…，S k‘ ]不在K中，则将其作为新的状态加入到K中。

（3）重复第2步，直到K中不再有新的状态加入为止。

（4）上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。

（5）DFA中凡是含有NFA终态的状态都是DFA的终态。

对于上述NFA确定化算法——子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。

首先给出两个相关定义。

假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为：（1）若Q∈I，则Q∈ε-closure（I）；（2）若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈ε-closure（I）。

状态集ε-closure（I）称为状态I的ε闭包。

＝ε-closure 假设NFA M＝（K，∑，F，S，Z），若I∈K，a∈∑，则定义Ia（J），其中J是所有从ε-closure（I）出发，经过一条a弧而到达的状态集。

NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。

经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。

3.实验内容输入：非确定有限（穷）状态自动机。

输出：确定化的有限（穷）状态自动机4.实验心得此次实验采用了java可视化的界面来编程的，编程的主要思想是：首先构造NFA的状态的子集的算法，再来计算ε-closure。

完成这些子模块的设计后，再通过某一中间模块的总控程序对其调用，最后再由主程序总调用，也就实现了NFA转化为其等价的DFA，接下来就是在实现DFA的化简，最后加以验证，经多次代码的修改成型。

通过实验，我可以更好的掌握了NFA到DFA的转化的原理。

5.实验代码与结果5.1实验运行结果截图如下：左侧为输入的每个NFA的每个状态，右侧为显示的结果，显示了子集个数，和由NFA构造的·DFA状态。

5.2代码：package wy;import java.awt.Graphics;import java.awt.Graphics2D;import java.awt.Image;import java.awt.Toolkit;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.util.ArrayList;import javax.swing.*;class Node{ //每一个结点包含的有以该结点为起始的整条边的信息：String data; //本结点值String condition;//条件值空符号串用ε表示String next;//指向下一个结点的结点值Node(String d)//终止结点{data=d;condition=null;next=null;}Node(String d,String c,String s)//非终止结点{data=d;condition=c;next = s; //下一个结点的值}}public class NFA_DFA extends JFrame{public static void main(String[] args) {NFA_DFA nfa_dfa=new NFA_DFA();nfa_dfa.NFA_DFA();}public JLabel jl0 = new JLabel("----每条边的信息如下：----------------");public JLabel jl_start = new JLabel("起点状态:");public JLabel jl_condition = new JLabel("条件:");public JLabel jl_end = new JLabel("终点状态:");public JTextField jtf_start = new JTextField();public JTextField jtf_condition = new JTextField();public JTextField jtf_end = new JTextField();public JButton jbt0 = new JButton("确定");public JLabel jl_start0 = new JLabel("初态:");public JLabel jl_end0 = new JLabel("终态:");public JButton jbt1 = new JButton("确定");public JTextField jtf_start0 = new JTextField();public JTextField jtf_end0 = new JTextField();public JTextArea jta_display = new JTextArea();public JScrollPane sta1 = new JScrollPane(jta_display);public JButton jbt_result = new JButton("结果显示");public JTextArea jta_display1 = new JTextArea();public JScrollPane sta2 = new JScrollPane(jta_display1);public ArrayList<Node> node = new ArrayList<Node>();//非终止结点public ArrayList<Node> node_end = new ArrayList<Node>();//终止结点public ArrayList<String> condition = new ArrayList<String>();//条件符号public ArrayList<ArrayList<String>> C=new ArrayList<ArrayList<String>>();//子集族Cpublic ArrayList<String> CC=new ArrayList<String>();//重命名的Cpublic String start0;//初态值public void NFA_DFA(){this.setTitle("NFA转换为DFA----WY");this.setContentPane(new MyPanel5());this.setLayout(null);this.setSize(700, 700);jl_start0.setBounds(150, 35, 70, 30);add(jl_start0);jtf_start0.setBounds(200, 35,120, 30);add(jtf_start0);jl_end0.setBounds(350, 35, 70, 30);add(jl_end0);jtf_end0.setBounds(400, 35, 120, 30);add(jtf_end0);jbt1.setBounds(555, 35, 60, 30);add(jbt1);jl0.setBounds(200, 80,200, 30);add(jl0);jl_start.setBounds(145, 110, 70, 30);add(jl_start);jl_condition.setBounds(300, 110,50, 30);add(jl_condition);jl_end.setBounds(445, 110, 70, 30);add(jl_end);jtf_start.setBounds(130, 140, 80, 30);add(jtf_start);jtf_condition.setBounds(280, 140,80, 30);add(jtf_condition);jtf_end.setBounds(430, 140, 80, 30);add(jtf_end);jbt0.setBounds(555, 140, 60, 30);add(jbt0);sta1.setBounds(80, 250, 200, 400);add(sta1);sta2.setBounds(300, 250, 300, 400);add(sta2);jbt_result.setBounds(300, 200, 100, 30);add(jbt_result);this.setVisible(true);jta_display.append("每条边的显示：\n");jbt1.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {start0=jtf_start0.getText(); //初态String str3 = jtf_end0.getText();String[] ss3 = new String[100];ss3 = str3.split(","); // 终态在输入的时候以","隔开for (int i = 0; i < ss3.length; i++) {Node node_end0=new Node(ss3[i]);node_end.add(node_end0); //将终态加入终止结点中}}});jbt0.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {jta_display.append(jtf_start.getText()+"—>"+jtf_condition.getText()+"—>"+jtf_end.getText()+"\n");Node node_temp=new Node(jtf_start.getText(),jtf_condition.getText(),jtf_end.getText());node.add(node_temp); //加入非终止结点if(!condition.contains(jtf_condition.getText())&& !jtf_condition.getText().equals("ε"))condition.add(jtf_condition.getText()); //加入条件符号jtf_start.setText(null);jtf_condition.setText(null);jtf_end.setText(null);}});jbt_result.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {myNFA_DFA();}});}public void myNFA_DFA(){ArrayList<Boolean> flag=new ArrayList<Boolean>();//标记//1、找起始结点,计算起始结点的T0=e_closure(start0); 此时T0没有标记,是子集族C中唯一的元素ArrayList<String> T0=new ArrayList<String>();T0=e_closure(start0);C.add(T0);flag.add(false);//此时T0没有标记//2.标记T0；T1=e_closure(move(T0,a)),T2=e_closure(move(T0,b))····,将T1,T2加入C中，但是未标记flag.set(0,true);//标记T0for(int i=0;i<condition.size();i++){ ArrayList<String> T=new ArrayList<String>();ArrayList<String> t1=new ArrayList<String>();t1=move(T0,condition.get(i));T=e_closure0(t1);if(!C.contains(T)){C.add(T);flag.add(false);}}//3.分别标记flag=false的对应的C中的项while(flag.contains(false)){int index=flag.indexOf(false);flag.set(index,true);//标记C的index，即ArrayList<String> C_temp=new ArrayList<String>();C_temp=C.get(index);for(int i=0;i<condition.size();i++){ ArrayList<String> T=new ArrayList<String>();ArrayList<String> t1=new ArrayList<String>();t1=move(C_temp,condition.get(i));T=e_closure0(t1);if(!C.contains(T)){C.add(T);flag.add(false);}}}display();//在文本域中显示结果}public void display(){jta_display1.append("算法终止共构造了"+C.size()+"个子集：\n");for(int i=0;i<C.size();i++){jta_display1.append("T"+i+" = "+C.get(i)+"\n");CC.add("T"+i); //给新得的子集重新命名T1,T2,T3....}jta_display1.append("给定NFA构造的DFA为：\n");jta_display1.append("1、S={");for(int i=0;i<CC.size()-1;i++)jta_display1.append("["+CC.get(i)+"],");jta_display1.append("["+CC.get(CC.size()-1)+"]}\n");jta_display1.append("2、ε={");for(int i=0;i<condition.size()-1;i++)jta_display1.append(CC.get(i)+",");jta_display1.append(CC.get(CC.size()-1)+"}\n");ArrayList<String> D=new ArrayList<String>();D=transform(C);jta_display1.append("3、\n");for(int i=0;i<D.size();i++)jta_display1.append(D.get(i)+"\n");jta_display1.append("4、S0= ["+CC.get(0)+"]\n");jta_display1.append("5、St= ["+CC.get(CC.size()-1)+"]\n");}public ArrayList<String> transform(ArrayList<ArrayList<String>> c){ //转换函数DArrayList<String> r=new ArrayList<String>();ArrayList<String> r_temp = new ArrayList<String>();for(int i=0;i<c.size();i++){ArrayList<String> c_temp = new ArrayList<String>();c_temp=c.get(i);for(int j=0;j<condition.size();j++){r_temp=e_closure0(move(c_temp,condition.get(j)));for(int k=0;k<CC.size();k++){if(r_temp.equals(C.get(k)))r.add(" D( ["+CC.get(i)+"] , "+condition.get(j)+" ) = ["+CC.get(k)+"]");}}}return r;}public ArrayList<String> e_closure0(ArrayList<String> AA){ArrayList<String> T1=new ArrayList<String>();for(int i=0;i<AA.size();i++){ArrayList<String> T=new ArrayList<String>();T=e_closure(AA.get(i));for(int j=0;j<T.size();j++){T1.add(T.get(j));}}return T1;}public ArrayList<String> e_closure(String A){ArrayList<String> T=new ArrayList<String>();for(int k=0;k<node_end.size();k++){if(A.equals(node_end.get(k).data)){if(!T.contains(A))T.add(A); //e_closure()将自身也包含进去的}}for(int i=0;i<node.size();i++){if(A.equals(node.get(i).data) ){if(!T.contains(A))T.add(A); //e_closure()将自身也包含进去的if(node.get(i).condition.equals("ε")){T.add(node.get(i).next); //经过一条ε弧for(int j=0;j<node.size();j++){if(node.get(i).next.equals(node.get(j).data)&& node.get(j).condition.equals("ε")){T.add(node.get(j).next); //经过两条ε弧for(int k=0;k<node.size();k++){if(node.get(j).next.equals(node.get(k).data)&& node.get(k).condition.equals("ε")){T.add(node.get(k).next); //经过三条ε弧for(int m=0;m<node.size();m++){ if(node.get(k).next.equals(node.get(m).data)&&node.get(m).condition.equals("ε")){T.add(node.get(m).next); //经过四条ε弧}}}}}}}}}return T;}public ArrayList<String> move(ArrayList<String> TT,String a){ //move(I,a)函数ArrayList<String> T=new ArrayList<String>();for(int i=0;i<TT.size();i++){for(int j=0;j<node.size();j++){if(TT.get(i).equals(node.get(j).data) && node.get(j).condition.equals(a)){T.add(node.get(j).next);}}}return T;}}class MyPanel5 extends JPanel {public void paintComponent(Graphics g) {Graphics2D g2 = (Graphics2D) g;super.paintComponent(g);Image img = Toolkit.getDefaultToolkit().getImage("./src/1.jpg");g2.drawImage(img, 0, 0, this.getWidth(), this.getHeight(), this);}}。