DFA（确定的有穷自动机）
一个确定的有穷自动机M是一个五元组：
M=(K，∑，f，S，Z)
- K是一个有穷集，它的每个元素称为一个状态。
- ∑是一个有穷字母表，它的每一个元素称为一个输入符号，所以也陈∑为输入符号表。
- f是转换函数，是Kx∑->K上的映象。
- S∈K，是唯一的一个初态。
- Z∈K，是一个终态集，终态也称可接受状态或结束状态。
实例代码
- 实现文法
G[S]: S->aU|bVU->bV|aQQ->aQ|bQ
状态图
代码实现
-*- coding: utf-8 -*- ##@author: chlinlearn#@createTime: 2019/4/13 14:12#@fileName: DFAclass DFA(): def __init__(self): #状态集 self.listEdge = [] #初态 self.S = [] #终态 self.Z = [] #判断是否是终态集 def isZ(self,ch): for i in range(0,len(self.Z)) : if self.Z[0] == ch or self.Z[1] == ch: return True else: return False #输入 def input(self): self.S = input("请输入开始符：") self.Z = input("请输入终态集(终集符组成的一个字符串)：") self.Z = self.Z.split(",") print("请输入正规文法以exit结尾：") print("example:S,aZ") while(True): list = [] inStr = input() if inStr=='exit': break inStr = inStr.split(',') # 读取第一个状态集 s = inStr[0] for i in range(0,len(inStr[1])): #ch,ns if len(inStr[1])==2: c = inStr[1][0] n = inStr[1][1] list = [s,c,n] self.listEdge.append(list) elif len(inStr[1])==1: c = inStr[1][0] list = [s, c, self.Z[0]] self.listEdge.append(list) #转换函数 def isNextState(self,s,ch): for i in range(0,len(self.listEdge)): if s == self.listEdge[i][0] and ch == self.listEdge[i][1]: return self.listEdge[i][2] return def judgeDFA(self): print("请输入要判断的字符串:") while(True): #获取字母表 str = input() if '#' in str : print("程序已退出，欢迎下次使用!") return temp = self.S[0] for i in range(0,len(str)): if str[i] is 'a': temp = self.isNextState(temp,'a') elif str[i] is 'b': temp = self.isNextState(temp, 'b') else: break if self.isZ(temp): print("此字符串“属于”该文法！") else: print("此字符串“不属于”该文法！") print("再次判断请输入字符串(退出程序输入#):")if __name__ == '__main__': DFA = DFA() DFA.input() DFA.judgeDFA() 总结
这是我在课程中的一个实验，代码手写并且可运行，是参照一个java版的代码实现的，加上自己的理解和思路把它以python的形式实现。学习别人好的地方，当然也不能照搬别人，不然能够为己用的东西少之又少。通过不同的编程语言把整个思路在理一遍能够加深自己的理解，并且能够得到一样的运行结果，说明自己的理解是对的。最后也附上对应的java版代码，有需求的童鞋可以参考喔！
欢迎访问我的个人网站附件
java版DFA
import java.util.ArrayList;import java.util.List;import java.util.Scanner;class edge { char PriorityState; char ch; char NextState; edge(char p,char c, char n){ PriorityState = p; ch = c; NextState = n; } @Override public String toString() { return "edge [PriorityState=" + PriorityState + ", ch=" + ch + ", NextState=" + NextState + "]"; }}/**DFA的构造*/public class DFA { static List listEdge = new ArrayList ();//状态集 //static HashMap mapEdge = new HashMap<>(); static String S;//初态集 static String Z;//终态集 //flag is here static boolean judeZ(char ch){ for(int j=0; j