形式语言与自动机前半期

2022-04-19

整理到第三章结尾，期中考试前。

随便写写。

第一章没有。

没标粗那就不是重点，速通的话不用看。

标粗也不一定是，也可能是因为我觉得这里标粗了更好看。

第二章语言及文法

第一节语言

字母表：字符的有限集合，记为T。
- 形式符号的集合
- 常用 T、表示

字符串：字母表 T 上的一个字符串（简称串），或称为字（word），为 T 中字符构成的一个有限序列。
- 空串（empty string）, 用表示，不包含任何字符
- 常记为u,v,w,x,y,z；
- 常用a,b,c,d 标识单个字符。
- 字符串 w 的长度，记为 |w| ，是包含在 w 中字符的个数。

连接：设 x, y为串, 且 x = a1a2 … am, y = b1b2 … bn,
则 x 与 y 的连接
x y = a1a2 … am b1b2 … bn\
- 连接运算的性质：
  - ( x y ) z = x（ y z ）
  - x = x = x
  - | x y | = |x|+|y|
设ω1, ω2, ω3是字母表T上的字符串，称ω1是字符串ω1ω2的前缀，ω2是字符串ω1ω2的后缀，且ω2是字符串ω1ω2ω3的子串。
- 空串是任何字符串的前缀，后缀及子串。
- 字符串ω的逆用表示。是字符串ω的倒置。
- 空串ε的逆还是ε
幂运算：设 T 为字母表，n 为任意自然数，
- 定义
  - = {}
  - 设 x ，a T，则a x
  - 中的元素只能由（1）和（2）生成
- *闭包：
- +闭包：

语言：设 T 为字母表，则任何集合 L T* 是字母表T上的一个语言（language）
- 语言的积：两个语言L1 和L2的积L1 L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。
- 语言的幂：
  - 语言的幂可归纳定义如下:
    = {ε}
    
    注意这里有个左右翻转

第二节文法

定义：所谓文法是用来定义语言的一个数学模型
表示语言的方法：
- 若语言L是有限集合，可用列举法
- 若L是无限集合（集合中的每个元素有限长度），用其他方法。
  - 方法一：文法产生系统，由定义的文法规则产生出语言的每个句子
  - 方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。
元语言：描述语言的语言。例如：各种各样的程序设计语言
- 当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言。
BNF（巴科斯范式）：BNF范式通常被作为讨论某种程序设计语言语法的元语言
- ::= “定义为”
- <数字> ::= 0|1|2|……9
- <字母> ::= A|B|C|……Z|a|b|……z
- <标识符> :: =<字母> | <标识符><字母> | <标识符><数字>
- 通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。
- BNF定义了一种语言，其中标识符如上定义。
- BNF描述它所定义的语言，为元语言。
文法是一种元语言，一种方法，根据文法产生出语言的句子。

Chomsky文法体系：

相较于BNF，其中:=用代替，分别用I，L，D表示标识符、字母、数字
所以把BNF表示的再用Chomsky表示一遍，如下：
- I→L
- I→L
- I→ID
- L→a|b|….|z
- D→0|1|….9
Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。
P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。
可见文法的核心是生成式的集合，它决定了语言中句子的产生。

我终于知道为什么自动机ppt符号基本是错的了。属于是直接把电子教材的文本拷贝到ppt里，也不管符号编码对不对上。
倒是方便我做笔记了，直接复制粘贴就行了。
Chomsky文法的形式定义：文法G是一个四元组G=(N，T，P，S)，其中
- N 非终结符的有限集合
- T 终结符的有限集合
- P 形式为的生成式的有限集合。
  - 且
- S 起始符且S ∈N。

推导与句型

直接推导：
- 设G =（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，则有αAγ=> αβγ称αAγ直接推导出αβγ，或说αβγ是αAγ的直接推导。
推导序列：
- 设G = (N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）中的字符串，且α=α0、 α’ =αn，其中αi直接推导出αi+1 （0≤i≤n）,则称序列α0=>α1=>α2=>…=>αn是长度为n的推导序列，*而α=α0是长度为0的推导序列。
- 对α推导出α’记为αα’ ，若推导序列长度大于0，则记为α  α’。
- 推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。

Chomsky文法体系分类

该体系对生成式（产生式）的形式做了一些规定，分为四类，即0型、1型、2型、3型文法
0型文法：无限制文法
对应的语言：递归可枚举语言，与图灵机等价。
1型文法:也称上下文有关文法（CSG：Context-sensitive Grammar)
- 生成式的形式为α→β，
  - 其中 |α|≤|β|，β∈（N∪T）+，
  - α∈（N∪T）N+（N∪T）*
- 限定约束：
  - 左部的长度小于右部
  - 不含A->ε
2型文法：也称上下文无关文法（CFG：Context-free Grammar)
- A→α,
- A∈N, 且α∈（N∪T）*
- 左部是单个非终结符。
3型文法：
- 右线性文法（Right-linear Grammar）：
```
A→ωB 或 A→ω
    A、B∈N, ω∈T*。
```
- 左线性文法（Left-linear Grammar）：
```
A→Bω或 A→ω
        A、B∈N, ω∈T*。
```
- 对应的语言：正则语言
- 对应的自动机：有限自动机（Finite Automaton）。
四类文法之间的关系
- 0型无限制
- 1型不允许A→ε形式
- 2型
- 3型属于2型
- 不含A→ε的2型、3型属于1型，1型、2型、3型均属于0型。

第三章有限自动机与右线性文法

第一节有限自动机

有限自动机的概念：
- 具有离散输入输出系统的一种数学模型
  (可以没有输出，比较特殊的也可以没有输入).
- 有限的状态
- 后继状态唯一：DFA
- 后继状态不唯一：NFA
FA的模型：FA可以理解成一个控制器，它读一条输入带上的字符。

DFA的形式定义

定义: DFA是一个五元组 M=(Q,T,δ,q0,F)
- Q: 有限的状态集合
- T: 有限的输入字母表
- δ: 转换函数(状态转移集合): Q×T Q
- q0: 初始状态， q0 Q
- F: 终止状态集, F  Q
δ’函数：接收一个字符串的状态转移函数。
- 对任何q Q，定义：
  - 若ω是一个字符串, a是一个字符
    定义: δ’(q,ωa)=δ(δ’(q,ω),a)
DFA接收的语言：
- 被DFA接收的字符串: 输入结束后使DFA的状态到达终止状态。否则该字符串不能被DFA接收.
- DFA接收的语言: 被DFA接收的字符串的集合.
格局：为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当前状态q，待输入字符串w。两者构成一个瞬时描述，用（q,w）表示，称为格局。
- 初始格局：（q0,w)
- 终止格局： (q,ε), qF
  
  描述格局的这个符号长得还挺奇特

第二节不确定的有限自动机NFA

修改DFA的模型，使之在某个状态，对应一个输入，可以有多个转移，到达不同的状态，则称为不确定的有限自动机。

NFA是一个五元组，M=(Q,T,δ,q0,F)。
其中δ是的函数，其余与DFA相同
如果接收一个字符串后NFA进入一个状态集，而此集合中包含一个以上F中的状态，则称NFA接收该字符串。

用格局描述NFA，则要分别描述每个可能的状态：

第三节 NFA和DFA的等价性

定理：设一个NFA接受语言L，那么必然存在一个DFA接受L。

NFA构造DFA 子集构造法

表示初态，*表示终态

实践中, 通过子集构造法得到的 DFA 的状态数目与原NFA 的状态数目大体相当.
在较坏的情况下,上述 DFA 的状态数目接近于所有子集的数目.

证明不放了。估计不考。

第四节有转换的NFA

定义：概念：当输入空串(无输入) 时，也能引起状态的转移。
的形式定义：一个是一个五元组 .
- 与 NFA 的不同之处

闭包的概念

状态 q 的 - 闭包，记为 - CLOSURE 或ECLOSE ，定义为从 q 经所有的路径可以到达的状态（包括q自身）
状态子集I
- 概念：
  - 其中 $，$ . 即P是从I中的状态经过一条标a的边可以到达的状态集合
  - 即
扩展转移函数适合于输入字符串

注意一下这个注意

从NFA构造等价的无NFA

关键点就一句话：
δ1’（q0，ω）含F1的一个状态当且仅当δ’（q0， ω）含F的一个状态
这里F1指的是带,F是指不带的。

抽道题：

过程差不多就是遍历T，保证对于所有可以到达的状态，也可以通过相同符号到达就行了。

还要注意的就是，如果起始状态的闭包里有终止状态，那NFA里要把起始状态改成终止状态

第五节正则集和正则式

正则集：字母表上一些特殊形式的字符串的集合，是正则式所表示的集合。
正则式：用类似代数表达式的方法表示正则语言。
归纳正则表达式如下：
- ε，，a （a∈T）都是正则式 (原子正则式) ，
  相应的正则集为{ε}，，{a}
- 如果A和B是正则式，且分别代表L(A)和L(B).则(A+B)，(AB)， A* 也是正则式，分别表示以下正则集
  - L(A) ∪L(B) (语言A / 语言B的串)
  - L(A) • L(B) (两个语言中的串的连接)
  - L(A) * (语言A中的串的多次连接)
正则式的性质：

幺元这个东西感觉有点玄幻
然后这个东西在因式分解的时候当1使

右线性文法导出正则式

右(左)线性文法又称为正则文法，右线性文法与正则式可以用来代表同一正则语言。二者具有等效性。

求解规则R：
设x = αx+β，α∈T，β∈(N∪T), x∈N
则x的解为 $＝$

设右线性文法G=({S,A,B},{a,b},P,S}，生成式P如下： S→aA , S→bB, S→b, A→bA, A →, B→bS

以上生成式写成联立方程为
S=aA+bB+b （1）
A=bA+ （2）
B=bS （3）

对式（2）利用规则R和性质 α = α得 A=b* （4）
将式（4）和式（3）代入式（1）中的A、B，得
S=ab*+bbS+b=bbS+ab*+b=(bb)(ab+b)
所以由G产生的语言用正则式表示为 (bb)(ab*+b)

第六节正则集和右线性文法

正则集是由右线性文法产生的语言
由右线性文法产生的语言都是正则集

证明略了。

提了两句互相转换。

正则集右线性文法：找出相应的右线性文法，使之产生的语言是这些正则集。

也就是说没啥好方法，看点子

右线性文法正则集：对右线性文法构造标准形式的正规表达式方程组，应用规则 $＝＝$ 进行消元，求解方程组，即可得出正规表达式。

定理: 一个语言是正则集，当且仅当该语言为右线性语言。

正则集到有线性文法的例子：

第七节正则表达式与有限自动机的关系

有限自动机、右（左）线性文法、正则表达式都定义了同一种语言– 正则语言.

DFA构造等价的正则表达式

扩展自动机的概念，允许正则表达式作为转移弧的标记。这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变
在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补。

步骤：

eg:

从正则表达式构造等价的

定理: L 是正则表达式 R 表示的语言, 则存在一个 - NFA E ,满足 L(E) = L(R) = L.
构造：

就是用一大堆。能用的全用上了。

eg：

上述表明三种定义正则集的方式：

正则表达式
右线性文法
正则集是含有{ε}，，{a} 以及在并、连接和 * 运算下封闭的语言
完事了还有第四种，可以用自动机定义。挺明显了上面讲了一大堆自动机和正则式的转换

右线性文法有限自动机

看题就懂了。

注意要单独捏造一个最终状态

对于右边接的是字符串的，单独开个状态：

有限自动机右线性文法

看题就懂了。

第九节右线性语言的性质

确定有限自动机DFA的化简

简单来说就是先将不可达状态删了之后，把同一分区的都合并。

等价和可区分：
- 设DFA M = (Q，T，δ，q0，F)
  - 对不同的状态q１， q２∈Q 和每个ω∈T*，如果有(q１，ω)┣ (q，ε) 和 (q２，ω)┣ (q，ε) 且q∈F，
    则称q１与q２状态等价. 记为q１≡q２
    否则，称q１， q２可区分。
不可达状态：如果不存在任何ω∈T，使(q０，ω)┣* (q，ε)，则称状态q∈Q为不可达状态。
最小化：若DFA Ｍ不存在互为等价状态及不可达状态，则称DFA Ｍ是最小化的。