第02章+形式语言与自动机理论

10
第10页
1．形式语言
什么是形式语言 形式语言: 形式化描述字母表上字符串集合。 字母表：字符有限集合。
e.g.：26个英文字母组成字母表。
字符串：字母表中字符组成有限序列。
e.g. hello, afjhkfyu
形式语言和自动机
College of Computer Science & Technology, BUPT
连接请求
q0
断开 连接
q1
收到 应答
q2
传输数据
形式语言和自动机
College of Computer Science & Technology, BUPT
22
第22页
依据结构不一样，自动机又可分为有限自动 机，下推自动机，图灵机等。
下推自动机能够看作是由一条输入带，一个 有限控制器和一个下推栈组成。
基本图灵机由一个含有读写头有限控制器和 一条无限带组成。
使用自动机，能够形式化描述现实世界中一 些问题。
形式语言和自动机
College of Computer Science & Technology, BUPT
23
第23页
3．形式语言与自动机关系
形式语言和自动机是亲密相关。 形式语言 ―― 字符串 自动机 ―― 字符串识别系统
4
第4页
经典参考书
书名 Introduction to Automata Theory,
Languages, and Computation （Second Edition）
作者
John E. Hopcroft （Cornell） Rajeev Motwani （Stanford） Jefferey D. Ullman （Stanford）

d0，d1} {aa，ab，bb}{0,1}={ aa0，aa1，ab0，ab1，bb0，
bb1}
1.4.3 基本概念
• 字母表∑的n次幂
∑0={ε} ∑n=∑n-1∑ ε是由∑中的0个字符组成的。
• ∑的正闭包
∑+=∑∪∑2∪∑3∪∑4∪…
• ∑的克林闭包
∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪…
•创新意识的建立和创新能力的培养也在这个教育过 程中循序渐进地进行着。
•内容用于后续课程和今后的研究工作。 •是进行思维训练的最佳知识载体。
•是一个优秀的计算机科学工作者必修的一门课程。
1.4.3 基本概念
• 对语言研究的三个方面
– 表示(representation)—— 无穷语言的表示。 – 有穷描述(finite description) ——研究的语言要
• 计算思维能力
–逻辑思维能力和抽象思维能力 –构造模型对问题进行形式化描述 –理解和处理形式模型
课程目的和基本要求
• 知识
–掌握正则语言、下文无关语言的文法、识别模 型及其基本性质、图灵机的基本知识。
• 能力
–培养学生的形式化描述和抽象思维能力。 –使学生了解和初步掌握“问题、形式化描述、
自动化（计算机化）”这一最典型的计算机问 题求解思路。
• 相应的理论用于其他方面。
1.4.2 形式语言与自动机理论的 产生与作用
• 形式语言与自动机理论在计算机科学与技术 学科的人才的计算思维的培养中占有极其重 要的地位。
• 计算学科的主题：“什么能被有效地自动 化”。
1.4.2 形式语言与自动机理论的 产生与作用
• 计算机科学与技术学科人才专业能力构成
• 语言是一定的群体用来进行交流的工具。 • 必须有着一系列的生成规则、理解(语义)

S =>SS =>(S)S =>(( ))S =>(( ))(S) =>(( ))(SS) =>(( ))(( )S) => (( ))(( )( ))
产生式的个数是有限的，规则是递归 的，所有的小括号匹配的串，都可以由 产生式产生；
它们组成的集合就称为一个语言。
• S称为非终结符，在推导过程中，可以被 代替的符号。
S→( ) S→(S) S→SS
还可以再简写成 S→( )|(S)|SS
文法和语言的3类问题
已知文法 得到该文法产生的语言
已知语言 构造产生该语言的某个文法
判断一个语言是否由某一个文法产生
第一类问题
文法 S→aSa|bSb|c
产生的语言是什么？ 需要考虑所有产生式的所有可能
使用情况（包括顺序和次数）
u|v|w|x|y|z D→0|1|2|3|4|5|6|7|8|9
思考：
上例是从标识符的形成角度思考问题。 从标识符的定义角度考虑，则？
注意
D→0|1|2|3|4|5|6|7|8|9 不能简写为
D→0|…|9
将I的定义加入到表达式中：
E→E+T|E-T|T T→T*F |T/F|F F →(E)|I I→L|IL|ID L→… D→…
使用文法作为语言的有穷描述，不仅 可以描述出语言的结构特征，而且可以 产生这个语言的所有句子。
定义2-1 短语结构文法(文法)的 定义
文法G是一个四元式， G=(∑，V，S，P)
∑是有限字符的集合(字母表)， 元素 称为字母或者终结符；
V是有限字符的集合--非终结符集合， 元素称为变量或者非终结符；
• 规则(的个数)是有限的，但可以产生无 限个句子、甚至长度无限的句子

• 知识
–掌握正则语言、下文无关语言的文法、识别模 型及其基本性质、图灵机的基本知识。
• 能力
–培养学生的形式化描述和抽象思维能力。 –使学生了解和初步掌握“问题、形式化描述、
自动化（计算机化）”这一最典型的计算机问 题求解思路。
13.11.2020
4
主要内容
• 语言的文法描述。 • RL
– RG、 FA、RE、RL的性质 。
•考虑的对象的不同，所需要的思维方式和能力就不 同，通过这一系统的教育，在不断升华的过程中， 逐渐地培养出了学生的抽象思维能力和对逻辑思维 方法的掌握。
•创新意识的建立和创新能力的培养也在这个教育过 程中循序渐进地进行着。
•内容用于后续课程和今后的研究工作。 •是进行思维训练的最佳知识载体。
•是一个优秀的计算机科学工作者必修的一门课程。
13.11.2020
16
1.4.3 基本概念
• 字母表(alphabet)
– 字母表是一个非空有穷集合，字母表中的元素 称为该字母表的一个字母(letter)。又叫做符号 (symbol)、或者字符(character)。
– 非空性。 – 有穷性。
• 例如：
{a，b，c，d} { a，b，c，…，z}
{0,1}
13.11.2020
17
1.4.3 基本概念
• 字符的两个特性
– 整体性(monolith)，也叫不可分性。 – 可辨认性(distinguishable)，也叫可区分性。
• 例（续）
{a，a′，b，b′} {aa，ab，bb} {∞，∧，∨，≥，≤}
13.11.2020
18
1.4.3 基本概念
• CFL
– CFG(CNF、GNF)、PDA、CFL的性质。