2.2有限自动机

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

有限自动机 FA

工作状态

  • 读读头所指向的字符
  • 据当前状态和读的字符改变自动机的状态
  • 将读头向前移动

    确定的有限自动机 DFA

M=(Q,∑,f,q0,Z)

  • 一个确定的有限自动机M是一个五元组
  • Q:状态的有限集合，每个元素qi(qi∈Q)称为一个状态
  • ∑:输入字符的有限集合，有穷字符表
  • f:状态转换函数-从Q×∑→Q的映射 // f(p,a)=q q称为p的后继状态
  • q0:M的唯一初态 q0∈Q
  • Z:M的终态集(接受状态集) Z是Q的子集

DFA-状态转换图-状态转换表 转化

  • DFA
    • 2-2DFA
  • 状态转换图
    • 2-2-2
    • 2-2-21
  • 状态转换表

DFA的识别机制

  • 有限自动机M=(Q,∑,f,q0,Z)接受字符表∑上的字符串ω=w1w2…wn的意义

若存在Q中的状态序列p0,p1…pn，满足下列条件：

  1. p0=q0
  2. f(pi,wi+1)=pi+1, i=0,1…n-1
  3. pn属于Z

则M接受ω

  • 若M初态和终态相同，则空串被M所识别
  • 确定的有限自动机M识别的字符串全体称为M识别的语言，记为L(M)
  • L(M) = { |    *  f(q0, ) Z }
    • 设＝a1a2an-1an，
    • f(q0,)=f(f(f(f(q0,a1,),a2),,an-1),an)

确定的有限自动机等价

  • 设有DFA M和DFA M’，若有L(M)=L(M’)，则称M和M’等价
  • 对于任意字，在DFA中有且仅有唯一路径

设计DFA

非确定的有限自动机 NFA

M=(Q,∑,f,q0,Z)

  • 一个非确定的有限自动机M是一个五元组
  • Q:状态的有限集合，每个元素qi(qi∈Q)称为一个状态
  • ∑:输入字符的有限集合，有穷字符表
  • q0:M的唯一初态 q0∈Q
  • Z:M的终态集(接受状态集) Z是Q的子集
  • f:状态转换函数-从Q×(∑∪{ε})→2^Q的映射 // 后继状态不唯一

NFA&DFA区别

  • NFA：f=Q×(∑∪{ε})→2^Q
  • DFA：f=Q×∑→Q
  • NFA对字的识别验证的路径可能不唯一

设计NFA

子集法

  • I是NFA M’状态集Q的一个子集。

  • 则ε-closure(I)为 ：

    1. qi∈I，qi ∈ε-closure(I)；
    2. qi ∈I，从qi出发经过任意条ε弧而能到达的任何状态qj ，qj ∈ε-closure(I)。

  • 状态集ε-closure(I) 即为在I中的状态下，不输入任何字符所能到达的状态的全体并包含I中的状态，就是状态集I的ε闭包

  • 状态集合I的a弧转换Ia

  • Ia=ε-closure(f (ε-closure(I) ，a))。

NFA确定化

  • 对任何一个NFA M,都存在一个DFA M’，使L(M)=L(M’) => M=M’

  • 子集法

    1. 消去ε弧
    2. 解决映射不唯一的问题

  • 过程

  • 例

DFA的化简

  • 所谓DFA M的化简是指寻找一个状态数最小的DFA M’(规约或最小的DFA M’),使L(M)=L(M’)

  • 如果DFA M’既没有无关状态，且没有彼此等价的状态,则称DFA M是规约的，即最小的DFA M

  • 思想

    • 通过删除无关状态，合并等价状态的规约过程，直至得到规约机(最小的DFA)

  • 删除无关状态的算法

    无关状态:如果从DFA M的初态开始，任何输入序列都不能到达的那些状态称为无关状态。

  • 合并等价状态方法:划分法

    设DFA M的两个不同状态 q1，q2，如果对任意输入字符串ω，从q1，q2状态出发，总是同时到达接收状态或拒绝状态之中，称q1，q2是等价的。
    如果两个状态不等价，则称q1，q2是可区别的（q1，q2被ω所区别）。

    • 实现

    • 例子