形式语言与自动机 Part.1绪论, Part.2 语言与文法

课程名：形式语言与自动机

作者：Lupinus_Linn

许可证：CC-BY-NC-SA 3.0 创作共用-署名-非商业性-相同方式共享

• 署名（英语：Attribution，BY）：您（用户）可以复制、发行、展览、表演、放映、广播或通过信息网络传播本作品；您必须按照作者或者许可人指定的方式对作品进行署名。
• 非商业性使用（英语：Noncommercial，NC）：您可以自由复制、散布、展示及演出本作品；您不得为商业目的而使用本作品。
• 相同方式共享（英语：Sharealike，SA）：您可以自由复制、散布、展示及演出本作品；若您改变、转变或更改本作品，仅在遵守与本作品相同的许可条款下，您才能散布由本作品产生的派生作品。（参见copyleft。）

引用：

• 本文中部分文字与图片引用自北京邮电大学计算机学院王柏教授的《形式语言与自动机》课程课件。
• 绪论中的证明方法部分引自清华大学王生原老师课件。
• 部分题目插图引用自北京邮电大学出版社《形式语言与自动机 第二版》教材。

在此一并表示感谢，并不做商业用途。

本笔记所有内容的传送门

Part.1绪论, Part.2 语言与文法
Part 3.有限自动机
Part.4 正则语言，2DFA，Mealy&Moore机
Part.5 上下文无关语言与下推自动机(PDA)
Part.6 图灵机

Part 1. 绪论

1.1 课程核心内容

(序号指课本章节)

2. 语言，文法, 语言的运算(并、连接、闭包、…)， 推导， 句型， 句子
3. 有限自动机、三种类型（DFA/NFA/ɛ-NFA），极小化，相互关系
   右线性文法，正则式，文法与自动机、正则式的关系
   3型语言的性质（泵浦引理等）
   有输出的自动机
4. 推导树，二义性
   上下文无关文法的变换
   CNF/GＮF (GNF 本届考试不要求)
   下推自动机
   文法与自动机的关系 （本届PDA 转 CFG 考试不要求）
   文法特性（２型语言的泵浦引理等）
5. 图灵机 （本届仅5.1 基本图灵机）

1.2 形式语言

形式化描述的字母表上的字符串的集合

形式语言是某个字母表上的字符串的集合， 有一定的描述范围。

1.3 自动机

自动机是具有离散输入输出的数学模型。自动机接受一定的输入，执行一定的动作， 产生一定的结果。使用状态迁移描述整个工作过程。

自动机的本质：根据状态、输入和规则决定 下一个状态

状态： 一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”。

有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。

自动机和语言的关系

1.4 文法

文法是定义语言的一个数学模型，而自动机可 看作是语言的识别系统。

1.5 证明技术

“If – Then”命题

把 If部分作为已知的命题，把 Then 部分作为结论.

“If - And - Only - If ”命题

可分别证明如下两个命题：
1 if A then B，
2 if B then A.

欲证R ⊆ S

可证明如下命题： if x∈R then x∈S

欲证R = S

可分别证明如下两个命题：
1 if x∈R then x∈S
2 if x∈S then x∈R

逆否命题的证明

有时，证明原命题的逆否(contrapositive)命题更加方便。
欲证 if A then B ， 可证明如下命题： if not B then not A

反证法

欲证 if H then C ，可以把 H 和 not C 都作为已知的命题，把任何一个矛盾( contradiction ) 命题作为新的结论.

举例证明存在性&举反例否定任意性

集合的归纳定义

由 3 部分构成：
1 基础（basis） // 直接定义集合中的元素（至少1个）
2 归纳（induction）// 从已知元素生成新元素的规则
3 极小性限制 // 申明集合中的元素只能由1、2 生成

结构归纳法

对于归纳定义的集合S，欲证对于任意x∈S，满足性质P(x).
1 基础（basis） // 若有直接定义a∈S，则证明P(a)
2 归纳（induction） // 若归纳定义中有规则
$a_1,a_2,\dots ,a_n\in S,thenf(a_1,a_2,\dots ,a_n)inS$
则证明$ifP(a_1),P(a_2),\dots ,P(a_n)inSthenP(f(a_1,a_2,\dots ,a_n))成立$

Part 2.语言和文法

2.1 基本概念

• 字母表
• 字符串
• 闭包
• 语言
• 文法
• 推导和句型
• 句子

2.2 常用符号规定

• 字母表: Σ, Γ, . . .
• 字符: a, b, c, . . .
• 字符串: . . . , w, x, y, z
• 集合: A,B, C, . . .

2.3 Chomsky文法体系

Chomsky文法体系该体系对生成式（产生式）的形式做了一些规定， 分为四类，即0型、1型、2型、3型文法.

• 注意，四种文法从上到下是包含关系，询问类别时应该取尽量靠下的文法（范围较小的文法）。