【编译原理】有限状态机（FSM）和有限自动机（FA）

╰+攻爆jí腚メ 2024-03-31 15:50 67阅读 0赞

## 1 回顾 ##

### 1.1 一些基本概念 ###

程序：特定符号的字符串  
语法：通过使用它来生成格式良好的程序的一组规则

### 1.2 基本功能与层次 ###

程序：描述对某些数据的处理过程

程序语言的功能：描述数据和数据的处理过程

程序层次：

1.  子程序，过程，函数
2.  面向对象：类
3.  句子：表达式

## 2 一些基本术语 ##

### 2.1 字母表 ###

一组非空有限元（符号），我们写为**∑**  
\{a, b, c, +, …\}

### 2.2 字符串 ###

表中每个元素都称为**string**

∑中的字符串：由∑中的符号组成的任何有限序列

空序列：不包含任何字符串的序列（空字符串ε，也是∑的字符串）

∑\*，所有字符串，包括ε（∑不包括ε）  
![在这里插入图片描述][ae3a42b0cc3c445bbe6148096ceab992.png]  
字符串的长度：字符串中symbol的数量  
![在这里插入图片描述][8b56bbfe302f4f41a20abb804e47f5c8.png]  
![在这里插入图片描述][d2718f22cddb42529d509b3bf88bf0ca.png]

## 3 有限状态机（FSM） ##

也称为有限自动机（FA）

它用来表达第三类语法（正则语法）

这种语法所描述的语言是正则语言（一种语言可以用正则语法来描述，那么就可以用FSM来分析）  
![在这里插入图片描述][d94d6e4d418e4d6fae7a265f1cbe32fc.png]  
**Start（initial）state**：  
识别过程开始  
画一条“不知从何而来”的无标记箭头线

**Transition states**:  
根据一个或多个标记字符的匹配，记录从一个状态到另一个状态的更改。

**Accepting（final）states:**  
表示识别过程的结束  
在图中的状态周围绘制双线边框

有限自动机（有限状态机）是描述特定类型算法的数学方法。

有限自动机与正则表达式之间的强关系。

只要一种语言可以用正则语法来描述，它就可以用FSM来分析。

## 4 有限状态机和正则表达式之间的关系 ##

只要一种语言可以用规则语法来描述，它就可以用FSM来分析

每个FSM只识别一种语言

ε-转变：在不查阅输入字符串（并且不使用任何字符）的情况下可能发生的转换

![在这里插入图片描述][4a4dfa33aafa493fa52870dea65840e0.png]

## 5 FSM的功能 ##

识别一种语言（可以是字符串集）  
![在这里插入图片描述][3676b128762042f09b0aa470b72fd7fa.png]  
**每个FSM只识别一种语言**

1.  如果FSM F不接受字符串，则L（F）=Ø
2.  ε-转换：可以在不查询输入字符串（并且不使用任何字符）的情况下发生的转换  
    ![在这里插入图片描述][7d2823ffbbea4d7485318e9cc98fbd50.png]

## 6 有限状态机(FSM)的形式化定义 ##

补充：NFSM =》一个输入对应多个输出

### 6.1 五元组表示法 ###

FSM是一个5元组 M = (S, Σ, f, s0, Z) 其中：

1.  S是有限状态集合
2.  Σ是一个有限字母表，其中w=w1w1…wn是一个输入字符串，且wi是∑的成员
3.  f是一个单值转换函数，定义了S x Σ -> S
4.  s0∈S是初始状态0
5.  Z∈S是最终状态  
    ![在这里插入图片描述][ee5bc901bc4f4707966faad79498b1c2.png]  
    ![在这里插入图片描述][349a4f7221d0482f8f91e40ca59231b3.png]

### 6.2 状态转换表表示法 ###

![在这里插入图片描述][21a2669951f04eb5bb40ca22c553668a.png]

## 7 高级语言和语法描述 ##

语法：描述语言语法结构的形式规则

给出语言定义的三种方法：

1.  列举：限定句 e.g. \{ I am a teacher, You are students\}
2.  有限规则：用所描述的语言生成所有句子/有限或无限的句子
3.  自动机（一种算法或过程）：  
    1）字母表中的所有字符串作为输入，检查或识别这些字符串  
    2）当输入字符串是字母表中的一个句子时，接受  
    3）否则，拒绝

## 8 乔姆斯基（Chomsky）类别（层次结构） ##

乔姆斯基将语法分为4个类，每个类对应一种语言  
Type 0 grammar  
Type 1 grammar  
Type 2 grammar  
Type 3 grammar  
表达能力不断增强的形式语法类型集

### 8.1 类型0（短语结构语法或无限制语法） ###

G中的规则为α→ β、 α∈V+和β∈V\*，对α，β没有其他限制  
类型0定义的语言：L0或递归可枚举语言  
图灵机：接受或识别这种类型的语言

### 8.2 类型1（上下文有关语法） ###

G中的规则为α1Aα2→α1βα2，α1，α2∈V+，A∈Vn，β∈V+ (A是非终结符)  
终结字符指的是不可再分解的字符  
类型1定义的语言:L1或上下文有关语言  
线性有限自动机：接受或识别这种类型的语言

### 8.3 类型2（上下文无关语法） ###

G中的规则为A→β、 A∈Vn，β∈V+  
类型2定义的语言：L2或上下文无关语言  
下拉机（pumping lemma）：接受或承认这类语言

### 8.4 类型3（正则语法） ###

G中的规则为  
A→aB or A→a, A and B ∈Vn, a∈Vt  
A→Ba or A→a, A and B ∈Vn, a∈Vt  
类型3定义的语言：L3或正则语言  
有限自动机：接受或识别这种类型的语言

### 8.5 总结 ###

![在这里插入图片描述][3faba57b714e433e99f5c6a827c70283.png]  
L0 L1 L2 L3 从左到右，最右边语法限制最多  
if α → β  
 Type 0 grammar: at least one non-terminal in α  
 Type 1 grammar: |α| ≤ |β|  
 Type 2 grammar: A∈ Vn  
 Type 3 grammar: A → wB or A → Bw

举例：如果语法是正则的，那么它必须是上下文无关  
![在这里插入图片描述][be8dec3db1764088b3ed586a9c272590.png]  
参考来源：Dr. Amit K. Chopra

[ae3a42b0cc3c445bbe6148096ceab992.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/836141ef05044270a0fee93d20a7313f.png
[8b56bbfe302f4f41a20abb804e47f5c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7a2773905df94688bbf5c0d3ced9f7cc.png
[d2718f22cddb42529d509b3bf88bf0ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bd19760ab76641dba7bea9229b28caf2.png
[d94d6e4d418e4d6fae7a265f1cbe32fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ee1a696721a4497197742fe487c12b71.png
[4a4dfa33aafa493fa52870dea65840e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f08cd05887c4439f9013630e0a944e65.png
[3676b128762042f09b0aa470b72fd7fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c80d45a05be4473c8ee928289986dc96.png
[7d2823ffbbea4d7485318e9cc98fbd50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/854a14caae1e45d1ab4121aa10fc89ac.png
[ee5bc901bc4f4707966faad79498b1c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/010cda4698f049e7829ce6551ac628cb.png
[349a4f7221d0482f8f91e40ca59231b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b8ff89ecd20641ae9aa1a342c172dae0.png
[21a2669951f04eb5bb40ca22c553668a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b4ecd3b7c6f649f89c9528c2faf42550.png
[3faba57b714e433e99f5c6a827c70283.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a53e002264f946cf83cd97abd740d03c.png
[be8dec3db1764088b3ed586a9c272590.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/35af4f82650a4da7a2010f61dd1c4a05.png