形式语言与自动机第三课

本章节主要内容：

1. 确定有限自动机、非确定有限自动机及其等价性
2. 右线性文法和有限自动机的等价性
3. 右线性文法性质（泵普定理）
4. 使用归纳法进行证明

确定有限自动机、非确定有限自动机及其等价性

• 状态：将事物区分的一种标识
  有限状态自动机必定是离散的

• 有限状态自动机

1. 具有离散的输入输出（可以没有输入或者输出）
2. 状态有限
3. 状态+输入->状态转移

• 有限自动机五要素：

1. 有限状态集
2. 有限符号输入集
3. 转移函数
4. 一个开始状态
5. 一个终态集合

DFA->每次转换后的后继状态唯一
NFA->每次转换后的后继状态唯一

• FA：理解为读取卡带上字符的控制器

DFA

定义：$M=(Q,T,\delta ,q_0,F)$
$Q$：有限状态集合
$T$：有限输入集合
$\delta$状态转移集合 $Q\times T\to Q$
$q_0$：初始状态
$F$：终止状态集

• ${\delta }^{\prime }$函数：接收一个字符串的状态转移函数
  ${\delta }^{\prime }(q,ϵ)=q$

• DFA接收的语言KaTeX parse error: Undefined control sequence: \set at position 6: L(M)=\̲s̲e̲t̲{\omega | \delt…
  必须使得DFA到达终态

• 格局
  描述有限状态机在某个时刻的状态
  初始格局：$q_0,\omega$（$\omega$ 为待输入字符串）
  终止格局：$q,ϵ$

有限状态自动机是无记忆的

自动机的设计是一个创造过程
关键：不需要记住所看到的整个字符串，只需要记住关键信息

NFA

对应一个输入，可以同时到达多个状态，称之为NFA
NFA的$\delta$为：$Q\times T\to 2^Q$

接收一个字符串后，NFA进入一个状态集，包含一个或者以上F中的状态，称之为NFA接收该字符串

• ${\delta }^{\prime }$扩展
  KaTeX parse error: Undefined control sequence: \set at position 21: …a'(q,\epsilon)=\̲s̲e̲t̲{q}
  KaTeX parse error: Undefined control sequence: \set at position 16: \delta'(q, wa)=\̲s̲e̲t̲{p|存在r\in\delta…：${\delta }^{\prime }(q,w)$对应的每个状态下再接收字符a后可以达到的状态集合的并集，即${\delta }^{\prime }(q,w)=r_i,{\delta }^{\prime }(q,wa)=\cup \delta (r_i,a)$

NFA、DFA的等价性

DFA是NFA的特例
因此，NFA必定能接收DFA的源
证明等价性：只要证明NFA能接收的语言能被DFA所接收

定理：设一个NFA接收语言L，则必定存在一个DFA能接收L

• 子集构造法（我不是很懂）

实践中，通过子集构造法得到的DFA的状态数目与原NFA的状态数目大体相同