📄 nfatodfa.java
字号:
import java.util.ArrayList;
import java.util.Scanner;
public class NFATODFA {
private static int numState;// 初始的状态个数
private static char input[];// 输入变量
private static int val = 0;// 输入变量的个数
private static state firstSta[][];
private static state newSta[] = new state[60];
private static state lastSta[] = new state[40];
private static state minSta[]=new state[20];
private static int newNumState;
private static int lastNumState;
private static int tempState[] = new int[20];
private static minState minLastSta[];
private static minState minNewSta[];
private static char rep = 'A';
private static ArrayList<state> min=new ArrayList<state>();
private static ArrayList<threeState> three=new ArrayList<threeState>();
public static void main(String args[]) {
/*
* String in; int temp[] = new int[15]; int tempnum = 0; Scanner sc =
* new Scanner(System.in); System.out.println("请输入你输入的变量:"); in =
* sc.nextLine(); val = in.length(); input = new char[val]; input =
* in.toCharArray(); System.out.println("请输入有几个初始状态："); numState =
* sc.nextInt(); firstSta = new state[numState][val];
* System.out.println("初始化（每个状态以－１结束）："); for (int i = 0; i < numState;
* i++) { for (int j = 0; j < val; j++) { while ((temp[tempnum] =
* sc.nextInt()) != -1) { tempnum++; } firstSta[i][j] = new
* state(input[j], tempnum, temp); for (int w = 0; w < 15; w++) {
* temp[w] = 0; } tempnum = 0; } }
*/
initial();
Scanner sc =new Scanner(System.in);
first(0, 'e');
lastNumState = 1;
int index = 0;
int num = lastSta[index].num;
int sta[] = new int[20];
int staNum = 0;
int eTemp[] = new int[10];
while (num > 0 || index != lastNumState) {
for (int j = 0; j < val; j++) {
if (input[j] != 'e') {
staNum = 0;
for (int i = 0; i < num; i++) {
init();
int n = move(lastSta[index].state[i], input[j]);
for (int w = 0; w < n; w++) {
if (!find(tempState[w], sta, staNum)) {
sta[staNum] = tempState[w];
staNum++;
}
}
for (int ww = 0; ww < 10; ww++) {
eTemp[ww] = -1;
}
for (int ww = 0; ww < staNum; ww++) {
eTemp[ww] = tempState[ww];
}
init();
int elen = staNum;
for (int ee = 0; ee < elen; ee++) {
if (eTemp[ee] == -1)
break;
int e = emove(eTemp[ee]);
for (int a = 0; a < e; a++) {
if (!find(tempState[a], sta, staNum)) {
sta[staNum] = tempState[a];
staNum++;
}
}
init();
}
}
state st = new state(' ', staNum, sta);
staNum = 0;
if (!findState(st)) {
// System.out.println(lastNumState);
lastSta[lastNumState] = st;
newSta[newNumState] = st;
newNumState++;
lastNumState++;
} else {
newSta[newNumState] = st;
newNumState++;
}
}
}
index++;
if (index == lastNumState) {
num = -1;
} else {
num = lastSta[index].num;
}
}
int ss = 0;
for (int i = 0; i < lastNumState; i++) {
for (int j = 0; j < lastSta[i].num; j++) {
System.out.print(lastSta[i].state[j] + " ");
}
for (int w = 0; w < 2; w++) {
System.out.print(" ");
for (int e = 0; e < newSta[ss].num; e++) {
System.out.print(newSta[ss].state[e] + " ");
}
ss++;
System.out.print(" ");
}
System.out.println();
}
toMin();
String str;
System.out.println("请输入一个串:");
str=sc.nextLine();
int kk;
char state;
state=three.get(0).begin;
int i;int xx = 0;
for(i=0;i<=str.length();i++){
char ch = 0;
if(i!=str.length()){
ch=str.charAt(i);
}
if(ch=='a'){
kk=0;
}else{
kk=1;
}
if((xx=FindChar(state))!=1){
state=change(kk,state);
}else{
break;
}
}
if(xx==0)System.out.println("错误");
if(i!=str.length()){
System.out.println("错误");
}
if(xx!=0&&i==str.length()){
System.out.println("正确");
}
}
private static char change(int kk, char state) {
char returnchar;
int pos=FindPos(state);
if(kk==0){
returnchar=three.get(pos).mindle;
}else{
returnchar=three.get(pos).end;
}
return returnchar;
}
private static int FindPos(char state) {
for(int i=0;i<three.size();i++){
if(state==three.get(i).begin){
return i;
}
}
return 0;
}
private static int FindChar(char state) {
for(int i=0;i<three.size();i++){
if(state==three.get(i).begin){
return three.get(i).state;
}
}
return 0;
}
private static void minInit() {
minLastSta = new minState[lastNumState];
minNewSta = new minState[newNumState];
for (int i = 0; i < lastNumState; i++) {
minLastSta[i] = new minState(rep, lastSta[i].num, lastSta[i].state,
0);
rep++;
}
for (int i = 0; i < newNumState; i++) {
for (int j = 0; j < lastNumState; j++) {
if (panduan(minLastSta[j].sta, newSta[i].state,
minLastSta[j].numState, newSta[i].num)) {
minNewSta[i] = new minState((char) (j + 'A'),
newSta[i].num, newSta[i].state, j);
}
}
}
int aa = 0;
System.out.println("确定化后的结果为：");
for (int i = 0; i < lastNumState; i++) {
System.out.print(minLastSta[i].replace + " ");
for (int j = 0; j < 2; j++) {
System.out.print(minNewSta[aa].replace + " ");
aa++;
}
System.out.println();
}
}
private static void minFirst() {
int first[]=new int[10];
int fir=0;
int last[]=new int[10];
int las=0;
for(int i=0;i<lastNumState;i++){
if(!find(lastNumState,lastSta[i].state,lastSta[i].num)){
first[fir]=i;
fir++;
}else{
last[las]=i;
las++;
}
}
state st1=new state(' ',fir,first);
state st2=new state(' ',las,last);
min.add(st1);
min.add(st2);
st1=null;
st2=null;
}
private static void toMin() {
minInit();
minFirst();
for(int i=0;i<min.size();i++){
for(int j=0;j<val-1;j++){
if(fen(i,j)){
AddMin(i,j);
i=0;
break;
}
}
}
outPut();
}
private static void outPut(){
System.out.println("最小化后的结果为：");
int aa=0;
char c1=0,c2 = 0,c3 = 0;
System.out.println(" "+"a "+"b ");
for (int i = 0; i < lastNumState; i++) {
// System.out.print(FindMin(minLastSta[i].replace)+" ");
c1=FindMin(minLastSta[i].replace);
//System.out.print(minLastSta[i].replace + " ");
for (int j = 0; j < 2; j++) {
//System.out.print(minNewSta[aa].replace + " ");
//System.out.print(FindMin(minNewSta[aa].replace)+" ");
if(j==0){
c2=FindMin(minNewSta[aa].replace);
}
if(j==1){
c3=FindMin(minNewSta[aa].replace);
}
aa++;
}
threeState th;
if(c1>='D'){
th=new threeState(c1,c2,c3,1);
}else{
th=new threeState(c1,c2,c3,0);
}
three.add(th);
}
guolu();
}
private static void guolu() {
char c1,c2,c3;
for(int i=0;i<three.size();i++){
c1=three.get(i).begin;
c2=three.get(i).mindle;
c3=three.get(i).end;
for(int j=0;j<three.size();j++){
if(i!=j){
if(c1==three.get(j).begin){
if(c2==three.get(j).mindle){
if(c3==three.get(j).end){
three.remove(j);
j--;
}
}
}
}
}
}
for(int i=0;i<three.size();i++){
System.out.println(three.get(i).begin+" "+three.get(i).mindle+" "+three.get(i).end);
}
}
private static char FindMin(char replace) {
for(int i=0;i<min.size();i++){
for(int j=0;j<min.get(i).num;j++){
if((char)(min.get(i).state[j]+'A')==replace){
char ch=(char) (min.get(i).state[0]+'A');
return ch;
}
//System.out.print((char)(min.get(i).state[j]+'A')+" ");
}//System.out.println();
}
return ' ';
}
private static void AddMin(int i,int j) {
int first[]=new int[10];
int fir=0;
int last[]=new int[10];
int las=0;
int flag=minMove(min.get(i).state[0]*j);
for(int w=0;w<min.get(i).num;w++){
int pos=min.get(i).state[w]*j;
if(minMove(pos)==flag){
first[fir]=min.get(i).state[w];
fir++;
}else{
last[las]=min.get(i).state[w];
las++;
}
}
min.remove(i);
state st1=new state(' ',fir,first);
min.add(st1);
state st2=new state(' ',las,last);
min.add(st2);
}
private static boolean fen(int i, int j) {//判断状态i是否能分
int next=minMove(min.get(i).state[0]*j);
for(int w=0;w<min.get(i).num;w++){
int e=min.get(i).state[w]*j;
if(next!=minMove(e))return true;
}
return false;
}
private static int minMove(int j){//返回输入字母后到的下一个状态的下标
int sta=minNewSta[j].num;
for(int w=0;w<min.size();w++){
for(int e=0;e<min.get(w).num;e++){
if(sta==min.get(w).state[e])return e;
}
}
return 0;
}
private static boolean findState(state st) {//
for (int i = 0; i < lastNumState; i++) {
if (panduan(lastSta[i].state, st.state, lastSta[i].num, st.num)) {
return true;
}
}
return false;
}
private static boolean panduan(int[] state, int[] state2, int num, int num2) {// 判断两个状态是否相同
int sum = 0;
if (num != num2)
return false;
else {
for (int i = 0; i < num; i++) {
for (int j = 0; j < num2; j++) {
if (state[i] == state2[j]) {
sum++;
break;
}
}
}
if (sum == num)
return true;
}
return false;
}
private static void init() {
for (int i = 0; i < 20; i++) {
tempState[i] = -1;
}
}
private static void first(int i, char c) {
int pos = index(c);
int firstnum = 0;
int index = 0;
int firststate[] = new int[10];
for (int j = 0; j < 10; j++) {
firststate[j] = -1;
}
firststate[0] = 0;
firstnum++;
int num = firstSta[i][pos].num;
if (pos != -1) {
while (num > 0 || index != firstnum) {
for (int j = 0; j < num; j++) {
if (!find(firstSta[i][pos].state[j], firststate, firstnum)) {
firststate[firstnum] = firstSta[i][pos].state[j];
firstnum++;
}
i = firstSta[i][pos].state[j];
}
index++;
if (firststate[index] != -1) {
num = firstSta[firststate[index]][pos].num;
} else {
num = -1;
}
}
lastSta[0] = new state('0', firstnum, firststate);
} else {
firststate[0] = 0;
lastSta[0] = new state('0', 1, firststate);
}
}
private static int emove(int state) {
int pos = index('e');
int eNumState = 0;
int num = firstSta[state][pos].num;
int index = 0;
while (num > 0 || index != eNumState) {
for (int i = 0; i < num; i++) {
tempState[eNumState] = firstSta[state][pos].state[i];
eNumState++;
}
num = firstSta[tempState[index]][pos].num;
state = tempState[index];
index++;
}
return eNumState;
}
private static int move(int state, char in) {// 从状态state输入in后有几个状态，返回并把状态放到一个全局的数组中
int numState = 0;
int pos = index(in);
int num = firstSta[state][pos].num;
if (num > 0) {
for (int i = 0; i < num; i++) {
tempState[numState] = firstSta[state][pos].state[i];
numState++;
}
return numState;
}
return 0;
}
private static boolean find(int i, int[] firststate, int firstnum) {// 在有firstnum个元素firststate[]的数组中看有没有i
for (int j = 0; j < firstnum; j++) { // 如有返回true
if (i == firststate[j])
return true;
}
return false;
}
private static int index(char c) {
for (int i = 0; i < val; i++) {
if (c == input[i])
return i;
}
return -1;
}
public static void initial() {
val = 3;
input = new char[val];
input[0] = 'a';
input[1] = 'b';
input[2] = 'e';
numState = 8;
firstSta = new state[numState][val];
int temp1[] = { -1 };
int temp2[] = { -1 };
int temp3[] = { 1, -1 };
int temp4[] = { 1, -1 };
int temp5[] = { 1, -1 };
int temp6[] = { 2, -1 };
int temp7[] = { 3, -1 };
int temp8[] = { 4, -1 };
int temp9[] = { -1 };
int temp10[] = { 5, -1 };
int temp11[] = { -1 };
int temp12[] = { -1 };
int temp13[] = { -1 };
int temp14[] = { 5, -1 };
int temp15[] = { -1 };
int temp16[] = { -1 };
int temp17[] = { -1 };
int temp18[] = { 6, -1 };
int temp19[] = { 6, -1 };
int temp20[] = { 6, -1 };
int temp21[] = { 7, -1 };
int temp22[] = { -1 };
int temp23[] = { -1 };
int temp24[] = { -1 };
firstSta[0][0] = new state('a', 0, temp1);
firstSta[0][1] = new state('b', 0, temp2);
firstSta[0][2] = new state('e', 1, temp3);
firstSta[1][0] = new state('a', 1, temp4);
firstSta[1][1] = new state('b', 1, temp5);
firstSta[1][2] = new state('e', 1, temp6);
firstSta[2][0] = new state('a', 1, temp7);
firstSta[2][1] = new state('b', 1, temp8);
firstSta[2][2] = new state('e', 0, temp9);
firstSta[3][0] = new state('a', 1, temp10);
firstSta[3][1] = new state('b', 0, temp11);
firstSta[3][2] = new state('e', 0, temp12);
firstSta[4][0] = new state('a', 0, temp13);
firstSta[4][1] = new state('b', 1, temp14);
firstSta[4][2] = new state('e', 0, temp15);
firstSta[5][0] = new state('a', 0, temp16);
firstSta[5][1] = new state('b', 0, temp17);
firstSta[5][2] = new state('e', 1, temp18);
firstSta[6][0] = new state('a', 1, temp19);
firstSta[6][1] = new state('b', 1, temp20);
firstSta[6][2] = new state('e', 1, temp21);
firstSta[7][0] = new state('a', 0, temp22);
firstSta[7][1] = new state('b', 0, temp23);
firstSta[7][2] = new state('e', 0, temp24);
}
}
class state {
char input;
int state[];// 存放状态的种类
int num;// 有几个状态
public state(char input, int num, int state[]) {
this.state = new int[num];
this.num = num;
this.input = input;
for (int i = 0; i < num; i++) {
this.state[i] = state[i];
}
}
}
class threeState{
char begin;
char mindle;
char end;
int state;
public threeState(char begin,char mindle,char end,int state){
this.begin=begin;
this.mindle=mindle;
this.end=end;
this.state=state;
}
}
class minState {
char replace;
int sta[];
int numState;//有几个状态
int num;//确定后的第几个状态
public minState(char replace, int numState, int state[], int num) {
this.replace = replace;
this.numState = numState;
sta = new int[numState];
this.num = num;
for (int i = 0; i < numState; i++) {
this.sta[i] = state[i];
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -