• 有穷自动机 DFA（确定）和NFA（不确定）

    有穷自动机分为DFA和NFA两种。分别为确定的和不确定的两种形式。

    DFA部分：

    一个确定的有穷自动机是一个五元组  M=(K,Σ,f,S,Z)各自的意义分别为：

    K ： 状态集合，有限集合
    Σ ： 有穷字母表，它的每个元素称为一个输入符号
    f ： 状态转换函数， f ： K × Σ→K 的映射，且为单射。例 如 f (k i ,a)=k j 表示当前状态为 k i ，输入符号 a ，经状态转 换函数转向状态 k j 。
    S ： 唯一的一个初始状态， S ∈ K
    Z ： 终止状态集， Z⊆ S ， 终态也称为可接受状态
    DFA的状态转换图 : DFA M 含有 m 个状态， n 个输入字符，则状态转换 图有 m 个结点，每个结点至多有 n 条箭弧射出，每条箭弧用 Σ 中一 个不同的输入字符做标记。
    如： DFA M=( K, Σ, f , S, Z ) = ( {S, U, V, Q}, {a,b}, f , S, {Q})
    f (S,a) = U   f (S,b) = V   f (U,a) = Q   f (U,b) = V   f (V,a) = U   f (V,b) = Q   f (Q,a) = Q   f (Q,b) = Q

     在状态转换图中开始的状态是需要有一个箭头指向的，终止的状态是一个双圈的。

    DFA的特点：
    (1) 初态唯一
    (2) 输入字符不包括ε(空串)
    (3) 有向边上只有一个字符
    (4) 一个状态对于某个字符，最多只有一条出边
    可被 DFA 识别癿单词符号
    对 ∑ * 中任意符号串 t ，若存在从初态到某一终态的 通路，且通路上所有弧标记符连接成的字等于 t ，
    则称 t 可为 DFA 所识别 ( 读出或接受 ) 。 即对于任意字符串 t ∈ Σ, f (S ， t)=P, P ∈ Z
    可识别空串
    若 M的 初态结点同时也是终态结点，则空字 ε 可为 M 所识别。
    f (k i ， ε)= k i
    NFA部分：
    不确定有限自动机NFA定义：
    NFA是一个五元组， M=(K, Σ, f , S, Z)  标红的部分是和DFA不同的地方
    K ： 状态集合，有限集合
    Σ ： 有穷字母表，它的每个元素称为一个输入符号
    f ： 状态转换函数， f ： K × Σ * →K 的全体子集映射
    S ： 非空初始状态集， S⊆ K
    Z ： 终止状态集， Z⊆ K ， 可为空集
    3. NFA的特点：
    (1) 初态不 唯一
    (2)输入字符包括ε(空串)
    (3)有向边上可以为 字符串
    (4)一个状态对于某个字符，可能有 多条输出 边 ，即状态的后继不唯一。
    DFA是NFA的特例
    有穷自动机的等价性
    对于每个NFA M，存在一个DFA M’使得 L(M)=L(M’)
    对于任何两个有穷自动机，如果L(M)=L(M’)， 则称M与M‘是等价的
  • 相关阅读:
    软件测试/测试开发丨探索AI与测试报告的完美结合，提升工作效率
    使用Spring Cache实现广告缓存并基于RabbitMQ实现双写一致
    Maven 的 spring-boot-maven-plugin 红色报错
    CSDN21天学习挑战赛 - 第四篇打卡文章
    wuzhicms代码审计
    python笔记Ⅴ----元组、字典、集合
    python odoo 中药的生产管理一
    基于seata的分布式事务
    java毕业生设计中小型连锁超市配送中心配送管理计算机源码+系统+mysql+调试部署+lw
    Apache Doris (四十三）： Doris数据更新与删除 - Update数据更新
  • 原文地址：https://blog.csdn.net/m0_53345417/article/details/126806124