形式语言与自动机第一课

先修课程：离散数学，计算机导论，数据结构
后续课程：编译原理

形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课

计算机科学的主要部分：

1. 构成计算机的概念、模型
2. 构成计算机的工程技术
3. 解决实际问题

核心内容：

1. 有限状态自动机
2. 正规语言
3. 正规表达式
4. 上下文无关文法
5. 上下文无关语言
6. 下推自动机
7. 图灵机
8. 计算问题分类

形式语言

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

是一种通用语言
有一定的描述范围

起因：语言学家想使用一套形式化方法来描述语言

最初的应用：编译，让机器按照语法规则将高级语言方便地翻译成机器语言

自动机

具有离散输入输出的数学模型
状态+输入+规则->状态迁移

可能的状态、运行的规则都是事先确定的，一旦开始运行就按照事先确定的规则工作

根据结构不同分为：

1. 有限自动机
2. 下推自动机：输入带，有限控制器，下推栈
3. 图灵机：有限控制器，无限带

形式语言与自动机的关系

形式语言——字符串
自动机——字符串的识别系统

一定类型的自动机和某种类型的文法具有等价性

证明方法

演绎证明

证明是命题的序列
已知的命题称为假设
最后一个命题称之为结论

• IF THEN
• IF AND ONLY IF：IF A THEN B，IF B THEN A

归纳定义与结构归纳法

集合的归纳定义：

1. 基础：直接定义集合中的元素（至少一个）
2. 归纳：从已知元素生成新元素的规则
3. 极小性限制：集合中的元素只能从1、2生成

结构归纳法：
对于归纳定义的集合S，要证明任何$x\in S$，满足性质$P(x)$

1. 若有直接定义$a\in S$，证明$P(a)$
2. 证明$if{a}_1,a_2,...\in Sthenf(a_1,s_2)\in S$=>$ifP(a_1),P(a_2),...thenP(f(a_1,a_2,...))$