自动机考试

填空选择问答

1. 绪论

1.1 语言和形式语言

  1. 语言是字集齐组合规则的统一体

1.2 字母表

  1. 字母表是一个非空有穷集合,具有非空性有穷性

  2. 字符具有整体性可辨认性

  3. 正闭包:+=234\sum^+ = \sum \cup \sum^2 \cup \sum^3 \cup \sum^4 \cup \cdots

  4. 克林闭包:正闭包 0\cup \sum^0

    =0+=0234\sum^* = \sum^0 \cup \sum^+ = \sum^0 \cup\sum \cup \sum^2 \cup \sum^3 \cup \sum^4 \cup \cdots

1.3 句子

  1. 字符的总个数成为句子的长度,记为x|x|
  2. 前缀、后缀,公共前缀、公共后缀与集合中的子集相同
  3. 两个句子含有同一个串,这个串称为公共子串,如果这个串是最长的,那么称为最大公共子串

2. 文法

2.1 形式定义

文法 GG 是一个四元组:

G=(V,T,P,S)G = (V, T, P, S)

VV——变量(variable),AV\forall A \in VAA 叫做语法变量或者非终极符号或者语法范畴
TT——终极符号(terminal)是非空有穷集合。aT\forall a \in T aa 称为终极符号,是组成一个串或者句子的元单位
PP——产生式(production),形式为 αβ\alpha \to \beta
SS——SVS \in V,文法 G 的开始符号,表示语言被定义的地方

2.2 句型

如果可以从开始符号推导出一个串,那么这个串称为 GG 产生的一个句型

2.3 乔姆斯基体系

  1. 没有任何限制的文法称为 0 型文法,语言叫做 0 型语言

  2. 对于 0 型文法,经过产生式后句子长度不减少,叫做上下文有关文法,语言叫做上下文有关语言,也被称为 1 型文法,语言叫做 1 型语言

    对于 αβP\forall \alpha \to \beta \in P,均有 βα|\beta| \ge |\alpha|

  3. 对于 1 型文法,如果左部都是变量,那么叫做上下文有关文法语言叫做上下文有关语言,也被称为 2 型文法,语言叫做 2 型语言

    对于 αβP\forall \alpha \to \beta \in P,均有 βα|\beta| \ge |\alpha|,并且有 αV\alpha \in V

  4. 对于 2 型文法,如果产生式只产生终极符号终极符号后接变量,那么叫做正则文法,语言叫做正则语言,也叫做 3 型文法

    对于αβP\forall \alpha \to \beta \in P, αβ\alpha \to \beta均具有形式:
    AwA \to w
    AwBA \to wB

    注:正则文法又叫右线性文法
    如果变量在左边就叫左线性文法
    两个串中间夹一个变量就是线性文法

可以看到,文法的乔姆斯基体系是逐步收紧限制的

2.4 推导、归约和文法构造

这些都比较简单,慢慢推就行了。
构造看结构想想就行了。

3. 有穷状态自动机

3.1 物理模型

有穷状态自动机由以下结构构成:

  1. 右端无穷输入带
  2. 有穷状态控制器
  3. 读头

3.2 形式定义

有穷状态自动机是一个五元组

M=(Q,,δ,q0,F)M = (Q, \sum, \delta, q_0, F)

QQ——状态的非空有穷集合,qQ\forall q \in Q, qq 称为 MM 的一个状态
\sum——输入字母表
δ\delta——状态转移函数,读入字符后经过转移函数处理进行状态转移
q0q_0——开始状态
FF——终止状态,又称接受状态

3.3 DFA

对于状态集合中的任何一个状态,状态转移函数均有一个确定的值

3.4 NFA

  1. 形式定义

    δ\delta——状态转移函数,对于(q,a)Q×,δ(q,a)={p1,p2,,pm}\forall (q,a) \in Q \times \sum, \delta(q,a) = \{p_1, p_2, \cdots, p_m\}
    其余与 DFA 相同

  2. 与 DFA 的区别

    1. 并不是所有在状态集合中的状态对应某个输入都有状态转移函数结果与之对应
    2. 并不是对于所有的状态转移结果都只对应一个状态

3.5 ϵNFA\epsilon-NFA

  1. 形式定义

    qQ,δ(q,ϵ)={p1,p2,,pm}\forall q \in Q, \delta (q, \epsilon) = \{ p_1, p_2, \cdots, p_m \},表示 MM 在状态 qq 不读入任何字符的情况下也能选择进行状态转移

3.6 补充

  1. FA 接受的语言是正则语言

4. 正则表达式

4.1 形式定义

  1. \varnothing\sum 上的正则表达式,表示语言\varnothing

  2. ϵ\epsilon\sum 上的正则表达式,表示语言 {ϵ}\{ \epsilon \}

  3. 对于a,a\forall a \in \sum , a\sum 上的正则表达式,它表示语言 {a}\{ a \}

  4. 如果 rrss 分别是 \sum 上的表达语言 RRSS 的正则表达式,那么

    (r+s)(r + s) 表达的语言是 RSR \cup S
    (rs)(rs) 表达的语言是 RSRS
    (r)(r^*) 表达的语言是 RR^*

  5. 只有满足以上四条,才是正则表达式

5. 正则语言的性质

5.1 封闭性

RL 在交、并、补,乘积、闭包运算都是封闭的

5.2 Myhill-Nerode 定理

如下三个命题等价

  1. LL \subseteq \sum^* 是 RL
  2. L 是 \sum^* 上的某个具有有穷指数的又不变等价关系 R 的某些等价类的并
  3. RLR_L 具有无穷指数

6. 上下文无关语言

6.1 二义性

对于 CFG G=(V,T,P,S)G = (V, T, P, S),如果存在 wL(G)w \in L(G)ww 至少有两颗不同的派生树,则称 GG二义性的,否则则为非二义性的

如果语言 LL 不存在非二义性文法,则称 LL固有二义性的,或者先天二义性的

6.2 乔姆斯基范式(CNF)

形式定义:

如果 CFG G=(V,T,P,S)G = (V, T, P, S)中的所有产生式都具有形式:

ABCAa\begin{aligned} A &\to BC \\ A &\to a \end{aligned}

则称为乔姆斯基文法或者乔姆斯基范式

6.3 格雷巴赫范式

形式定义:

如果 CFG G=(V,T,P,S)G = (V, T, P, S) 具有形式

AaαA \to a\alpha

则称 GG格雷巴赫范式文法,简称格雷巴赫范式

7. 下推自动机

7.1 物理模型

下推自动机有三个基本结构:

  1. 存放输入符号串的输入带
  2. 存放文法符号
  3. 有穷状态控制器

7.2 形式定义

下推自动机是一个七元组:

M=(Q,,Γ,δ,q0,Z0,F)M = (Q,\sum, \Gamma, \delta, q_0, Z_0, F)

QQ——状态集合
\sum——输入字母表
Γ\Gamma——栈符号表
δ\delta——状态转移函数
q0q_0——开始状态
Z0Z_0——开始符号
FF——终止状态

8. 上下文无关语言性质

8.1 封闭性

  1. 交运算、补运算不封闭

  2. 并、乘积、闭包运算封闭

9. 图灵机

9.1 物理模型

基本模型包括:

  1. 有穷状态控制器(FSC)
  2. 含有无穷多个带方格的输入带
  3. 读头

9.2 形式定义

图灵机是一个七元组:
M=(Q,,Γ,δ,q0,B,F)M = (Q, \sum, \Gamma, \delta, q_0, B, F)

QQ——状态集合
\sum——字母表
Γ\Gamma——带符号表,如果XΓ\forall X \in \Gamma, XXMM 上的一个带符号,表示在 MM 的运行过程中, XX 可以在某一时刻出现在输入带上
δ\delta——转移函数
q0q_0——开始状态
BB——空白符
FF——终止状态

9.3 即时描述

TM M=(Q, , Γ, δ, q0, B, F),a1a2Γ,qQ,a1a2TM\ M = (Q, \ \sum, \ \Gamma, \ \delta, \ q_0, \ B, \ F), a_1a_2 \in \Gamma^*, q \in Q, a_1a_2

称为 MM即时描述

10. 上下文有关语言

10.1 线性有界自动机的形式定义

线性有界自动机是一种非确定的图灵机,满足如下两个条件:

  1. 输入字母表(\sum) 中包含两个人特殊的符号 (打不出来,C 画一条斜线) 和 $\$, 其中,(C 画一条斜线)作为输入符号串的左端标识,$\$,作为输入符号串的右端标识
  2. LBA 的读头只能在上面两个符号之间移动,而且 LBA 不能在上面两个断点符号上面打印另外一个符号

LBA 可以被看做一个八元组,其接受的语言为:

Hehe

线性有界自动机和上下文有关文法等价

大题

大题考点

  • ϵ\epsilon-NFA 转 NFA
  • NFA 转 DFA
  • 正则语言转 FA
  • DFA 转正则语言
  • 泵引理证明一个语言不是 RL
  • DFA 极小化
  • 上下文无关语言的文法化简
  • 泵引理证明一个语言不是上下文无关语言

1. ϵ\epsilon-NFA 转 NFA

步骤:

  1. 先找空闭包(包括它本身),得到一个集合
  2. 寻找这个集合的对于某个特定输入的转移,得到另一个集合
  3. 对于 2 的集合寻找其空闭包(包括它本身),得到第三个集合

第三个集合即为某个状态对于上面的特定输入的状态转移

找出所有非空输入的状态为止

2. NFA 转 DFA

步骤:

  1. 由 NFA 的初始状态出发,找出初始状态对应输入的集合

  2. 由对应的输入集合出发,继续根据输入写出对应的转移

  3. 重复 2 直到找完所有集合为止

  4. 含有终止状态的集合均为终止状态

  5. 勾出可达状态。

    可达状态即为从初始状态能到达的所有状态集合

3. 正则语言转 FA

3.1 DFA 转正则文法

  1. qsq_s 开始状态开始

  2. 根据输入和相应的转移状态写文法

    每一个转移对应文法为:输入,状态(没有逗号)

  3. 如果转移到终止状态,则写终止符号

    终止符号为转移到终止状态的输入

  4. 如果终止状态有闭包,则除了终止符号外,还要加上相应的 【输入,状态】

  5. 终止状态有转移则写终止状态,没有则不用写

  6. 如果有不可达状态,写出之后要删去

    不可达状态即只能写出自身闭包的文法

3.2 正则文法转 FA

根据相应文法写出状态转移函数即可

  1. 引入一个终止状态 ZZ

  2. 根据文法写出状态转移函数

    形式如下:
    δ(\delta(变量,输入)) == {\{转移后状态}\}
    例如:
    E0AE \to 0A
    δ(E,0)={A}\delta(E,0) = \{A\}

  3. 如果遇到终止符号,则在右方集合中写上终止状态ZZ

    例如:
    A11CA \to 1|1C
    δ(A,1)={Z,C}\delta(A,1) = \{Z,C\}

3.3 正则表达式转 FA

分析结构,有以下几种状况

  1. 遇到加号就分叉
  2. 乘号在后面加一段相应字符的转移
  3. 克林闭包意味着循环和可跳过
  4. 正闭包意味着循环和至少需要经过一次(即不可跳过)
  5. 最后合并到终止状态

3.4 DFA 转正则表达式

根据 DFA 的图转换成正则表达式

  1. 预处理

    1. 用状态 XXYY 将图“括起来”

      XX 用空转移指向初始状态,所有的终止状态用空转移指向 YY

    2. 去掉所有的不可达状态

  2. 并弧

    将两个状态的平行弧(方向一致),或者有逗号的,将其输入用加号连起来

  3. 去掉点

    对于到达 YY 的路径,将输入拼起来即可
    关于消去这个点之后,将其他经过这个点到达的路径的输入拼起来
    如果有闭包,则在对应的输入上使用克林闭包
    如果除了 XX YY 只有一种状态,而且没有经过这种状态从 XX 到达 YY 的路径,则将这个点和对应的路径直接删去即可

  4. 不断重复 2 和 3

  5. 最后只剩下 XXYY,则输入则为正则表达式

4. 泵引理证明一个语言不是 RL

利用泵引理反证法证明一个语言不是 RL

  1. 利用正整数 NN 构造一个特殊的 zz

    一般将语言中的未知数替换成 NN 即可,有时也需动点脑筋

  2. 利用 v1|v| \ge 1uvN|uv| \le N 说明 vv 必定为某个式子。

    式子为符号的幂,下同

  3. z=uvwz = uvw 得出 uu vv ww 的对应的式子

  4. uviwuv^iw 得出化简后的相应式子

    注意不要消掉 2 中的设定的参数

  5. 选择一个恰当的 ii 说明 4 中的关系和 1 中的关系矛盾

  6. 证明完成

5. DFA 的极小化

对于一个 DFA 的图进行简化

  1. 去掉不可达状态

  2. 在可区分状态表标记所有终止状态的行和列

    对于交界的格子,不进行标记

  3. 对于空的格子,根据相应转移函数算出对应结合

    相应转移函数:状态集合对应输入所得到的状态集合的函数
    对于[q0,q4][q_0,q_4],进行 δ(q0,\delta(q_0,输入)) δ(q4,\delta(q_4, 输入)) 来进行
    所得出的新的两个状态则为相应的转移后状态集合

    建议先算出所有的转移函数结果

  4. 如果算出来的集合未被标记,增加到关联表中

    关联表:算出的新集合 \to 原集合
    如果新的“原集合”算出一个已经算出过的“新集合”,继续接到后面去
    注意,以某个集合为起点的关联表才是它的关联表。

  5. 如果算出来的集合已经被标记了,那么就把它标记,并根据标记的集合的关联表进行递归标记

    如果根据某个输入得出该组集合已经被标记,就没有必要去看另一组输入的结果了。

  6. 如果算出的集合跟原集合相等,不进行任何操作

  7. 如果转移函数得到相等结果,不进行任何操作

  8. 此时算法结束,根据可区分状态表中没有标记的组,列出来,说明它们恒等

    如果没有未标记的组,说明当前图已经是最简了

  9. 根据 \equiv 的传递性进行状态分组

    恒等的分成一组

  10. 如果还有落单的状态,另分组

  11. 分组完毕,根据原图根据分组的状态来画出简化图

6. 上下文无关文法的化简

步骤:

  1. 清除无用符号
  2. 清除 ϵ\epsilon 产生式
  3. 清除单一产生式
  4. 清除无用符号(如果有的话)

6.1 去无用符号

  1. 先清除非产生的

    非产生的:从这个符号开始,进行推导不能得出只有终结符号的,被称为非产生的

    注意含有非产生符号的式子要一并清除

  2. 再清除不可达的

    不可达的,即由 SS 不能达到的

6.2 清除 ϵ\epsilon 产生式

注意,如果清除之后出现无用符号,那么就应该为它加上某个它自身能推导出来的终结符
并考虑到它的可能为空的特性,在上级符号中加入不含这个符号的产生式

6.3 清除单一产生式

形如 ABA \to B 即为单一产生式,可以将 BB 的内容合并到 AA 中。
不断重复,直到没有单一产生式为止

7. 用泵引理证明一个语言不是上下文无关语言

这里的泵引理是 CFL 的泵引理