題目

將通過以下有窮自動機DFA的圖，識別輸入的字符串，并判斷輸入的字符串是否符合該DFA圖。

圖

分析

輸入aab如何判斷aab是否符合DFA圖?
首先DFA圖肯定是從起始位置(始態(tài)-雙箭頭指向的狀態(tài))-1位置開始執(zhí)行，如果輸入aab，首先從字符串頭開始遍歷，例如a符號在1位置轉(zhuǎn)換為2，a(第二個a)又在2位置狀態(tài)下4，b又在4狀態(tài)下轉(zhuǎn)換為2狀態(tài)，然后字符串遍歷結(jié)束。這個時候我們可以發(fā)現(xiàn)最終DFA的狀態(tài)停在了2狀態(tài)也就是終態(tài)(雙圓圈的狀態(tài))，所以DFA也停止，因次aab可以被DFA識別。
由上發(fā)現(xiàn)只要最終DFA的狀態(tài)為終態(tài)，則該字符串遍能被該DFA識別，例如輸入ab，不能識別最終狀態(tài)為1不是終態(tài)。

特殊情況

輸入的字符串中含有DFA中不存在的符號，例如輸入acb，DFA中無對應(yīng)的c符號，肯定不能識別。

思路

每個狀態(tài)寫一個子程序，相互調(diào)用

上代碼

package BianYi; /** DFA* 本方法只適應(yīng)該DFA圖* I Ia Ib * 1 2 3 0* 2 4 1 1* 3 1 5 0* 4 4 2 0* 5 2 3 1* */ import java.util.Scanner;public class Demo_02 {public static int count=0;//全局計數(shù)器 用于遍歷輸入的字符串public static boolean flag=false;//記錄輸入的字符串是否能被DFA識別，默認為false 全局變量public static void main(String[] args) { Scanner input=new Scanner(System.in);System.out.print("請輸入一串字符串:");String str=input.next();//接收該字符串//先排除簡單的情況 即輸入的字符串中存在某個字符在DFA符號中無對應(yīng) 例如輸入aac c無對應(yīng)(符號為a b)for(int i=0;i<str.length();i++) {//遍歷輸入的字符串 一一對比if(str.charAt(i)!='a'&&str.charAt(i)!='b') {//遍歷的字符在DFA中無對應(yīng)System.out.println("字符串:"+str+"不能被當前的DFA識別!");System.exit(0);//終止程序}}//遍歷輸入的字符串fun_01(str.charAt(count),str);if(flag) {System.out.print("字符串:"+str+"能被當前的DFA識別!");}else {System.out.println("字符串:"+str+"不能被當前的DFA識別!");}}public static boolean funCtion(String str,int t) {if((t==5||t==2)&&count==str.length()) {//如果此時count的值等于字符串的長度-即已經(jīng)遍歷到了最后一個字符了flag=true;//因為此處會調(diào)用fun_02或fun_05，而且fun_02或fun_05為終態(tài)，并且已經(jīng)是遍歷的最后一個字符 所以該字符串能被DFA識別return true;//讓程序不再往下執(zhí)行，不然會造成str.charAt(count)下標越界 }if((t==1||t==3||t==4)&&count==str.length()){flag=false;//因為此處會調(diào)用fun_03||04||01，而且都不為終態(tài)，并且已經(jīng)是遍歷的最后一個字符 所以該字符串不能被DFA識別return true;//讓程序不再往下執(zhí)行，不然會造成str.charAt(count)下標越界}return false; }public static void fun_01(char ch,String str) {//DFA中的1狀態(tài)if(ch=='a') {count++;if(funCtion(str,2)) {return;}fun_02(str.charAt(count),str);}else {//ch=='b'count++;if(funCtion(str,3)) {return;}fun_03(str.charAt(count),str);}}public static void fun_02(char ch,String str) {//DFA中的2狀態(tài)-終態(tài)if(ch=='a') {count++;if(funCtion(str,4)) {return;}fun_04(str.charAt(count),str);}else {//ch=='b'count++;if(funCtion(str,1)) {return;}fun_01(str.charAt(count),str);}}public static void fun_03(char ch,String str) {//DFA中的3狀態(tài)if(ch=='a') {count++;if(funCtion(str,1)) {return;}fun_01(str.charAt(count),str);}else {//ch=='b'count++;if(funCtion(str,5)) {return;}fun_05(str.charAt(count),str);}}public static void fun_04(char ch,String str) {//DFA中的4狀態(tài)if(ch=='a') {count++;if(funCtion(str,4)) {return;}fun_04(str.charAt(count),str);}else {//ch=='b'count++;if(funCtion(str,2)) {return;}fun_02(str.charAt(count),str);}}public static void fun_05(char ch,String str) {//DFA中的5狀態(tài)-終態(tài)if(ch=='a') {count++;if(funCtion(str,2)) {return;}fun_02(str.charAt(count),str);}else {//ch=='b'count++;if(funCtion(str,3)) {return;}fun_03(str.charAt(count),str);}} }

矩陣法-二維數(shù)組

開辟一個二維數(shù)組存在每個狀態(tài)經(jīng)過輸入的符號轉(zhuǎn)后后的狀態(tài)
其中行為狀態(tài)的個數(shù)，列為DFA中的符號個數(shù)+1，最后一列存儲當前的狀態(tài)是否為終態(tài)-01標記 1-為終態(tài)。
為了能使程序通用其他DFA圖，將DFA狀態(tài)之間的相關(guān)關(guān)系寫入了文本中
文本存儲規(guī)則:狀態(tài)標識用阿拉伯數(shù)字表示，符號用字母表示

文本存儲代碼

package BianYi; import java.io.BufferedReader; import java.io.File;//導(dǎo)入包 import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; //讀取文本中的信息 public class FileText {public static int hang;//二維數(shù)組的行數(shù)public static int lie;//二維數(shù)組的列數(shù)private static int i=1;//目的是標記文本中的第一行，因為第一行只有2個數(shù)字，其他行有三個數(shù)字，且均以空格分離private static String path="C:\\Users\\wsg\\Desktop\\編譯原理.txt";//定義文本的名稱，private static File file;//定義一個File(File讀取文件的流)的變量名static {//static 為靜態(tài)代碼塊 程序運行只執(zhí)行一次file = new File(path);if(!file.exists()){try {//捕獲創(chuàng)建、讀取文件時可能發(fā)生的異常file.createNewFile();//文件如果不存在會創(chuàng)建如果存在不會創(chuàng)建} catch (IOException e) {e.printStackTrace();}}}public static int[][] fun(int[][] array) {try {array=readDataFromFile4(file,array); } catch (IOException e) {e.printStackTrace();}//返回權(quán)限return array;}private static int[][] readDataFromFile4(File file,int[][] array) throws IOException {//聲明為staic可用類名訪問 throws表示該方法可能拋出IOException異常BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));//緩沖流-讀取String str = "";//局部變量需要先賦值后引用int count=0;//數(shù)組行數(shù)的統(tǒng)計while((str = reader.readLine())!=null){//如果沒有讀取到最后一行String[] stuInfo= str.split("\\s+");//按照空格正則分割,全部讀取if(i==3) {Demo_01.chArry=stuInfo;}if(i==1) {//第一行存取的是行數(shù)和列數(shù)hang=Integer.valueOf(stuInfo[1]).intValue();//將讀取的行數(shù)轉(zhuǎn)換為整數(shù)類型lie=Integer.valueOf(stuInfo[3]).intValue(); //堆區(qū)開辟數(shù)組空間array=new int[FileText.hang][FileText.lie+1];//聲明一個二維數(shù)組，行數(shù)和列數(shù)從文本中讀取 其中行為狀態(tài)的個數(shù)，列為輸入的符號個數(shù)和初始態(tài)0 1 }if(i>3){//當讀取的行數(shù)大于三時，此時讀取的便是狀態(tài)之間的轉(zhuǎn)換關(guān)系，將其存儲在二維數(shù)組中 array[count][0]=Integer.valueOf(stuInfo[0]).intValue();//存儲某個狀態(tài)經(jīng)過輸入某個字符轉(zhuǎn)換后的狀態(tài)array[count][1]=Integer.valueOf(stuInfo[1]).intValue();//存儲某個狀態(tài)經(jīng)過輸入另一個字符轉(zhuǎn)后的狀態(tài)array[count][2]=Integer.valueOf(stuInfo[2]).intValue();//存儲此時狀態(tài)是否為初始態(tài) 0 1count++;}i++;}return array;//將新開辟的數(shù)組空間返回 便于調(diào)用 不返回會造成訪問數(shù)組為null-即只能在該方法中訪問該數(shù)組} }

矩陣代碼

package BianYi;import java.util.Scanner; /** 文本中的存儲規(guī)則：* 如果DFA的輸入字符在圖中為數(shù)字 則用字母a b c...代替* 如果DFA的狀態(tài)在圖中為字母，則用數(shù)字 1 2 3....代替* */ //有窮自動機DFA程序 public class Demo_01 {public static String[] chArry;//將有DFA的輸入符號存儲在chArry中 例如 a bpublic static void main(String[] args) { Scanner input=new Scanner(System.in);//輸入語句int[][] array = null;//首先定義一個二維數(shù)組，賦值為空 ，在讀取的文件類FileText中賦值array=FileText.fun(array);//傳遞數(shù)組名稱，分配空間，并且讀取文本中的內(nèi)容(各狀態(tài)轉(zhuǎn)換之間的關(guān)系) System.out.print("I ");for(String st:chArry) {//將DFA中的輸入字符打印出來 例如 a bSystem.out.print("I"+st+" ");//空格分割}System.out.println();//換行for(int i=0;i<FileText.hang;i++) {//將二維表中的狀態(tài)關(guān)系全部打印出來 最后一列存儲的是該狀態(tài)是否終態(tài)0-1System.out.print((i+1)+" ");for(int j=0;j<FileText.lie+1;j++) {System.out.print(array[i][j]+" ");//以空格隔開}System.out.println();//換行}System.out.print("請輸入一串字符串:");String str=input.next();//輸入用戶需要識別的字符串 if(funCtion(str,array)) {//調(diào)用funCtion函數(shù)，傳遞用戶輸入的字符串以及存儲各狀態(tài)轉(zhuǎn)換關(guān)系的二維數(shù)組，識別成功返回tureSystem.out.print("字符串:"+str+"可以被該有窮自動機識別");}else {System.out.print("字符串:"+str+"不可以被該有窮自動機識別");}}public static boolean funCtion(String str,int[][] array) {//如果識別成功 返回true 否則返回falsechar[] strArray=str.toCharArray();//將要用戶輸入的字符串轉(zhuǎn)換為char[]類型，便于一個一個比較與轉(zhuǎn)換boolean flag=false;//記錄用戶輸入的字符串與DFA中的字符號是否一模一樣，默認不一樣//第一種情況 輸入的字符在DFA中找不到該字符 例如 DFA中的符號是a b 用戶輸入的是abc c不存在String s;//char[]類型和String[]類型無法比較，需要轉(zhuǎn)換，s存儲strArray[i]for(int i=0;i<strArray.length;i++) {//遍歷用戶輸入的字符串flag=false;//用戶輸入的字符串中每一個字符都默認為在DFA符號中無對應(yīng)s=String.valueOf(strArray[i]);//將字符char類型轉(zhuǎn)換為string類型便于比較for(int j=0;j<chArry.length;j++) {//遍歷DFA中的字符號if(s.equals(chArry[j])) {//如果用戶輸入的字符串中的每一個字符在DFA中有相應(yīng)的字符號對應(yīng)，改變flag的狀態(tài)flag=true;//如果用戶輸入的字符串的每個字符在DFA中都有符號對應(yīng)，則flag一直為truebreak;//只要當前的該單個字符在DFA中有對應(yīng)的字符號就不需要再遍歷當前查找了，退出內(nèi)層循環(huán)}} if(!flag) {//表明用戶輸入的字符串的字符存在與DFA中的字符號不一致;則該字符串肯定不能被該機器識別 則不需要再查找，直接返回falsereturn false;}}int num=1;//如果輸入的是aab a在某一列 則num存儲某一列的DFA轉(zhuǎn)換狀態(tài)for(int i=0;i<strArray.length;i++) {//遍歷用戶輸入的字符串int n=-1;//記錄當前遍歷的字符在二維表中對應(yīng)的列數(shù)(根據(jù)DFA中的符號判斷)s=String.valueOf(strArray[i]);//將字符char類型轉(zhuǎn)換為string類型便于比較for(int j=0;j<chArry.length;j++) {//遍歷DFA中的符號if(s.equals(chArry[j])) {//如果當前遍歷的字符與當前遍歷的DFA中的符號相等n=j;//將s在二維表中的列數(shù)賦予nnum=array[num-1][j];//將要這列中的break;}}if(i==strArray.length-1&&array[num-1][2]==1) {//已經(jīng)掃描完最后一個字符,并且當前該字符所在的狀態(tài)為1 則說名該字符符合該有窮自動機return true;}//System.out.println(n);}return false;} }

結(jié)果

注：此程序?qū)τ谝恍〥FA圖可能識別不了，例如某個狀態(tài)轉(zhuǎn)換為其他狀態(tài)只有一種輸入符號,那么DFA中的其他符號在二維數(shù)組中的存儲值應(yīng)該為空(可置為0，增加判斷即可)。
如下圖，如果輸入abca字符串則結(jié)果為識別不成功，因為第輸入a轉(zhuǎn)換為2狀態(tài)后，2狀態(tài)沒有與b字符有關(guān)的操作。

總結(jié)

以上是生活随笔為你收集整理的有穷自动机【DFA】【编译原理】识别字符串的实现-编程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。