编译原理学习之：有限状态机（Finate-state Automaton）

有限状态自动机（Finate-State Automaton）

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

有限状态自动机的定义

• $Q$ 代表有限的状态集合，
• $\Sigma$ 表示有限的字母表，也就是上图中线上的那些触发条件；通常选用那些数字 $1,2,3...$ 或者小写字母 $a,b,c...$
• $\delta$ 代表的是状态转移的矩阵（情况）即，一个状态 $q\in Q$ 在一个 $\sigma \in \Sigma$ 的情况下转移到另外一个状态 $q$；上图中所有的状态转移的全部记录就是 $\delta$
• $q_0$ 是状态里的一个特殊状态，即开始状态；开始状态只有一个
• $F\subseteq Q$ 是接受状态， 即上图中用双圆圈表示的状态；当然 $F$ 是一个集合，他里面可以有多个接受状态，也可以只有一个接受状态；
  

字符串和语言

• $\Sigma$ 上的 字符串 是 $\Sigma$ 中 一串符号的有限序列
• 字符串可以进行 concatenate，例如 $x$ 可以和 $y$ 结合成为 $xy$
• $ϵ$ 用来表示空字符串
• $\Sigma$ 上的 语言（language） 是 $\Sigma$ 上的 所有有限长度字符串的集合；这个集合可以是有限的，也可以是无限的
• ${\Sigma }^{\ast }$ 代表 $\Sigma$ 上的 所有有限长度的字符串

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

• 下面的每一个集合表示的字符串集合都是一种语言。这些语言都是建立在 $\Sigma$ 字符集上的
• 这么来看，其实一个 $\Sigma$ 字符集能表示的语言有很多种（每种对应不同的规则，也可以表示为不同的自动机）
• 换句话说，每种语言都是字符集 ${\Sigma }^{\ast }$ 的一个子集而已
  

自动机 vs 语言

• 当我们已知一个有限状态的自动机 $M_1$，我们其实就表示了一种语言（language），即一个语言被 $M_1$ recognized 。
• 我们上面已经知道，一个语言其实是一个集合，那么我们被 $M_1$ 识别的语言可以表示成如下形式：
  

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

• 如何判断一个字符串是否被一个 automaton 接受呢？其实这个问题问的就是，怎么判断一个字符串属于 $M_1$ 自动机表示的语言（字符串集合）。

  公式化表示：

  • 假设自动机 $M=(Q,\Sigma ,\delta ,q_0,F)$；并使得字符串 $w=v_1{v}_2\cdot \cdot \cdot v_n$ 属于字符集 ${\Sigma }^{\ast }$ ；如果 $M$ accepts $w$ 当且仅当：存在一系列状态（states）$r_0,r_1,...,r_n$，其中 $r_i\in Q$，满足：
    • $r_0=q_0$
    • $\delta (r_i,v_{i+1})=r_{i+1},fori=0,...,n-1$
    • $r_n\in F$
  • $M$ recognises language $A$ iff A = { w ∣ M   a c c e p t s   w } A = \{w | M~ accepts ~w\} A={
    w∣M accepts w}

正则语言定义 Regular

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

正则运算

• 一个正则语言（集合）和另外一个正则语言的并运算之后还是正则的
• 两个正则语言进行 concate 操作之后还是正则的
• 一个正则语言的克林闭包得到的集合依然是个正则语言
• $ϵ$ 也属于克林闭包集合中
  
  

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