【最新】有限自动机理论-2章形式语言

u|v|w|x|y|z D→0|1|2|3|4|5|6|7|8|9
41
2021/2/2
思考：
上例是从标识符的形成角度思考问题。 从标识符的定义角度考虑，则？
42
2021/2/2
注意
D→0|1|2|3|4|5|6|7|8|9 不能简写为
D→0|…|9
43
2021/2/2
将I的定义加入到表达式中：
①( )是该语言的最基本的句子； ②若S是句子,则(S)是句子； ③若S是句子,则SS是句子；
11
2021/2/2
这些规则称为形成规则，根据这些 规则，可以
产生该语言的任意的句子；
判断某个串是否是该语言的句子-语法分析。
12
2021/2/2
例如
可以产生句子（（）） 而推断串 （（））） 不是句子。
它们组成的集合就称为一个语言。
22
2021/2/2
S称为非终结符，在推导过程中，可以被 代替的符号。
(和)称为终结符，在推导过程中，不可以 被代替的符号。
→ 是产生式系统的元符号，不属于非终 结符，也不属于非终结符。
23
2021/2/2
例2-1：由偶数个0组成的串的语言。 规则的自然语言描述方式：
①00是该语言的基本的句子； ②若S是句子,则00S是句子。
24
2021/2/2
形式化的描述方式： S→00 S→00S
25
2021/2/2
问题：
将产生式S→00S换成 S→0S0或S→S00或S→SS
是否还产生相同的语言？
26
2021/2/2
结论：
一个语言，可以使用不同的产生式组 合来产生。
15
2021/2/2
使用尖括号“<”和“>”包括起来的部分，作 为一个整体来看待，表示某个语法成分
需要使用字母表中的字母来定义其构成
符号“::=”是BNF本身的符号（元符号）， 代表“定义为”或“是”。
符号“( ”和“ )”是字母表的元素。
16
2021/2/2
Chomsky采用的符号化(形式化)的描述 方式，运用规则（称为产生式）：
13
2021/2/2
规则(的个数)是有限的，但可以产生无 限个句子、甚至长度无限的句子
因为规则是递归的。
14
2021/2/2
BNF的描述方式
巴科斯和诺尔采用的巴科斯-诺尔范式 (BNF--Backus-Naur Form)描述规则：
<括号匹配串>::= ( ) <括号匹配串>::=(<括号匹配串>) <括号匹配串>::=<括号匹配串><括号匹配串>
74
2021/2/2
第二类问题
构造产生语言L的文法。 L= {wwT|w∈{a,b,c}+}
其中：wT是w的逆（反序）
75
2021/2/2
思考：
产生下列语言的文法： L1={anbn|n>0} L2={anbn|n≧0}
约定：如果没有特别说明,则
小写的英文字母u，v，w，x，y，z代 表终结符串；
小写的希腊字母α，β、ᵞ 代表非终结符 和终结符串；
58
2021/2/2
推导（派生）的定义2-2
文法G，α和β是集合(∑∪V)上的串 α= pvr ，β=pur(p和r可能同时为ε) 而v→u是文法G的一个产生式, 则称α直接推导出β
生
69
2021/2/2
对于文法G=(∑，V，S，P) 约定：
第一个产生式左边的符号，就是开 始符号（可以不是S）；
大写的英文字母代表非终结符。
70
2021/2/2
对于文法（G），只需给出该文法的 所有产生式即可。 产生括号匹配语言的文法可以写成
S→( ) S→(S) S→SS
71
2021/2/2
第一个产生式的左边只能有一个符号， 就是开始符号S。
55
2021/2/2
文法的作用就是产生一个语言。
56
2021/2/2
约定：如果没有特别说明,则
第一个产生式左边的符号，就是开始符 号，可以不为S；
大写的英文字母代表非终结符； 小写的英文字母a，b，c，d，e和数字 代表终结符；
57
2021/2/2
36
2021/2/2
其中： E代表表达式，T代表项，F代表因子 (E)代表的是带小括号的表达式 表示：先因子，再*、/，最后+、-
37
2021/2/2
如果使用%代表模运算(即取余数运算)、 使用^代表指数运算，则有
E→E+T|E-T|T T→T*F|T/F|T%F|A A→F^A|F F→(E)|i
L(G)={ω|S=>*ω，且ω∈∑*}
67
2021/2/2
例
文法 G= ({(,)},{S},S,{ S→( ), S→(S), S→SS })
产生语言 L(G)={w|w是括号匹配的串}
68
2021/2/2
注意:
文法G产生语言L，必须满足： ①G推导产生的所有句子都在L中 ②L的任意句子都可以由G推导产
记为α=>β ，即 pvr =>pur
59
2021/2/2
推导的实质 产生式的右边替换产生式的左边
60
2021/2/2
非终结符代表在推导的过程中可以被 替代的符号，
终结符代表在推导的过程中不可以被 替代的符号。
61
2021/2/2
推导的逆过程称为归约。
与pvr =>pur对应，串pur可以直接 归约成串pvr
A→+|-|*|/
+、-、*、/ 称为A的侯选式。
33
2021/2/2
E→ i E→EAE E→(E) 也可以记为： E→ i|EAE|(E)
34
2021/2/2
注意：
这组产生式 没有表示出运算符的优先级。
35
2021/2/2
表示出运算符的优先级的产生式： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i
P是有序偶对(α，β)的集合：α是集合 (∑∪V)上的字符串，至少包含一个非 终结符；β是集合(∑∪V)*的元素
一般，将有序偶对(α，β)记为
α→β
称为产生式；
53
2021/2/2
如果有α→ε，称之为空串产生式或者 ε产生式。
如果有A→B，称之为单产生式。
54
2021/2/2
一个产生式的左边可能不只一个符号；
5
2021/2/2
本章介绍形式语言的基本内容。
6
2021/2/2
语言的形式定义
设是一个字母表， L*, L称为字母表上的一个语言, wL, w称为语言L的一个句子。
7
2021/2/2
2.1 例子语言
括号匹配串的语言。 该语言是指所有的左括号和右括号相
匹配的串的集合； ( )，(( ))，( )( )等等都是该语言的句子 )( ，( ))等等不是该语言的句子。
形式语言所研究的问题。
3
2021/2/2
接收一个语言
使用某种自动机模型来接收字符串， 该模型所接收的所有字符串，也形成一 个语言。
自动机所研究的问题。
4
2021/2/2
统一的理论
形式语言与自动机作为统一的理论, 实际上包括3个方面的内容: 1) 形式语言理论(产生语言) 2) 自动机理论(接收语言) 3) 形式语言与自动机的等价性理论
30
2021/2/2
形式语言的描述方式
① E→ i （i代表单个变量） ② E→EAE ③ E→(E) ④ A→+ ⑤ A→⑥ A→* ⑦ A→/
31
2021/2/2
思考：
字母表为？ 若以A开始推导，则产生？
32
2021/2/2
其中 ： A→+，A→-，A→*，A→/ 四个产生式
的左边是相同的符号，可以合并为
51
2021/2/2
定义2-1 短语结构文法(文法)的定义
文法G是一个四元式，
G=(∑，V，S，P)
∑是有限字符的集合(字母表)， 元素 称为字母或者终结符；
V是有限字符的集合--非终结符集合， 元素称为变量或者非终结符；
52
2021/2/2
短语结构文法(文法)的定义
S∈V，称为文法的开始符号；
49
2021/2/2
2.2 文法和语言的关系
语言的定义 文法的定义 文法与语言的关系
50
2021/2/2
对于语言，在字母表上，按照一定的 构成规则，根据语言句子的结构特点， 可以定义一个产生该语言的文法。
使用文法作为语言的有穷描述，不仅 可以描述出语言的结构特征，而且可以 产生这个语言的所有句子。
最终可以产生括号匹配的的句子。
20
2021/2/2
例:句子(( ))(( )( ))的推导过程
S =>SS =>(S)S =>(( ))S =>(( ))(S) =>(( ))(SS) =>(( ))(( )S) => (( ))(( )( ))
21
2021/2/2
产生式的个数是有限的，规则是递归 的，所有的小括号匹配的串，都可以由 产生式产生；
① S→( ) ② S→(S) ③ S→SS
17
2021/2/2
“→”代表“定义为”或者“是” ，
它的左边和右边分别称为该产生式的 左边和右边
18
2021/2/2
根据产生式
可以生成任意句子； 可以判断一个串是否为句子
19
2021/2/2