一个确定有限自动机(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 tranA(chars[i] - '0');
}
if(state.equals("q2")){
System.out.println("该串满足条件a:以00结尾,被接收");
}
}
if(num == 2) {
for (int i = 0; i tranB(chars[i] - '0');
}
if(state.equals("q3")){
System.out.println("该串满足条件b:含000子串,被接收");
}
}
if(num == 3) {
for (int i = 0; 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);
}
}
}
}