编译原理学习之:有限状态机(Finate-state Automaton)

编译原理学习之:有限状态机(Finate-state Automaton)文章目录有限状态自动机(Finate-StateAutomaton)有限状态自动机的定义字符串和语言自动机vs语言自动机accept一个字符串的意义正则语言定义Regular正则运算有限状态自动机(Finate-St

有限状态自动机(Finate-State Automaton)

  • 状态是有限的
  • 通过不同的触发在状态之间进行转换

在这里插入图片描述

有限状态自动机的定义

  • Q Q Q 代表有限的状态集合,
  • Σ \Sigma Σ 表示有限的字母表,也就是上图中线上的那些触发条件;通常选用那些数字 1 ,   2 ,   3… 1,~2,~3… 1, 2, 3... 或者小写字母 a , b , c . . . a,b,c… a,b,c...
  • δ \delta δ 代表的是状态转移的矩阵(情况)即,一个状态 q ∈ Q q\in Q qQ 在一个 σ ∈ Σ \sigma\in \Sigma σΣ 的情况下转移到另外一个状态 q q q;上图中所有的状态转移的全部记录就是 δ \delta δ
  • q 0 q_0 q0 是状态里的一个特殊状态,即开始状态;开始状态只有一个
  • F ⊆ Q F\subseteq Q FQ 是接受状态, 即上图中用双圆圈表示的状态;当然 F F F 是一个集合,他里面可以有多个接受状态,也可以只有一个接受状态;
    在这里插入图片描述

字符串和语言

  • Σ \Sigma Σ 上的 字符串 Σ \Sigma Σ一串符号的有限序列
  • 字符串可以进行 concatenate,例如 x x x 可以和 y y y 结合成为 x y xy xy
  • ϵ \epsilon ϵ 用来表示空字符串
  • Σ \Sigma Σ 上的 语言(language) Σ \Sigma Σ 上的 所有有限长度字符串的集合;这个集合可以是有限的,也可以是无限的
  • Σ ∗ \Sigma^* Σ 代表 Σ \Sigma Σ 上的 所有有限长度的字符串

举例: Σ = { 0 , 1 } \Sigma=\{0,1\} Σ={
0,1}
上的语言:

  • 下面的每一个集合表示的字符串集合都是一种语言。这些语言都是建立在 Σ \Sigma Σ 字符集上的
  • 这么来看,其实一个 Σ \Sigma Σ 字符集能表示的语言有很多种(每种对应不同的规则,也可以表示为不同的自动机)
  • 换句话说,每种语言都是字符集 Σ ∗ \Sigma^* Σ 的一个子集而已
    在这里插入图片描述

自动机 vs 语言

在这里插入图片描述

  • 当我们已知一个有限状态的自动机 M 1 M_1 M1,我们其实就表示了一种语言(language),即一个语言被 M 1 M_1 M1 recognized
  • 我们上面已经知道,一个语言其实是一个集合,那么我们被 M 1 M_1 M1 识别的语言可以表示成如下形式:
    在这里插入图片描述

自动机 accept 一个字符串的意义

  • 如何判断一个字符串是否被一个 automaton 接受呢?其实这个问题问的就是,怎么判断一个字符串属于 M 1 M_1 M1 自动机表示的语言(字符串集合)

    公式化表示

    • 假设自动机 M = ( Q , Σ , δ , q 0 , F ) M=(Q, Σ, δ, q_0, F) M=(Q,Σ,δ,q0,F);并使得字符串 w = v 1 v 2 ⋅ ⋅ ⋅ v n w = v_1v_2 · · · v_n w=v1v2vn 属于字符集 Σ ∗ \Sigma^* Σ ;如果 M M M accepts w w w 当且仅当:存在一系列状态(states) r 0 , r 1 , . . . , r n r_0,r_1,…,r_n r0,r1,...,rn,其中 r i ∈ Q r_i\in Q riQ,满足:
      • r 0 = q 0 r_0=q_0 r0=q0
      • δ ( r i , v i + 1 ) = r i + 1 ,   f o r   i = 0 , . . . , n − 1 δ(r_i, v_{i+1}) = r_{i+1} , ~for ~i = 0, . . . , n − 1 δ(ri,vi+1)=ri+1, for i=0,...,n1
      • r n ∈ F r_n ∈ F rnF
    • M M M recognises language A A A iff A = { w ∣ M   a c c e p t s   w } A = \{w | M~ accepts ~w\} A={
      wM accepts w}

正则语言定义 Regular

  • 能被一个有限状态机识别的语言一定是一个正则语言;即正则语言和优先状态机是等价的

正则运算

  • 一个正则语言(集合)和另外一个正则语言的并运算之后还是正则的
  • 两个正则语言进行 concate 操作之后还是正则的
  • 一个正则语言的克林闭包得到的集合依然是个正则语言
  • ϵ \epsilon ϵ 也属于克林闭包集合中
    在这里插入图片描述
    在这里插入图片描述

今天的文章
编译原理学习之:有限状态机(Finate-state Automaton)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/80666.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注