一、确定有限自动机

1. 确定有限自动机的定义

⚠️注意这里说的是终止状态集，即终止状态不唯一
包含定义：字符集（圈中内容）、状态集（圆圈）、状态转移函数（箭头）、初始状态S、终止状态集（同心圆）

2. DFA的确定性

2的解释：一个状态接收一个符号得到一个值（相当于函数的一一映射）

3. DFA的表示

状态转移矩阵

二元函数直接填写对应的数值；要满足表示5元组，初始和终止要单独表示出来。无值地方填缺省。
优势：
是一种更为直观的表现形式，是真实在程序使用的实现手段，是一种更加容易实现的方法，用一个二维数组即可，从实现的角度更加方便。

状态转换图

初始状态一个入度箭头、终止状态同心圆两个。注意字符集和状态集都是使用英文字母表示的时候的区分
构造方式：

1. 图中的节点就是状态
2. 构造映射函数，即给定一个状态给定一个字符，映射到另一个状态上，相当于是一种对转换函数的一种转化
3. 初始和终止节点的标识（对于终止状态不一定唯一）
   优势：
   分析手段

4. DFA接受的串

即从初始状态到终止状态上的箭头上标识的字母按照顺序连接在一起组成的符号串。

⚠️在自动机中可能存在一个【缺省状态】，对于在给定定义中没有给出接收之后到达状态的边均到达缺省状态。缺省状态只有入度没有出度。

现在已知自动机的定义、自动机的两种表示、自动机所能接受的串，那么这些定义有什么应用？
自动机作为一种工具，用这种工具做什么取决于使用者的需求和目的，在操作系统中可以使用自动机描述并发活动（状态机）。抽象的写，说一个字符集abcd，但是实际应用中每一个符号都可以带有特定意义的动作或功能——对自动机应用的象征性实例理解。

就是连续的两个1串之间如果有字符0的话就是连续的两个1串。
可以使用自动机的方式表示（补）

用自动机去描述被3整除的10进制数（考点）

1. 分组：根据余数对每一位的数字进行分类
   D₀:0/3/6/9
   D₁:1/4/7
   D₂:2/5/8
2. 自动机表示，终止状态是D₀
3. 按照输入数字的顺序每个数字从高位开始进入自动机进行判断，最后到达D₀的数字串即为可以被3整除的数

注意每一个状态所代表的不同意义！

5. 自动机描述词法规则

自动机的作用即根据输入的单个字符拼凑出单词序列，使用自动机描述标识符、常数、特殊符号将其描述为一个大的自动机。

1. 标识符的描述

如果输入的字符可以从开始状态出发到达终止状态，并且停留在终止状态上，那么这个串即可被自动机接受，如果是区分是哪一类的就可以看它最终是停在具体哪个终止状态。
能否表示即本身是否正确——是否可以停留在终止状态
属于哪一类——看最终停留在哪个终止状态上

判断±符号代表的意义是正负还是运算符号，可以往前判断一个字符是什么来判断其具体意义。eg：前面是标识符/常数——运算符；括号/赋值号——正负

6. 自动机的实现

⚠️注意的问题

1. 对于状态不太多的比如01串使用switch-case语句
2. 特殊的状态——死状态重点没通路，或者没有开始到达的通路
3. 缺省状态（之前）
4. 缺省转换函数——对应缺省状态的函数

7. 自动机等价

例题：
画出能被4整除的二进制数