精华内容
下载资源
问答
  • 有限自动机

    2015-10-27 08:40:24
    有限自动机 ppt 关于图灵机 还有有限状态自动机 确定的有限状态自动机
  • 确定有限自动机和非确定有限自动机概念及变换,语法图与自动机
  • 确定有限自动机DFA&非确定有限自动机NFA Part 1_自动机介绍:有穷自动机(finite state automata)是一个识别器,它对每个输入的字符做识别和判断,以确定其能到达的最终状态或状态集和路径,有穷自动机分为两类,...

    确定有限自动机DFA&非确定有限自动机NFA

    Part 1_自动机介绍:

    有穷自动机(finite state automata)是一个识别器,它对每个输入的字符做识别和判断,以确定其能到达的最终状态或状态集和路径,有穷自动机分为两类,即不确定的有穷自动机NFA和确定的有穷自动机DFA[1].

    例子1:红绿灯系统: G(绿灯亮了的状态);R(红灯亮的状态);Y(黄灯亮的状态)

    例子2:零售机(vending machine)。它接受五角和一块的硬币,但是要至少积累到3元才能按下选择,并且只有作出选择才会执行。所以从初始state开始,每一个状态之后都有两种选择:要么投5角,要么投1元;每次投完都会到达一个新的状态(目前投入硬币总数)。


    Part 2_专用名词解释:

    在介绍DFA和NFA之前,先介绍几个名词:

    alphabet 字母表:符号的有限集合。 记作: Σ 例如:{a, b, ... , x, m}

    strings 字符串: 通常我们用到建立在 Σ 上的字符串:有穷的符号序列。 例如:对于 Σ={a, b, c}, “ababc” 就是 Σ 上的一个字符串。

    languages 语言:通常我们也只用建立在Σ上的语言,语言就是多个字符串的集合。例如 {ababc, ab, bc, ..}

    sentences 句子:句子是语言集合中元素(字符串)的另一个称呼。

    notation 符号:Σ* 是Σ上所有可能的字符串的集合。例如:Σ={a, b}, Σ* = { ε, a, b, ab, ba}

    Part 3_DFA:

    DFA: Deterministic Finite State 确定的有穷自动机

    1. 第一种计算模型:用来解决对一个已知字符串,看它是否能被某个自动机所接受。
    2. 一个DFA有有穷个状态(state),主要分为三种状态:
    • 初始状态(initial state):自动机开始的状态;
    • 终止状态(final state):一个DFA至少有一个终止状态;
    • 中间状态。

    「状态间转换的公式: 状态 x 输入字符 --> 状态」

    3. DFA的定义:(共5部分)

    A = ( Σ, S, s0, F, N )

    • Σ: 输入字母表(alphabet),是一个输入字符的集合。
    • S:状态的集合
    • s0: 初始状态
    • F:终止状态集合 F ⊆ S
    • N:转换公式 N:S×Σ → S

    4. 「“确定”意味着对于一个输入字符,只有唯一的可能状态」

    5. 例子:

    从上图我们可以得到一个转换公式表格:

    单步表示: N (S0, 0): 是自动机从s0状态,读取符号0之后的状态。从表格中可以看出N (S0, 0) = S1.

    多步表示: N (N (S0, 0), 1) = S2.

    ** 重要定理: 对S中所有的状态s,所有 Σ*中的字符串 α,β, 有:

    N*(s, αβ) = N*(N*(s, α), β)。

    6. 最终状态公式 (eventual state function):

    从任意一个状态,经过一个string到达的最终状态的所有可能情况。

    表达为: N* : S × Σ* → S

    7. 如果一个字符串从一个DFA的初始状态出发,能在某一个终止状态结束,那这个字符串就被这个DFA所接受。所有的这种字符串的集合就是这个自动机的语言(language)。

    8. 自动机等同:如果两个自动机接受相同的语言,就说这两个自动机相等。

    9. 状态等同:如果对于所有的输入字符串 w, 有并且只有

    N*(Sj,w) ∈ F 并且N*(Sk,w) ∈ F (F是final state的集合)

    注意,一个非终止状态永远不可能与一个终止状态等同。

    10. 状态消除

    1)等同状态消除:如果两个状态等同,那么其中一个可以被消除,来简化自动机。

    以上面9.为例,Sk可以被消除, 消除Sk之后的新的自动机A' = (Σ, S', s0, F', N' )

    S' = S-Sk

    F‘ = F-Sk

    N‘(s,w)= (if N(s,w)=Sk then Sj

    else N(s,w))

    (注意这里有个前提,Sk不能是初始状态,因为初始状态不能被消除。)

    2) 无法到达的状态消除:如果一个状态是无法从初始状态到达的,那么它可以被消除,例如下图的S3。

    11. 这里有一个传统的分组算法,可以用来最简化自动机,这里不做详细介绍。

    Part 4_NFA:

    1. NFA(Non-Deeterministic Finite State Automata)不确定的有穷自动机: 对一个输入符号,有两种或两种以上可能对状态,所以是不确定的。

    2. NFA可以转换成DFA,NFA和DFA的主要区别在于[1]:

    1)DFA没有输入空串之上的转换动作;

    2)对于DFA,一个特定的符号输入,有且只能得到一个状态,而NFA就有可能得到一个状态集;

    3. NFA的定义:(共5部分)

    A = ( Σ, S, s0, F, N ) (具体表示内容与DFA相同)

    4. 对于输入字符串w,如果满足 ∃ s ∈F. R*(s0, w, s), 那么w是被自动机所接受的。 所有被该自动机接受的字符串就是这个自动机的语言

    5. 定理:如果语言L被一个NFA所接受,那么一定存在一些DFA也接受这一语言L。


    展开全文
  • 确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ; 确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ; 确定性有限自动机 给定一个输入 , 其输出时唯一的 ; 非确定性...





    一、非确定性有限自动机 组成部分



    非确定性有限自动机 : Nondeterministic Finite Automaton , NFA ;


    QQ 状态集 : 有限个状态 ;

    Σ\Sigma 字母表 : 有限个字符集 , 长度有限的字符串 ;

    δ\delta 转移函数 ( 指令集 ) : δ\delta 称为转移函数 ; 基于当前的 自动机 的某个状态 , 将字符集 输入到自动机中 , 该自动机转换成一个或多个状态 , 这个转换就是通过 δ\delta 转换函数进行的 , 使用公式描述 Q×Σε2QQ \times \Sigma_{\varepsilon} \to 2^Q ;

    q0q_0 起始状态 : 是自动机的开始状态 ;

    FF 接受状态集 : FF 是 可接受状态 , 是 QQ 的子集 , 记做 FQF \subseteq Q , FF 可接受状态相对的是不可接受状态 ;





    二、确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 等价



    确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ;


    确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ;


    确定性有限自动机 给定一个输入 , 其输出时唯一的 ;

    非确定性有限自动机的定义 包含 确定性有限自动机的 定义中 ;


    NFA 的后继状态 可以是 00 个 , 11 个 或 多个 , DFA 每个状态只能有 11 个后继状态 ;

    确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA ) ;


    可以证明非确定性有限自动机 ( NFA ) , 必定有一个 确定性有限自动机 ( DFA ) 与其等价 ;





    三、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA ) 示例



    正确的图片 :
    在这里插入图片描述

    下图绘制错误 , 暂时作废 , 看第一张图片 ;
    在这里插入图片描述
    上图绘制错误 , 暂时作废 , 看第一张图片 ;

    字符集 : Σ={a,b}\Sigma = \{a, b\}


    将上述 非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA ) , 需要将非确定性消除 , 只剩下确定性因素 ;


    转换过程 使用特定算法实现 , 下面会详细描述该算法 ;


    表格 : 绘制一个表格 , 表格列分别是 a,ba, b , 确定性有限自动机可以使用表格来表示 ;


    开始状态分析 : 上述非确定性有限自动机开始状态 11 , 但是有一个 ε\varepsilon 空字符 , 指向 33 状态 , 读取到空字符 ε\varepsilon 后会无条件跳转到 后继状态 33 , 因此 该自动机有 22 个开始状态 ;

    开始状态确定 : {1,3}\{1 , 3\} , 将开始状态看做一个集合 , 将这两个状态组成的集合看做一个新的状态 ,


    aa bb
    {1,3}\{1, 3 \}




    四、NFA 转 DFA ( 1 ) 开始状态 读取 aa 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \}

    表格 第 22 行 第 22 列 :


    1 . 数值含义 : 该位置的含义是 {1,3}\{1 , 3\} 开始状态下 , 读取 字符 aa 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 11 状态下读取 aa 字符后的后继状态 , 33 状态下读取 aa 字符后的后继状态 ;


    11 状态下读取 aa 字符是空集 {}\{ \varnothing \} ;

    33 状态下读取 aa 字符后继状态是 11 , 此时 11 状态又可以无条件跳转到 33 状态 , 可以与 11 状态并列 , 此时 33 状态 读取 aa 字符的后继状态是 {1,3}\{1, 3\} ;


    3 . 后继状态取并集 : 将上述的 两个 后继状态 {}\{ \varnothing \}{1,3}\{1, 3\} , 取并集 , 就是 {1,3}\{1 , 3\} 状态下读取 aa 字符的后继状态 , 取并集的结果是 {1,3}\{1, 3\} ;


    22 行 第 22 列 的 值是 {1,3}\{1, 3\} , 代表 {1,3}\{1 , 3\} 状态下读取 字符 aa , 后继状态是 {1,3}\{1 , 3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\}




    五、NFA 转 DFA ( 2 ) 开始状态 读取 bb 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\}

    表格 第 22 行 第 33 列 :


    1 . 数值含义 : 该位置的含义是 {1,3}\{1 , 3\} 开始状态下 , 读取 字符 bb 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 11 状态下读取 bb 字符后的后继状态 , 33 状态下读取 bb 字符后的后继状态 ;


    11 状态下读取 bb 字符 后继状态是 {2}\{ 2 \} ;

    33 状态下读取 bb 字符后继状态是 {}\{ \varnothing \} 空集 ;


    3 . 后继状态取并集 : 将上述的 两个 后继状态 {2}\{2\}{}\{ \varnothing \} , 取并集 , 就是 {1,3}\{1 , 3\} 状态下读取 bb 字符的后继状态 , 取并集的结果是 {2}\{2\} ;


    22 行 第 33 列 的 值是 {2}\{2\} , 代表 {1,3}\{1 , 3\} 状态下读取 字符 bb , 后继状态是 {2}\{2\} 状态 ;


    开始集合 {1,3}\{1, 3 \} , 读取 aa 字符 , 读取 bb 字符的后继状态 , 分析完毕 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}




    六、NFA 转 DFA ( 3 ) 选取第二个状态进行分析



    选取原则 : 没有出现过的状态 , 都要进行分析 ;

    开始分析后续状态 , 第一个后继状态是 {1,3}\{1,3\} 就是开始状态 , 已经分析过了 , 不再考虑 , 开始分析 {2}\{2\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\}




    七、NFA 转 DFA ( 4 ) 22 状态读取 aa 字符后续状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\}

    表格 第 33 行 第 22 列 :


    1 . 数值含义 : 该位置的含义是 {2}\{2\} 开始状态下 , 读取 字符 aa 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 {2}\{2\} 状态下读取 aa 字符后的后继状态 是 {2,3}\{2 , 3\} ;


    3 . 后继状态 : 33 行 第 22 列 的 值是 {2,3}\{2,3\} , 代表 {2}\{2\} 状态下读取 字符 aa , 后继状态是 {2,3}\{2,3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\}




    八、NFA 转 DFA ( 5 ) 22 状态读取 bb 字符后续状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\}

    表格 第 33 行 第 33 列 :


    1 . 数值含义 : 该位置的含义是 {2}\{2\} 开始状态下 , 读取 字符 bb 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 {2}\{2\} 状态下读取 bb 字符后的后继状态 是 {3}\{ 3\} ;


    3 . 后继状态 :33 行 第 33 列 的 值是 {3}\{3\} , 代表 {2}\{2\} 状态下读取 字符 bb , 后继状态是 {3}\{3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}




    九、NFA 转 DFA ( 6 ) 选取后续需要分析的状态



    选取原则 : 没有出现过的状态 , 都要进行分析 ;


    {2,3}\{2,3\}{3}\{3\} 状态都是分析 {2}\{2\} 状态的后继状态时新出现的状态 , 因此将这两个状态加入表格中 , 进行分析 ;


    加入两个状态后 , 最新表格如下 :


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\}
    {3}\{3\}

    下面开始分析后续内容 ;





    十、NFA 转 DFA ( 7 ) {2,3}\{2,3\} 状态 读取 aa 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\}
    {3}\{3\}

    表格 第 44 行 第 22 列 :


    1 . 数值含义 : 该位置的含义是 {2,3}\{2 , 3\} 开始状态下 , 读取 字符 aa 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 22 状态下读取 aa 字符后的后继状态 , 33 状态下读取 aa 字符后的后继状态 ;


    22 状态下读取 aa 字符 后继状态是 {2,3}\{ 2 , 3 \} ;

    33 状态下读取 aa 字符后继状态是 {1,3}\{1 , 3\} , 这里只要能到达状态 11 , 便需要无条件跳转到状态 33 , 因为 11 状态下读取空字符 ε\varepsilon 即可转为 33 状态 , 因此 1,31,3 状态并列 ;


    3 . 后继状态取并集 : 将上述的 两个 后继状态 {2,3}\{2, 3\}{1,3}\{ 1,3 \} , 取并集 , 就是 {2,3}\{2 , 3\} 状态下读取 aa 字符的后继状态 , 取并集的结果是 {1,2,3}\{1,2,3\} ;


    44 行 第 22 列 的 值是 {1,2,3}\{1,2,3\} , 代表 {2,3}\{2 , 3\} 状态下读取 字符 aa , 后继状态是 {1,2,3}\{1,2,3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\}
    {3}\{3\}




    十一、NFA 转 DFA ( 8 ) {2,3}\{2,3\} 状态 读取 bb 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\}
    {3}\{3\}

    表格 第 44 行 第 33 列 :


    1 . 数值含义 : 该位置的含义是 {2,3}\{2 , 3\} 开始状态下 , 读取 字符 bb 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 22 状态下读取 bb 字符后的后继状态 , 33 状态下读取 bb 字符后的后继状态 ;


    22 状态下读取 bb 字符 后继状态是 {3}\{ 3 \} ;

    33 状态下读取 bb 字符后继状态是 {}\{\varnothing\} ;


    3 . 后继状态取并集 : 将上述的 两个 后继状态 {3}\{3\}{}\{ \varnothing \} , 取并集 , 就是 {2,3}\{2 , 3\} 状态下读取 bb 字符的后继状态 , 取并集的结果是 {3}\{3\} ;


    44 行 第 33 列 的 值是 {3}\{3\} , 代表 {2,3}\{2 , 3\} 状态下读取 字符 bb , 后继状态是 {3}\{3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\}




    十二、NFA 转 DFA ( 9 ) 选取后续需要分析的状态



    选取原则 : 没有出现过的状态 , 都要进行分析 ;


    {1,2,3}\{1 ,2,3\} 是 新出现的状态 , 因此将这两个状态加入表格中 , 进行分析 ;

    加入该状态后 , 最新表格如下 :


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\}
    {1,2,3}\{1,2,3\}

    下面开始分析后续内容 ;





    十三、NFA 转 DFA ( 10 ) {3}\{3\} 状态 读取 aa 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\}
    {1,2,3}\{1,2,3\}

    表格 第 55 行 第 22 列 :


    1 . 数值含义 : 该位置的含义是 {3}\{ 3\} 开始状态下 , 读取 字符 aa 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 33 状态下读取 aa 字符后的后继状态 是 {1,3}\{1,3\}



    3 . 后继状态 : 55 行 第 22 列 的 值是 {1,3}\{1,3\} , 代表 {3}\{3\} 状态下读取 字符 aa , 后继状态是 {1,3}\{1,3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\}
    {1,2,3}\{1,2,3\}




    十四、NFA 转 DFA ( 11 ) {3}\{3\} 状态 读取 bb 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\}
    {1,2,3}\{1,2,3\}

    表格 第 55 行 第 33 列 :


    1 . 数值含义 : 该位置的含义是 {3}\{ 3\} 开始状态下 , 读取 字符 bb 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 33 状态下读取 bb 字符后的后继状态 是 {}\{\varnothing \}



    3 . 后继状态 : 55 行 第 33 列 的 值是 {}\{\varnothing \} , 代表 {3}\{3\} 状态下读取 字符 bb , 后继状态是 {}\{\varnothing \} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\} {}\{\varnothing \}
    {1,2,3}\{1,2,3\}




    十五、NFA 转 DFA ( 12 ) {1,2,3}\{1,2,3\} 状态 读取 aa 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\} {}\{\varnothing \}
    {1,2,3}\{1,2,3\}

    表格 第 66 行 第 22 列 :


    1 . 数值含义 : 该位置的含义是 {1,2,3}\{1,2 , 3\} 开始状态下 , 读取 字符 aa 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 11 状态下读取 aa 字符后的后继状态 , 22 状态下读取 aa 字符后的后继状态 , 33 状态下读取 aa 字符后的后继状态 ;


    11 状态下读取 aa 字符 后继状态是 {}\{ \varnothing \} ;

    22 状态下读取 aa 字符 后继状态是 {2,3}\{ 2 , 3 \} ;

    33 状态下读取 aa 字符后继状态是 {1,3}\{1 , 3\} , 这里只要能到达状态 11 , 便需要无条件跳转到状态 33 , 因为 11 状态下读取空字符 ε\varepsilon 即可转为 33 状态 , 因此 1,31,3 状态并列 ;


    3 . 后继状态取并集 : 将上述的 33 个 后继状态 {}\{ \varnothing \} , {2,3}\{2, 3\}{1,3}\{ 1,3 \} , 取并集 , 就是 {1,2,3}\{1 , 2 , 3\} 状态下读取 aa 字符的后继状态 , 取并集的结果是 {1,2,3}\{1,2,3\} ;


    66 行 第 22 列 的 值是 {1,2,3}\{1,2,3\} , 代表 {1,2,3}\{1 , 2 , 3\} 状态下读取 字符 aa , 后继状态是 {1,2,3}\{1,2,3\} 状态 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\} {}\{\varnothing \}
    {1,2,3}\{1,2,3\} {1,2,3}\{1,2,3\}




    十六、NFA 转 DFA ( 13 ) {1,2,3}\{1,2,3\} 状态 读取 bb 字符 后继状态分析



    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\} {}\{\varnothing \}
    {1,2,3}\{1,2,3\} {1,2,3}\{1,2,3\}

    表格 第 66 行 第 33 列 :


    1 . 数值含义 : 该位置的含义是 {1,2,3}\{1,2 , 3\} 开始状态下 , 读取 字符 bb 之后的后续状态集 ;


    2 . 后继状态分析 : 分别考虑 11 状态下读取 bb 字符后的后继状态 , 22 状态下读取 bb 字符后的后继状态 , 33 状态下读取 bb 字符后的后继状态 ;


    11 状态下读取 bb 字符 后继状态是 {2}\{ 2\} ;

    22 状态下读取 aa 字符 后继状态是 {3}\{ 3 \} ;

    33 状态下读取 aa 字符后继状态是 {}\{\varnothing\} ;


    3 . 后继状态取并集 : 将上述的 33 个 后继状态 {2}\{2\} , {3}\{ 3 \}{}\{ \varnothing \} , 取并集 , 就是 {1,2,3}\{1 , 2 , 3\} 状态下读取 bb 字符的后继状态 , 取并集的结果是 {2,3}\{2,3\} ;




    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\} {}\{\varnothing \}
    {1,2,3}\{1,2,3\} {1,2,3}\{1,2,3\} {2,3}\{2,3\}




    十七、NFA 转 DFA ( 14 ) 结果分析



    1 . 消除不确定性 : 下面的表格就是将 非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA ) 的结果 , 将状态集合当做一个新的状态 , 新状态由之前的 NFA 中的不同状态组合而来 , 由此消除不确定性 ;


    aa bb
    {1,3}\{1, 3 \} {1,3}\{1 , 3\} {2}\{2\}
    {2}\{2\} {2,3}\{2,3\} {3}\{3\}
    {2,3}\{2,3\} {1,2,3}\{1,2,3\} {3}\{3\}
    {3}\{3\} {1,3}\{1,3\} {}\{\varnothing \}
    {1,2,3}\{1,2,3\} {1,2,3}\{1,2,3\} {2,3}\{2,3\}

    2 . 定义开始状态 : {1,3}\{1, 3 \} 定义成开始状态 ;


    3 . 定义接收状态 : 原来的 非确定性有限自动机 ( NFA ) 中 11 是接受状态 , 在新的 确定性有限自动机 ( DFA ) 中 , 只要状态集合中包含 11 , 那么该状态集合就是 接受状态 , 因此这里 {1,3}\{1, 3 \}{1,2,3}\{1,2,3\} 两个状态集 代表的 新状态 是接受状态 ;

    展开全文
  • 提出了概率有限自动机的覆盖的定义,然后利用代数的方法讨论了概率有限自动机的全直积(限制直积)、级联积、圈积、并积的覆盖关系,证明了2个概率有限自动机的级联积(限制直积)覆盖它们的圈积(全直积),概率有限自动机的...
  • 我看一本书里说the number of states in the equivalent deterministic fsa...可是,我记得不确定性的有限自动机转成等价的确定性的有限自动机的时候,状态会减少呀,感觉应该是确定性的有限自动机的状态数更少,求解答
  • 有限自动机试题

    2013-10-22 14:54:55
    有限自动机试题 陈文宇 电子科技大学
  • 软考之有限自动机

    千次阅读 2018-08-15 15:02:50
    什么是有限自动机有限自动机可分为确定的有限自动机(DFA)和不确定的有限自动机(BFA)。其中确定的有限状态自动机和不确定的有限状态自动机最大的区别是它们的转移函数不同,确定有限状态自动机对每一个可能的...

    什么是有限自动机?

    有限自动机可分为确定的有限自动机(DFA)和不确定的有限自动机(BFA)。其中确定的有限状态自动机和不确定的有限状态自动机最大的区别是它们的转移函数不同,确定有限状态自动机对每一个可能的输入只有一个状态的转移,不确定有限状态自动机对每一个可能的输入可以有多个状态转移,接受到输入时从这多个状态转移中非确定地选择一个。

     

    1.有限自动机识别字符串

    这也是考试的一个常考点。所谓被有限自动机识别,就是依次输入字符串中的字符,判断其是否能使用有限自动机从初状态开始到终态结束,如果能,则可以被识别。

     

     

    2.状态转换图

    状态转换图是一个有向图,在状态转换图中,每一个结点代表一个状态,其中双圈是终态状态,每一个转换函数对应图中的一条有向弧。

     

    3.NFA转换位DFA

    此部分转载自:http://blog.csdn.net/u012359618/article/details/42456771

     

    1. 根据上面的状态转换图写出状态转换表,什么!不知道什么是状态转换表?那你来对地方了。状态转换表是转台转换图的另外一种表示形式,如下图,左侧表头0~9表示的

        是状态,上方表头a,b,c表示的是条件。其余部分表示的是后继状态

     

                    

          a      

           b      

           ε      

    0

    1, 7

    1

    2, 4

    2

    3

    3

    6

    4

    5

    5

    ∅ 

    6

    6

    1, 7

    7

    8

    8

    9

    9



    2. 求出ε-closure(s),ε-closure(s)表示由状态s经由条件ε可以到达的所有状态的集合

     

    ε-closure(0)={0,1,2,4,7}

    ε-closure(1)={1,2,4}

    ε-closure(2)={2}

    ε-closure(3)={1,2,3,4,6,7}

    ε-closure(4)={4}

    ε-closure(5)={1,2,4,5,6,7}

    ε-closure(6)={1,2,4,6,7}

    ε-closure(7)={7}

    ε-closure(8)={8}

    ε-closure(9)={9}

     

    3. 转换,下面就是真正剧情了

    首先将初始态的转换闭包ε-closure(0)设为状态A,即A={0,1,2,4,7},注意这里的状态A是DFA中的,和前面的状态0,1,2,3,4,5没有关系

    接着写出状态A经过上面转换图中所有转换条件得到的状态,后继状态里面不包括自身,这里的转换条件包括a和b,注意,不包括ε,转换的一个目的就是消除ε。

    ε-closure(0) = A

    ε-closure(move(A,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B

    ε-closure(move(A,b)) = ε-closure(5) = {1,2,4,5,6,7} = C

    ε-closure(move(B,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B

    ε-closure(move(B,b)) = ε-closure({5,9}) = {1,2,4,5,6,7,9} = D

    ε-closure(move(C,a)) = ε-closure()

    ε-closure(move(C,b))

    ε-closure(move(D,a)) = ε-closure({3,8}) = {1,2,3,4,6,7,8} = B

    ε-closure(move(D,b)) = ε-closure(5) = {1,2,4,5,6,7} = C

     

    4. 画出DFA状态转换表(每一个状态只有一个后继状态)

     

     

    a

    b

                 A             

                   B               

                    C                

    B

    B

    D

    C

    B

    C

    D

    B

    C

     

     

    5. 画出DFA状态转换图

     

     

    4.DFA的最小化

     

        (1) 消除多余状态

                  Ⅰ. 什么是多余状态

                        · 从这个状态出发没有通路到达终态

                        ·  从开始状态出发,任何输入串也不能到达的那个状态

                   Ⅱ. 如何消除多余状态

                         删除

                         

                 (2)  等价状态

                          Ⅰ. 何为等价状态,对于两个状态s和t

                                ·  一致性条件:状态s和t必须同时为终态或非终态

                                ·  蔓延性条件:对于所有输入符号,状态s和状态t必须转化到等价的状态里

            

                       接下来是关于如何利用上面的两个条件来判断是否为等价状态,来一张复杂的状态转换图,是不是有点晕,哈哈

                      

                       首先,画出状态转换表

                      

                      看1和2,1和2都是非终态,满足条件1,1和2都可以转换成状态2,满足条件2,将两者合并。

                      看6和7,6和7都是终态,满足条件2,6和7都可以转化成状态6,满足条件2,将两者合并。

                      以此类推,当然,2和5也是可以合并的,记住最后的结果只有一种,只要满足合并后的状态最少就行

                     

                       转化

                      1,2→A

                       3,4→B

                       5→C

                       6,7→D

                       列出转化后的转台转换表

                             

                     再画出相应的状态转换图就大功告成啦~~

                     

                       

                                        

    5.有限自动机与正规式之间的转换

    来源:http://blog.csdn.net/cgzhello1/article/details/7961965

    1.有限自动机转换为正规式

    对于 ∑上的NFAM,可以构造一个 ∑上的正规式R,使得L(R)=L(M)。拓广状态转换图的概念,令每条弧可用一个正规式作标记。为 ∑上的NFA M构造相应的正规式R,分为如下两步:

    (1)在M的状态转换图中加两个节点,一个x节点,一个y节点。从x节点到NFA M的初始状态节点引一条弧并用 ε标记,从NFA M的所有终态节点到y节点引一条弧并用 ε标记。形成一个与 M等价的M',M'只有一个初态x和一个终态y。

    (2)按下面的方法逐步消去M'中除x和y的所有节点。在消除节点的过程中,用正规式来标记弧,最后节点x和y之间弧上的标记就是所求的正规式。消除节点的规则如图2-6所示。

    图 2-6 有限自动机到正规式的转换规则示意图

    2.正规式转换为有限自动机

    同样地,对于 ∑上的每个正规式R,可以构造一个E上的NFA M,使得L(M)=L(R)。通过对正规式R进行分裂并加入新的节点,逐步把图转变成每条弧上的标记是E上的一个字符或 ε。转换规则如图2-7所示。

    图 2-7 正规式到有限自动机的转换规则示意图
     

     

     

     

    常见题目:

    题目给定一正规式,要求给出其NFA、DFA或最简DFA。

    题目给定一用状态图表示的NFA,要求给出其对应的DFA或最简DFA形式。

    题目给定一NFA、DFA或最简DFA,要求给出其对应的正规式。

    题目给定一正规集,要求给出其相应的DFA。

    题目给定一用自然语言描述的正规集,要求给出其相应的正规式表示形式

     

     

    例题:(来源见水印)

     

    
     

    [解析] 至少要有一个.或E,所以在BCD中。
    然后不含+,所以在CD中。

    然后观察5出去的两条边(对应于.后的字符),如果是数字的话,就不能出现E了,所以选C。

    具体来说

    0是入口,6是出口,初始进入0状态,必需最终到达6状态
    A 3857,状态过程:0->1->1->1->1
    B 1.2E+5,E+5状态过程:0->1->5->2->? 
    C -123.67,状态过程:0->4->1->1->1->5->6->6

    D 0.576E10,状态过程:0->1->5->6->6->6->?

    展开全文
  • 一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )、 二、转换方法与要点





    一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )



    确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ;

    确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ;


    确定性有限自动机 给定一个输入 , 其输出时唯一的 ;

    非确定性有限自动机的定义 包含 确定性有限自动机的 定义中 ;


    NFA 的后继状态 可以是 00 个 , 11 个 或 多个 , DFA 每个状态只能有 11 个后继状态 ;

    确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA ) ;

    可以证明非确定性有限自动机 ( NFA ) , 必定有一个 确定性有限自动机 ( DFA ) 与其等价 ;



    参考博客 :





    二、转换方法与要点



    1. 转换方法 :

    起始状态 开始推演运行 ,

    列出所有的 分支步骤 ,

    注意 计算分叉节点 , 会产生多个后续状态 ,

    此时就生成了 新的状态 ,

    这些新的状态就是非确定性有限自动机 转换成的 确定性有限自动机的 新状态 ;


    2. 转换要点 :

    ① 新状态生成时机 : 有两种情况会出现计算分支 ,

    情况一 : 状态有 ε\rm \varepsilon 无条件跳转 , 如下图的 11 状态 , 会无条件跳转到 33 状态 , 此时就会出现两个后续状态 {1,3}\rm \{ 1, 3 \} ,

    情况二 : 读取同样的字符 , 有两个后继状态 , 如 22 状态下读取 a\rm a 字符 , 会跳转到 22 状态和 33 状态 , 因此其后继状态是 {2,3}\rm \{ 2, 3 \} ,

    情况三 : 计算出现新状态后 , 新状态的后继状态 , 一般也是一个集合 , 当计算 {1,3}\rm \{ 1, 3 \} 的后续状态时 , 会分别计算集合中的两个状态分别读取 a\rm a 字符的后继状态 , 取并集 ;

    在这里插入图片描述

    ② 新状态的计算机制 : 如果生成了一个新的状态 , {1,3}\rm \{ 1, 3 \} , 如果要计算其后继状态时 , 就需要分别计算 1133 的后继状态, 然后取并集 ;

    ③ 空集 : 在推演计算时 , 有可能会出现空集 , 如 {3}\rm \{ 3 \} 状态读取 b\rm b 字符的后继状态没有 , 就是空集 ;


    3. 接受状态 : 如果最终的 DFA 的新状态集合中 , 包含 NFA 的接受状态 , 那么该新状态就是接受状态 ;


    4. 空集 : 如果其中有空集 , 那么将空集也当做一个状态 , 空集状态下读取任何字符都是空集 ;


    5 . 后继状态有 ε\rm \varepsilon 无条件跳转 : 如果读取字符后跳转的 后继状态有 ε\rm \varepsilon 无条件跳转 , 则该后继状态会是两个状态的集合 , 如 : {3}\rm \{ 3 \} 状态读取 a\rm a 字符跳转到 11 状态 , 而 11 状态无条件跳转到 33 状态 , 则后继状态是 {1,3}\rm \{1, 3\} ;



    参考博客 :

    展开全文
  • 有限自动机课件

    2012-03-23 22:45:38
    有限自动机课件,适合计算机研究生,有需要者可以下载。
  • dfa确定有限自动机定义In Deterministic Finite Automata (DFA), for a given input symbol the machine will move to which next state can be determined and hence it is named as deterministic automata....
  •  下面是我对非确定型有限自动机变换为确定型有限自动机的理解:  1.先画语法树.  2.用Thompson算法构造正规式的NFA(非确定性有限自动机)。  3.构造出正规式的状态转换矩阵然后把NFA转化为DFA(确定性有限...
  • 由正则表达式生成有限自动机,显示有限自动机的状态和动作等,方便学习有限自动机课程。
  • 非确定性有限自动机 NFA 转为确定性有限自动机 DFA 示例
  • 一、确定性有限自动机的接受问题、 二、证明 "确定性有限自动机的接受问题" 可判定性
  • 有限自动机DFA

    2014-03-07 14:34:17
    Java实现有限自动机相关功能的工具包,包含:正则式与NFA,DFA的相互转化;DFA的交、并、差、补运算;判断一个DFA对应的正则集是否是无限集;列出一个有限正则集所包含的所有字符串,以及包含字符串的最小长度和最大...
  • 有限自动机模板类

    2017-05-23 13:39:23
    有限自动机模板类,用于状态控制和切换
  • 编译原理课程实验-有限自动机的确定化和最小化: 实验目的:利用状态表和有限自动机的运行原理编写和设计程序,判断输入的自动机是DFA还是NFA,如果是NFA,利用子集法将其确定化,然后利用求同法或求异法将所得的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,430
精华内容 4,572
关键字:

有限自动机