【程序语言与编译】 有限自动机（DFA与NFA）

适合读者软考中级备考同学阅读时间3.5分钟内容DFA与NFA的定义、区别、等价转换、例题1. 什么是有限自动机有限自动机Finite Automaton, FA是一种识别器用于判断一个输入字符串是否属于某正规集。它是词法分析的核心工具也是软考中常考的内容。有限自动机分为两类确定型有限自动机DFADeterministic Finite Automaton非确定型有限自动机NFANondeterministic Finite Automaton二者识别能力等价任何NFA都可以转换为等价的DFA但DFA更适合实际实现NFA更方便人工构造。2. DFA确定型有限自动机2.1 形式定义DFA是一个五元组M(Q,Σ,δ,q0,F)M (Q, \Sigma, \delta, q_0, F)M(Q,Σ,δ,q0​,F)其中QQQ有限的状态集合Σ\SigmaΣ有限的输入字母表δ\deltaδ确定的转移函数δ:Q×Σ→Q\delta: Q \times \Sigma \rightarrow Qδ:Q×Σ→Q每个状态和输入符号唯一确定下一个状态q0q_0q0​初始状态q0∈Qq_0 \in Qq0​∈QFFF终止状态集合F⊆QF \subseteq QF⊆Q2.2 特点对于当前状态和输入符号有且只有一个下一状态。状态转移图中每个结点的出边在相同输入符号上最多一条。实现简单模拟运行速度快。2.3 示例DFA识别所有以01结尾的二进制串状态转移表状态输入0输入1AABBCBCAB初始状态AAA终止状态CCC。3. NFA非确定型有限自动机3.1 形式定义NFA同样是一个五元组M(Q,Σ,δ,q0,F)M (Q, \Sigma, \delta, q_0, F)M(Q,Σ,δ,q0​,F)区别在于转移函数δ\deltaδQ×(Σ∪{ε})→2QQ \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^QQ×(Σ∪{ε})→2Q映射到状态集合的子集而不是单个状态。3.2 特点从当前状态读入一个符号后可能进入多个下一状态不确定性。允许ε\varepsilonε转移不读入任何符号即可跳转。只要存在一条路径能到达终止状态NFA就接受该输入串。3.3 示例NFA识别以01结尾的串比DFA更简洁状态图A→0AA \xrightarrow{0} AA0​AA→1AA \xrightarrow{1} AA1​AA→0BA \xrightarrow{0} BA0​BB→1CB \xrightarrow{1} CB1​CC为终止。注意从A读0既可以留在A也可以到B这是非确定性。4. DFA与NFA对比表对比项DFANFA下一状态唯一多个或零个ε\varepsilonε转移不允许允许状态数较多较少通常构造难度较难手动容易直观模拟运行快无回溯慢需回溯或子集构造识别能力相同相同等价5. NFA转DFA子集构造法核心思想将NFA的一个状态子集看作DFA的一个状态。算法步骤从初始状态出发求其ε\varepsilonε闭包即通过任意步ε\varepsilonε转移能到达的所有状态集合作为DFA的初始状态。对每个DFA状态即一个NFA状态集对于每个输入符号aaa计算该状态集中所有状态读入aaa后能到达的状态的ε\varepsilonε闭包得到新的状态子集。若新子集未出现过则添加到DFA中。重复直到没有新状态产生。若某个DFA状态包含至少一个NFA的终止状态则该DFA状态为终止状态。简例NFA见3.3示例初始状态集{A}\{A\}{A}的ε\varepsilonε闭包还是{A}\{A\}{A}。读0从A出发0可到A和B →{A,B}\{A,B\}{A,B}闭包无ε\varepsilonε→{A,B}\{A,B\}{A,B}。读1从A出发1可到A →{A}\{A\}{A}。对新状态{A,B}\{A,B\}{A,B}读0从A到A,B从B无0转移 →{A,B}\{A,B\}{A,B}读1从A到A从B到C →{A,C}\{A,C\}{A,C}。{A,C}\{A,C\}{A,C}读0从A到A,BC无0 →{A,B}\{A,B\}{A,B}读1从A到AC无1 →{A}\{A\}{A}。最终DFA包含状态{A}\{A\}{A}初始{A,B}\{A,B\}{A,B}{A,C}\{A,C\}{A,C}终止。可重命名。6. 经典例题题目1已知NFA的状态转换图如下文字描述状态A初始A读0可到A和BA读1到AB读1到CC无转移。求该NFA对应的DFA。解即为5中的示例答案为DFA状态集和转移。题目2以下关于DFA和NFA的描述正确的是 。A. NFA的识别能力比DFA强B. DFA不允许ε\varepsilonε转移C. 每个NFA都可以转换为等价的DFAD. DFA的状态数一定小于NFA答案B和CA错能力等价D错DFA状态数可能指数增长题目3给定DFA初始状态0终止状态2转移0读a到10读b到01读a到21读b到12读a到22读b到2。判断字符串aaba是否被接受。解从0开始a→1a→2b→2a→2。最终在状态2终止接受。答案接受7. 记忆口诀DFA确定唯一路NFA多路可空跳。子集构造换等价识别能力一样高。8. 给备考同学的一句话有限自动机是词法分析的数学模型。软考中常见给定状态图或转移表判断DFA/NFA类型。NFA转DFA子集构造法只需理解概念很少要求完整手工计算复杂例子。模拟DFA运行判断字符串是否被接受。记住DFA实现简单NFA构造方便二者等价。理解子集构造法的思想考试时遇到相关选择题就能应对。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #有限自动机 #DFA #NFA #词法分析