第02章 形式语言与自动机理论ppt课件.ppt

《第02章 形式语言与自动机理论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章形式语言与自动机理论基础主要内容：语言和文法有限自动机正则表达式语言和文法语言和文法的关系什么是语言？如何表述语言？什么是程序设计语言？如何表述程序设计语言？语言：符号串的集合。元素——符号串——该语言的一个句子。字母表——符号串中符号的来源。句子的构成——按一定规则。语言的描述工具——文法程序设计语言：程序的集合句子——程序（一个或长或短的字符串）。字母表——固定的字符集，语言可以使用的所有符号。编程时必须遵循一定的规则——语法规则和语义规则。语言的概念2.1语言（1）有穷字母表一个元素的非空有穷集合，其中的元素也称符

2、号。每个语言均有一固定的字母表。例：C语言的字母表由基本字符集（字母，数字，括号，专用字符+、*、……）、保留字（int、long、if、struct、static、typedef、sizeof、……）等组成。语言的概念2.1语言2．符号串的相关概念和术语通常用V、Σ或其他大写字母表示。例如V={0，1}，Σ={a，b，c，d，e}等。（2）符号串字母表中的符号组成的任何有穷序列。相关术语：长度：符号串中符号的个数。符号串x的长度表示为｜x｜，｜x｜=m≥0。空符号串：无任何符号的串，简称空串，用ε表示，

3、ε

4、=0省略写法：z

5、=x……z=……xz=……x……语言的概念2.1语言【例2-1】Σ={a，b，c，……，z}，x=“laugh”，则

6、x

7、=5Σ={I，you，he，am，is，are，a，student}，y=“Iamastudent”，空格不计算长度，则

8、y

9、=4。（3）符号串的运算连接：符号串x、y的连接xy为一个新的符号串，该串的前面部分为x，后面部分为y。成立的等式：

10、xy

11、=

12、x

13、+

14、y

15、εx=xε=x【例2-2】若x=“home”，y=“work”则

16、x

17、=4,

18、y

19、=4xy=“homework”

20、xy

21、=4+4=8语言的概念2

22、.1语言方幂：符号串x的方幂就是n个x自身连接次，表示为xn。规定x0=ε。【例2-3】若x=“ab”则x0=εx1=“ab”x2=“abab”x3=“ababab”……成立的等式：x1=x，x2=xx，x3=xxx，……若n>0，则有：xn=xxn-1=xn-1xx*表示x的任意多次方幂（可以是0次）x+表示x的任意非0次方幂。语言的概念2.1语言（4）符号串的集合若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。乘积：两符号串集U、V的乘积为UV={αβ

23、α∈U∧β∈V｝成立的等式：{ε}U=U

24、{ε}=UVn=VV……V（n个V）规定：V0={ε}V*=V0∪V1∪V2∪……V+=V1∪V2∪……【例2-4】若U={a，b}，V={c，d}则UV={ac，ad，bc，bd}语言的概念2.1语言闭包：若指定字母表Σ，则Σ*表示Σ上的所有有穷长的串的集合。Σ*=Σ0∪Σ1∪Σ2∪……∪Σn∪……Σ*称为集合Σ的闭包。Σ+=Σ1∪Σ2∪……∪Σn∪……Σ+称为集合Σ的正闭包。成立的等式：Σ*=Σ0∪Σ+，Σ+=ΣΣ*=Σ*Σ若符号串x是Σ*的元素,则表示为x∈Σ*,否则xΣ*。【例2-5】Σ={0,1}Σ*={ε,0,1

25、,00,10,11,000,001,100,………}语言的概念2.1语言语言的句子个数有限——枚举语言的句子有很多甚至是无穷多个——给出一些规则说明这个语言的句子的组成结构。规则——文法规则语言的定义方式2.1语言【例2-6】文法规则：<句子>∷＝<主语><谓语><主语>∷＝<代词>│<名词><谓语>∷＝<动词><宾语><宾语>∷＝<代词>│<冠词><名词><名词>∷＝student│English│computer<代词>∷＝I│you│he<动词>∷＝am│is│are│have│study<冠词>∷＝a│an│the文法

26、规则的作用：（1）严格定义了一个语言的句子的结构；（2）用适当条数的规则描述了一个语言的全部句子。语言的定义方式文法文法的形式定义文法的表示方法相关概念2.2文法文法能清晰地描述程序设计语言的语法构成易于理解。文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。基于文法实现的语言易于扩展文法概述表示语言中的语法单位的符号，常用尖括号“<>”括起。一个非终结符一般可以推导出终结符串。一个语言可使用的所有非终结符组成的集合称为

27、非终结符集，用VN表示。1．终结符不可分割的符号串，是组成句子的最基本的单位。一个语言允许使用的所有终结符组成的集合称为终结符集，用VT表示。2．非终结符文法的形式定义2.2文法3．规则（重写规则、产生式、生成式）形如α→β或α∷＝β或（α，β）的有序对，其中α：某字母表V的