课程学习——有限自动机理论
一、Chomsky对文法和语言对分类
Chomsky的分类依据是产生该语言的文法。
0型文法
所有一般的PSG（短语结构文法）及PSL（短语结构语言）。似乎对文法和语言没有特别的要求，这一类包含了以下介绍的1型、2型、3型文法。
1型文法
文法的任意产生式 α -> β ，均有 | α | ≤ | β |。1型文法也叫上下文相关文法（CSG），其产生的语言称上下文相关语言（CSL）。简单理解：产生式左边的终结符和非终结符数目之和不大于产生式右边。
2型文法
文法的任意产生式 α -> β ，均有 | α | ≤ | β |，且α是非终结符。2型文法也叫上下文无关文法（CFG），其产生的语言称上下文无关语言（CFL）。在1型文法基础上，还要求产生式左边只能有非终结符（大量作业证明，还只有一个非终结符）。
3型文法
文法的任意产生式 α -> β ，只有形如A -> w或A -> wB的形式（一个非终结符推导出终结符或终结符+一个非终结符）。3型文法也叫右线型文法（RLG）或正则文法（RG）。
简单理解：产生式左边只有一个非终结符，产生式右边最多一个非终结符，且在最右边。
例题
文法分类构造
二、语言间的基本运算
1. 联合运算
L = L1∪L2 = {w | w∈L1或w∈L2}
两个语言L1、L2联合得到的语言L，其句子是原来两个语言所有句子。
2. 连接运算
L = L1L2 = {w | w=w1w2, w∈L1, w∈L2}
两个语言经连接运算得到的语言L，其句子是两个语言L1、L2句子前后相连。
3. 迭代运算
语言之间不停推导，替换。
定理：上下文相关语言，上下文无关语言和正则语言在3种运算内是有效封闭的。有效指仍能合法产生一个语言；封闭指经运算后，语言类型不发生改变。
三、正则集和正则表达式
正则集
对于字母表∑上的语言L
- 若L是有限的，则L是正则的（正则集）。
- 或L能由正则语言经3种运算产生。
正则语言即正则集。
正则表达式
- 若a∈∑，则a是正则表达式
- 或正则表达式经3种运算得到的
正则集和正则语言都是一种有穷描述。
四、有限自动机
有限自动机分类如下：
- 有限状态自动机（FA），包括确定的FA（DFA）和不确定的FA（NFA）
- 下推自动机（PDA），包括单态PDA和多态PDA
- 图灵机（TM）
Ⅰ. FA
有限状态自动机是状态转换图，根据当前状态和接收到的字符确定应转换到什么状态。DFA对于每一状态和接收字符有确定的状态转换，而NFA可能会转换到不同的状态。
例1 构造DFA
DFA构造
例2 构造NFA
NFA构造
Ⅱ. PDA
下推自动机用来表示无穷语言，栈存储方式。
- 单态PDA指令为<a, Z, AZ>，表示栈顶元素为Z时，读取到a字符，则将Z弹出栈，将AZ压栈。
- 多态PDA的五元式为<q, a, Z, q', AZ>，表示当前状态是q，栈顶元素是Z时，读取到a字符，则状态变为q'，并将Z弹出栈，将AZ压栈。
例1 构造能接收如下语言的单态PDA
单态PDA构造
例2 构造能接收如下语言的多态PDA
多态PDA构造
当字符串扫描结束，栈为空，称这是该PDA能够接收的语言。
Ⅲ.TM
图灵机（TM）的有限状态控制器（FSC）处于某个状态，读写头将扫描带上的一个单元。根据当前状态和扫描到的字符，TM发生如下动作：
- FSC状态改变
- 擦除扫描到的带上符号，并印刷上新的（可能与原来相同）
- 读写头向左/右移动一个单元，或不移
指令描述：<q, x, q', W, {R, L, N}>
其中，q和q'是前后状态，x是读到的字符，W是印刷上的新字符，{R, L, N}是读写头动作。
图灵机的几种技术
- 存储技术。如[q, a], [q, aa]两个状态可以存储读到的1个或2个a，用特殊状态实现。
- 移动技术。如[q, a1], [q, a1, a2], [q, a2, a3]，结合存储技术可实现如向右移动2个位置的功能。
- 多道技术。常用于实现图灵机的计算功能。
- 查讫技术。结合多道技术，查询到目标后在另一道对应位置标记特殊字符。
例 构造3道图灵机，实现二进制数的按位异或运算
图灵机构造
