代码模拟确定有限自动机（DFA）执行过程

一个确定有限自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中

① K是一个有穷集，它的每个元素称为一个状态；

② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；

③ f是转换函数，是K×Σ→K上的映射(且可以是部分函数)，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；

④ S ∈ K是唯一的一个初态；

⑤ Z⊂K是一个终态集，终态也称可接受状态或结束状态。

其具体过程：从初始状态出发，对于输入字符串中的每个字符，自动机都将沿着一条确定的边到另一状态，这条边必须是标有输入符号的边。对n个字符的字符串进行了n次状态变换后，如果自动机到达了一个终态，自动机将接收该字符串。若到达的不是终态，或者找不到与输入字符相匹配的边，那么字符串将拒绝接受这个字符串。 由一个自动机识别的语言是该自动机接收的字符串集合。

代码模拟过程：

DFA规定：

a规则，以00结尾

b规则，含连续三个0

c规则，包含011子串

首先构建这三个DFA的状态转移图：

根据状态转移图定义状态结点，并定义相应的转移函数。

具体代码如下：

package practice2_2_4;

import java.util.Scanner;

/**
 * Description :练习模拟DFA接收转移过程
 * Created by Resumebb
 */
public class DFA {
    public static String state;

    //定义a的转换规则
    public static void tranA(int num){
        while (true) {
            if (state.equals("q0") && num == 0) {
                System.out.println("q0接收" + num + "跳转至q1");
                state = "q1";
                break;
            } else if(state.equals("q0") && num == 1){
                System.out.println("q0接收" + num + "跳转至q0");
                state = "q0";
                break;
            }

            if (state.equals("q1") && num == 0) {
                System.out.println("q1接收" + num + "跳转至q2");
                state = "q2";
                break;
            } else if (state.equals("q1") && num == 1) {
                System.out.println("q1接收" + num + "跳转至q0");
                state = "q0";
                break;
            }

            if (state.equals("q2") && num == 0) {
                System.out.println("q2接收" + num + "跳转至q2");
                break;
            } else {
                System.out.println("q2接收1跳转至q0");
                state = "q0";
                break;
            }
        }
    }

    //定义b的转换规则
    public static void tranB(int num) {
        while (true) {
            if (state.equals("q0") && num == 0) {
                System.out.println("q0接收" + num + "跳转至q1");
                state = "q1";
                break;
            } else if (state.equals("q0") && num == 1) {
                System.out.println("q0接收" + num + "跳转至q0");
                state = "q0";
                break;
            }

            if (state.equals("q1") && num == 0) {
                System.out.println("q1接收" + num + "跳转至q2");
                state = "q2";
                break;
            } else if (state.equals("q1") && num == 1) {
                System.out.println("q1接收" + num + "跳转至q0");
                state = "q0";
                break;
            }

            if (state.equals("q2") && num == 0) {
                System.out.println("q2接收" + num + "跳转至q3");
                state = "q3";
                break;
            } else if(state.equals("q2") && num == 1){
                System.out.println("q2接收1跳转至q0");
                state = "q0";
                break;
            }

            if (state.equals("q3") && num == 0) {
                System.out.println("q3接收" + num + "跳转至q3");
                break;
            } else {
                System.out.println("q3接收1跳转至q3");
                break;
            }
        }
    }


    //定义c的转换规则
    public static void tranC(int num) {
        while (true) {
            if (state.equals("q0") && num == 0) {
                System.out.println("q0接收" + num + "跳转至q1");
                state = "q1";
                break;
            } else if (state.equals("q0") && num == 1) {
                System.out.println("q0接收" + num + "跳转至q0");
                state = "q0";
                break;
            }

            if (state.equals("q1") && num == 0) {
                System.out.println("q1接收" + num + "跳转至q1");
                break;
            } else if (state.equals("q1") && num == 1) {
                System.out.println("q1接收" + num + "跳转至q2");
                state = "q2";
                break;
            }

            if (state.equals("q2") && num == 0) {
                System.out.println("q2接收" + num + "跳转至q1");
                state = "q1";
                break;
            } else if(state.equals("q2") && num == 1){
                System.out.println("q2接收1跳转至q3");
                state = "q3";
                break;
            }

            if (state.equals("q3") && num == 0) {
                System.out.println("q3接收" + num + "跳转至q3");
                break;
            } else {
                System.out.println("q3接收1跳转至q3");
                break;
            }
        }
    }

    public static void myDFA(String str,int num){
        char[] chars = str.toCharArray();
        state = "q0";

        System.out.println("开始接收，初态为q0");
        if(num == 1) {
            for (int i = 0; i < chars.length; i++) {
                tranA(chars[i] - '0');
            }
            if(state.equals("q2")){
                System.out.println("该串满足条件a：以00结尾，被接收");
            }
        }

        if(num == 2) {
            for (int i = 0; i < chars.length; i++) {
                tranB(chars[i] - '0');
            }
            if(state.equals("q3")){
                System.out.println("该串满足条件b：含000子串，被接收");
            }
        }

        if(num == 3) {
            for (int i = 0; i < chars.length; i++) {
                tranC(chars[i] - '0');
            }
            if(state.equals("q3")){
                System.out.println("该串满足条件c：含011子串，被接收");
            }
        }
    }

    public static void main(String[] args) {
        //条件a，以00结尾
        //条件b，连续三个0
        //条件c，含011串的集合
        //4个状态q0,q1,q2,q3初态q0，终态q3
        Scanner in = new Scanner(System.in);
        while(true) {
            System.out.println("1.a");
            System.out.println("2.b");
            System.out.println("3.c");
            int choice = in.nextInt();
            System.out.println("输入0,1字符串：");
            String str = in.next();
            switch (choice) {
                case 1:
                    myDFA(str, choice);
                    break;
                case 2:
                    myDFA(str, choice);
                    break;
                case 3:
                    myDFA(str, choice);
                    break;
                default:
                    System.exit(1);
            }
        }
    }
}