形式语言与自动机04章 Chomsky文法体系及语言之间的运算-1

格式：ppt
大小：371.00 KB
文档页数：95

下载文档原格式

形式语言与自动机-课程介绍 ppt

出版社 Addison Wesley （2001）清华大学出版社（影印版）
John.E.Hopcroft, the Turing Award winner in 1986.
First Edition 中译本《自动机理论、语言和计算导引》徐美瑞等译科学出版社，1990
-
5
其它参考书
形式语言和自动机是密切相关的。形式语言 ―― 字符串自动机 ―― 字符串的识别系统
根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。
-
26
3.3 形式语言与自动机的关系
-
27
语言与有限自动机（Finite Automata）
的命题
-
32
演绎证明
概念一个证明（proof）是命题的序列，其中的每一个命题或者是已知的命题，或者是由前面出现过的命题使用逻辑公理和规则得出. 已知的命题集合称为假设（hypothesis）或前提（premise），最后一个命题称为该前提的结论（conclusion）.
-
33
“If – Then”命题
最初的应用：编译 ―― 让计算机按照语法规则将高级语言方便地翻译成机器语言。
-
15
为什么用形式语言
现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域
在计算机理论科学方面：
是可计算理论（算法―在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。
-
18
3.2. 自动机
自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。

形式语言与自动机理论-蒋宗礼-第四章参考答案

1.写出表示下列语言的正则表达式。

（吴贤珺02282047）⑴{0, 1}*。

解：所求正则表达式为：(0+1)*。

⑵{0, 1}+。

解：所求正则表达式为：(0+1)+。

⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。

解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。

⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。

解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。

⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。

解：所求正则表达式为：(0+1)*10110(0+1)*。

⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。

解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q0、q1、q2、q3、q4为终结状态考虑：q为终态时的正则表达式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*q为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*1q为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*2q为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*3q为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*4将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。

⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。

解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。

另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。

形式语言与自动机课件——语言及文法

L1 L2 ≠ L2 L1 语言的积不可交换。
形式语言与自动机课件——语言及文法
12
语言的基本运算
语言的幂：语言的幂可归纳定义如下: L0 = {ε} Ln = L·Ln-1 = Ln-1 · L n ≥1
上例中， L12 ={abab, abba, baab, baba} L22 ={aaaa, aabb, bbaa, bbbb}
形式语言与自动机课件——语言及文法
27
1型文法
也称上下文有关文法（CSG：Contextsensitive Grammar) 生成式的形式为α→β，其中 |α|≤|β|，β∈（N∪T）+， α∈（N∪T）*N+（N∪T）*
对应的语言：上下文有关语言（CSL： Context-sensitive Language)
22
四．推导与句型
1、直接推导
设G =（N,T,P,S）是文法，若A→β是P 中的生成式，α和γ是（N∪T）*中的字符串，则有αAγ=> αβγ称αAγ直接推导出αβγ，或说αβγ是αAγ的直接推导。
形式语言与自动机课件——语言及文法
23
2、推导序列
设 G = (N,T,P,S) 是文法， α、α0、α1…αn、α’ 都是（N∪T）*中的字符串，且α=α0、 α’ =αn，其中αi直接推导出αi+1 （0≤i≤n）,则称序列α0=>α1=>α2=>…=>αn是长度为n的推导序列，而α=α0是长度为0的推导序列。
形式语言与自动机课件——语言及文法
13
第二节文法
定义：所谓文法是用来定义语言的一个数学模型
表示语言的方法：若语言L是有限集合，可用列举法

形式语言与自动机理论-蒋宗礼-第四章参考答案

1.写出表示下列语言的正则表达式。

（吴贤珺02282047）⑴{0, 1}*。

解：所求正则表达式为：(0+1)*。

⑵{0, 1}+。

解：所求正则表达式为：(0+1)+。

⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。

解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。

⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。

解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。

⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。

解：所求正则表达式为：(0+1)*10110(0+1)*。

⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。

⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。

解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。

另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。

形式语言与自动机理论-04

DFA的极小化
可区分：设DFA M=(Q,Σ,δ,q0,F)，如果 ∃x∈Σ*，使得Q中的两个状态q和p， δ(q,x)∈F和δ(p,x)∈F中有且仅有一个成立，则称q和p是可以区分的(distinguishable) ；否则称p和q等价，记作q≡p。
举例
判断哪些状态不可以合并：终止状态和非终止状态不可以合并。 q0, q1, q5和q2, q3, q4不可以合并。如果两个状态读入同一个字符所进入的状态不能合并，那么这两个状态不能合并。 δ(q0,1)=q2, δ(q5,1)=q5, q2和q5不能合并，所以q0和q5不能合并。 δ(q1,1)=q3, δ(q5,1)=q5, q3和q5不能合并，所以q1和q5不能合并。 δ(q2,0)=q4, δ(q3,0)=q4, δ(q2,1)=q5, δ(q3,1)=q5, 读入相同字母后进入的状态完全相同，所以q2和q3不能区分。 δ(q2,0)=q4, δ(q3,0)=q4, δ(q4,0)=q4, δ(q2,1)=q5, δ(q3,1)=q5, δ(q4,1)=q5,读入相同字母后进入的状态完全相同，所以q2,q3和q4不能区分。 δ(q0,0)=q1, δ(q1,0)=q0, δ(q0,1)=q2, δ(q1,1)=q3, 没有任何转移能够判定q0和q1,q0和q3是可区分的，所以q0和 q1不能区分。
正规语言泵引理的应用-2
证明{0n|n为素数}不是RL。
证明：设L={0n| n为素数}是RL，则L满足泵引理。不妨设N 是泵引理所指的正整数，取z=0N+p，N+p是素数，那么 z∈L。根据泵引理，必存在u,v,w，使得z=uvw，而且|uv|≤N, |v|≥1。不妨设v=0k,k≥1。此时，u=0j,w=0N+p-k-j, j≥0。根据泵引理，uviw=0j(0k)i0N+p-k-j=0N+p+k(i-1)∈L。取i=N+p+1，有0N+p+k(i-1)=0(N+p)(k+1)∈L 而实际上，k≥1，所以(N+p)(k+1)不是素数，所以 0(N+p)(k+1)∉L。因此，产生矛盾，故假设不成立，即{0n|n为素数}不是RL。

形式语言与自动机理论-蒋宗礼-第四章参考答案

1.写出表示下列语言的正则表达式。

（吴贤珺02282047）⑴{0, 1}*。

解：所求正则表达式为：(0+1)*。

⑵{0, 1}+。

解：所求正则表达式为：(0+1)+。

⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。

解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。

⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。

解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。

⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。

解：所求正则表达式为：(0+1)*10110(0+1)*。

⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。

⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。

解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。

另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。

蒋宗礼送形式语言与自动机理论-资料

2019/10/15
19
补集(Complementary Set)
A是论域U上的一个集合，A补集是由U中的、不在A中的所有元素组成的集合
AUA
U
U
9/10/15
20
补集(Complementary Set)
如果AB，则 B A
AAU
AA
B A A B U & A B
2019/10/15
8
1.1.2 集合之间的关系
•集合相等
– 如果集合A，B含有的元素完全相同，则称集合A与集合B相等(Equivalence)，记作A=B。
•对任意集合A、B、C： ⑴ A=B iff AB且BA。 ⑵ 如果AB，则|A|≤|B| ⑶ 如果AB，则|A|≤|B|。 ⑷ 如果A是有穷集，且AB，则|B|>|A|。
2019/10/15
12
交(Intersection)
• ⑷ A∩B=A iff A B • ⑸ Φ∩A=Φ • ⑹ |A∩B|≤min{|A|，|B|} • ⑺ A∩(B∪C)=(A∩B)∪(A∩C) • ⑻ A∪(B∩C)=(A∪B)∩(A∪C) • ⑼ A∩(A∪B)=A • ⑽ A∪(A∩B)=A
2019/10/15
30
1.2.3递归定义与归纳证明
• 归纳证明
– 与递归定义相对应
– 归纳证明方法包括三大步
• 基础(Basis)：证明最基本元素具有相应性质
• 归纳(Induction)：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。
• 根据归纳法原理，所有的元素具有相应的性质
形式语言与自动机理论

形式语言与自动机讲义(Part1)

语言是字母表上所有句子集合的子集语言是字母表上一些句子的集合语言就是从通过组合规则从∑*中选择一些合乎要求的句子形成的集合。
13
⑶ L3={0, 1, 00, 01, 10, 11, 000, …}=∑+ ⑷ L4={ε, 0, 1, 00, 01, 10, 11, 000, …}=∑* ⑸ L5={0n|n≥1} ⑹ L6={0n1n|n ≥ 1} ⑺ L7={1n|n ≥ 1} ⑻ L8={x|x∈∑+且x中0和1的个数相同}
∈(V∪T)*。
产生式又叫做定义式或者语法规则。第一个产生的左边一定是开始符号
31
α→β1|β2|…|βn 读作：α定义为β1,或者β2 ,…,或者βn 称β1,β2,…，βn为候选式(candidate)
例：S → i|SAS|(S)， A → +|-|*|/
5
文法的形式定义
G=(V，T，P，S)
文法的形式定义约定
⑴ 对一组有相同左部的产生式
P——产生式(production)的非空有穷集合产生式，形如α→β 读作：α定义为β
α→β1,α→β2, … ,α→βn
可以简单地记为：
α 称为左部，其中α∈(V∪T)+，且α中至少有V中
元素的一个出现。
β 称为右部，β
例
∑={0, 1} ∑0= {ε}
例
∑={0, 1} ∑+= {0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, …} ∑* = {ε, 0, 1, 00, 01, 11, 000, 001, 010, 011, 100, …}
∑1= ∑0∑ = {ε} {0, 1} = {0, 1} ∑2 = ∑1∑ = {00, 01, 10, 11} ∑3 = ∑2∑= {000, 001, 010, 011, 100, 101, 110, 111}

形式语言与自动机-经典教学课件(完整版)资料讲解

3. John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979
2020/6/20
5
第1章绪论
2020/6/20
8
1.1.2 集合之间的关系
⑸ 如果AB，则对x∈A，有x∈B。 ⑹ 如果 AB ，则对 x∈A ，有 x∈B 并且
x∈B，但xA。 ⑺ 如果AB且BC，则AC。 ⑻ 如果AB且BC，或者AB且BC，或者
AB且BC，则AC。 ⑼ 如果A=B，则|A|=|B|。
2020/6/20
⑵ (A× B)× C≠A× (B× C)。 ⑶ A× A≠A。
⑷ A× Φ=Φ。
2020/6/20
15
笛卡儿积(Cartesian product)
Ai
i1
A{a|AS,aA}
AS
2020/6/20
10
交(intersection)
• 集合A和B中都有的所有元素放在一起构成的集合为A与B的交，记作A∩B。
A∩B={a|a∈A且a∈B}
• “∩”为交运算符，A∩B读作A交B。
• 如果A∩B=Φ，则称A与B不相交。
• ⑴ A∩B= B∩A。 ⑵ (A∩B)∩C=A∩(B∩C)。 ⑶ A∩A=A。
• 1.1 集合的基础知识 • 1.1.1 集合及其表示
– 集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)。
– 元素：集合的成员为该集合的元素(element)。 – 集合描述形式。 – 基数。 – 集合的分类。

形式语言04章 Chomsky文法体系及语言之间的运算

定义4-1 右线性文法的定义
对于文法G=(∑，V，S，P)，若它的每个产生式都是下列形式之一：
A→xC或者A→y；
其中：A，C∈V，x∈∑*，y∈∑+；则文法G是右线性文法（也称为正则文法RG）。
如果一个语言L可以由右线性文法产生，则该语言是右线性语言。
定义4-2 上文无关文法的定义
对于一般的短语结构文法，G=(∑，V，S，P)：
G称为0型文法，或短语结构文法(PSG)。对应的 L(G)叫作0型语言或者短语结构语言(PSL)、递归可枚举集。
如果对于任意P，均有||≥||成立，则称G为1型文法，或上下文有关文法(CSG)。对应的L(G)叫作1型语言或者上下文有关语言(CSL)。
结论4-4 Chomsky的文法体系：对于文法G=（∑，V，S，P），根据对产生式
的不同限制，Chomsky将文法分为四类：文法G是3型文法，即右线性文法；文法G是2型文法，即上下文无关文法；文法G是1型文法，即上下文相关文法；文法G是0型文法，文法对产生式没有任何限制；
语言的分类是根据产生该语言的文法的分类进行的。若一个语言L由某个i型文法产生，则它是i型语言。i=0,1,2,3。即
证明：
先根据G构造满足条件的G’，然后证明两者等价。
取G’=(∑，V∪{S’},S’,P’)，其中 P’=P∪{S’|SP}，G’与G有相同的类型。
如果S不出现在P中任何产生式的右边，那么效果相当于仅仅用S’代换S，P’中产生式实际上与P中完全相同。
先证L(G’)L(G)。对xL(G’)，在G’中存在如下推导： S’x，那么在G中存在如下推导：
Chomsky将文法分为四类，关系为：
任意一个右线性文法本身是一个无关文法；本身不一定是相关文法；

形式语言与自动机

EXAMPLE1: Let G be the grammar S SAB A aAa B bB (a) Give a leftmost derivation of abbaab (b) Give two leftmost derivations of aa (c) Build the derivation tree for the derivations in part (b) (d) Give a ergular expression for L(G). EXAMPLE2:A right garmmar is a context-free grammar each of whose rules has one of the following forms: i)A ω ii) A ω B iii)A Where ω∈∑*.prove that a language L is generated by a rightlinear grammar if, and if, L is generated by a regular grammar.
1.2 基本概念
5.句子 sentence 是一个字母表，对于＊上的任何元素x，x叫做上的一个句子。 6. 句子的长度
x∈ ＊,句子x中字符出现的总个数,记为|x| ,长度为零的字符串.
1.2 基本概念
1.2 基本概念
1.3语言的有限描述
例4：L（G（S））={| {0,1}* 其中中至少包含一个1 且每个1都有0紧跟其后} S 1A（A为0打头，1符合题意） S 0S A 0B （B为 0任意，1符合题意） B 0B B 1A（ A为0打头，1符合题意）
例5：L＝｛aR{a,b}＊，其中R为的逆｝ S aaSa bSb Example 6:Construct a grammar over {a,b,c} whose language is {anb2ncm|n,m>0} Example 7: Construct a grammar over {a,b,c} whose language is {anbmc2n+m|n,m>0} S aScc aBcc B bBc bc Example 8: Construct a grammar over {a,b,c} whose language is {anbmci|0≤n+m≤i} S B A A aAc B B bBc C C Cc Example 9: Construct a grammar over {a,b} whose language is {anbm|0≤n≤m≤2n} S aSb aSbb

形式语言与自动机文法的一般理论

Article
2021/3/10
Article
南京航空航天大学计算机学院胡军
the apple runs 语法/语义
6
2.2 形式文法与形式语言
定义2. 1 一个文法G是一个四元组 G = ( V, T, P, S )，其中： V：是变元（Variable，Nonterminal）的有限集。 T：是终结符（Terminal）的有限集。 P：是产生式（Production）的有限集，其中每个产生式都是 α→β的形式，其中α∈(V∪T)+，且其中至少有一个V中的符号， β∈(V∪T)*。α称为产生式的左部，β称为产生式的右部。 S∈V，称为文法G的开始符号。(S很重要，决定这组规则最终要定义什么，考虑例2.3中的<Verb Phase>和<Sentence>)
文法的乔姆斯基分类
定义2.6
由短语结构文法产生的语言，称为短语结构语言，简记为PSL。
由上下文有关文法产生的语言，称为上下文有关语言，简记为CSL。
由上下文无关文法产生的语言，称为上下文无关语言，简记为CFL。
是句子的集合。
2021/3/10
南京航空航天大学计算机学院胡军
11
文法语言
例2.8 给出文法G,它有两个产生式： S→aSb S→ab
则该文法产生的语言Ｌ(G)={an bn∣n≥1 }。这是根据Ｌ(G)的定义，考虑从S的推导，若先用G中第二个产生
式，则S ab，就不能再往下推导了，此时相当于语言中ｎ＝1 的情况。若从S出发，先用第一个产生式ｎ-1次，即S aSb aaSbb … an-1S bn-1，最后再使用第二个产生式一次，得到S aｎbｎ，这个推导对于任何ｎ>1都是对的。再加上ｎ=1的情况，即可得到L(G)＝{an bn∣n≥1 }。

形式语言与自动机理论-蒋宗礼-第四章参考答案

1.写出表示下列语言的正则表达式。

（吴贤珺02282047）⑴{0, 1}*。

解：所求正则表达式为：(0+1)*。

⑵{0, 1}+。

解：所求正则表达式为：(0+1)+。

⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。

解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。

⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。

解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。

⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。

解：所求正则表达式为：(0+1)*10110(0+1)*。

⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。

⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。

解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。

另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。

对应chomsky四种文法的四种语言之间的关系

对应chomsky四种文法的四种语言之间的关系NoamChomsky是20世纪最重要的语言学家之一。

他提出了一套语言理论，其中包括了四种文法类型。

这些文法在语言学研究中起着重要作用，因为它们提供了一种方式来描述不同类型的语言结构。

在本文中，我们将探讨这四种文法类型以及它们之间的关系。

1. 正则文法正则文法也称为类型3文法，是最简单的文法类型。

它由一组规则组成，这些规则定义了一种语言的基本结构。

正则文法可以描述一些简单的语言结构，例如正则表达式和有限自动机。

正则文法的语言特征是具有线性结构，其中每个符号只能出现一次。

这种文法的规则只能是一些形如A -> aB或者A -> a的形式。

其中A和B是非终结符，a是终结符。

正则文法只能描述一些简单的语言，例如a^n b^n，其中n是任意正整数。

这种语言可以使用有限自动机来识别。

2. 上下文无关文法上下文无关文法也称为类型2文法，它比正则文法更强大。

这种文法的规则可以定义为A -> α，其中A是一个非终结符，α是一个符号串。

这意味着一个非终结符可以被替换为任何符号串，而不管它周围的上下文是什么。

上下文无关文法可以描述一些复杂的语言结构，例如二元表达式和HTML文档。

上下文无关文法的语言特征是具有树形结构，其中每个符号可以出现多次。

这种文法的规则只能是一些形如A -> α的形式。

其中A是非终结符，α是一个符号串。

上下文无关文法可以描述一些复杂的语言，例如a^n b^n c^n，其中n是任意正整数。

这种语言可以使用语法分析器来识别。

3. 上下文相关文法上下文相关文法也称为类型1文法，它比上下文无关文法更强大。

这种文法的规则可以定义为αAβ -> αγβ，其中A是一个非终结符，α和β是符号串，γ是一个符号串，它可以替换A。

上下文相关文法可以描述一些非常复杂的语言结构，例如自然语言。

上下文相关文法的语言特征是具有树形结构，其中每个符号可以出现多次。

形式语言与自动机课件——Chomsky范式和Greibach范式

(不允许!)
11
下推自动机的结构
扩充办法：引入一个下推栈
① 足够简单 ② 可解决许多有意义的问题，如识别有效的程序下推自动机PDA（Push Down Automaton）
由一条输入带,一个有限状态控制器和一个下推栈组成
PDA的动作
在有限状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作。有时，不需要考虑输入符号（空
College of Computer Science & Technology, BUPT 17
下推自动机的图形表示
q

a, Z/ω
p
表示（p，ω ）∈δ （q，a，Z）
上例的图形表示：
a, a/aa b, a/ε a, z0/az0 b, a/ε
q0 q1 q2
ε , z0/ε
注：栈空就不能再移动了
用格局表示aabb的识别过程: (q0 ，aabb，z0) ├（q1，abb，az0） ├（q1，bb，aaz0） ├（q2，b，az0） ├（q2，ε ，z0）
├（q0，ε ，ε ）终态接受＃
College of Computer Science & Technology, BUPT
18
确定的下推自动机（DPDA）
College of Computer Science & Technology, BUPT 14
下推自动机的格局
格局：用于描述PDA的瞬时工作状况
PDA格局 (q, ω, α) 其中 ω∈Γ*，α∈Γ* q — 当前状态 ω— 待输入串 (ω＝ε时，表示输入字符已读完) α— 下推栈中的内容 (α＝ε时表示栈已弹空) δ (q，a，Z ) ＝{ (p，r) }用格局可表示为 (q, aω ,Zα ) ├ (p, ω ,rα )

生成Chomsky文法

一、实验名称生成Chomsky文法二、实验原理1．0型文法（短语文法）如果对于某文法G，P中的每个规则具有下列形式：u:: = v其中u∈V＋，v∈V*，则称该文法G为0型文法或短语文法，简写为PSG。

0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L。

这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。

任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。

这种语言可由图灵机（Turning）来识别。

2．1型文法（上下文有关文法）如果对于某文法G，P中的每个规则具有下列形式：xUy:: = xuy其中U∈VN；u∈V＋；x，y∈V*，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。

1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。

1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。

3．2型文法（上下文无关文法）如果对于某文法G，P中的每个规则具有下列形式：U :: = u其中U∈VN；u∈V＋，则称该文法G为2型文法或上下文无关文法，简写为CFG。

按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。

2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。

一般定义程序设计语言的文法是上下文无关的。

如C语言便是如此。

因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。

4．3型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U :: = T 或 U :: = WT其中T∈VT ；U,W∈VN，则称该文法G为左线性文法。

如果对于某文法G，P中的每个规则具有下列形式：U :: = T 或 U :: = TW其中T∈VT ；U, W∈VN，则称该文法G为右线性文法。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4.2
Chomsky的文法体系另一种描述目前，国内普遍对Chomsky的文法体系存在另外一种描述方式，该方式限制了一般的空串产生式的使用。
对于短语结构文法G=(∑，V，S，P)： G称为0型文法，或短语结构文法
(PSG)。对应的L(G)叫作0型语言或者短语结构语言(PSL)、递归可枚举集。
语言L的迭代运算（或者闭包运算）
为L* {w|w=w1w2…wm， wi∈L，m≥0 } 即 L* =ULn 对n≥0
其中：
L10={ε} L11 =L1 L1n+1= L1L1n
对n≥1
注意: 语言L1={an|n>0}，L２={bn|n>0}，则
L1L２＝{anbm|n,m>0}； L1L２≠ {anbn|n>0}。
CFL ，RL），则
L∪{} 仍然是CSL （ CFL ，RL）。
定理4-14
如果L是CSL（
CFL ，RL），则
L-{} 仍然是CSL （ CFL ，RL）。
证明
即可。需要注意的是：S不允许出现在产生式的右边。
只需要增加或减少S
4.3 语言之间的运算及运算的封闭性(略)
实际上，G1是一个无关文法。也
是一个相关文法。即：任意一个无关文法都可以改造为等价的一个相关文法，所以，任意一个无关语言也是一个相关语言。
结论4-4 Chomsky的文法体系
对于文法G根据对产生式的不同限制，
Chomsky将文法分为四类：文法G是3型文法，即右线性文法；文法G是2型文法，即无关文法；文法G是1型文法，即相关文法；文法G是0型文法，文法对产生式没有特殊限制；
如果对于任意P，均具有
形式Aw, AwB, 其中，A,BV, w∑+，则称G为3型文法，也可称为正则文法(RG)或正规文法。对应的L(G)叫作 3型语言，也可称为正则语言或正规语言(RL)。
四类文法和对应的四类语言之间都有
包含关系。
定义：形如的产生式叫作空产生式，
语言的分类是根据产生该语言的文法的
分类进行的。若一个语言L由某个i型文法产生，则它是i型语言。i=0,1,2,3。
定义4-5 文法分类பைடு நூலகம்
用Ψi（语言类）的概念来定义所有的i
型语言；对于0≤i≤3 Ψ i ={L ∑*|L=L(G) ，G是i型文法}。
定理4-6
语言分类定理 Chomsky将语言分为四类，且有包含关系（真子集关系）： Ψ3СΨ2 Ψ1 Ψ0

语言的封闭性可以用于证明某些语言
属于某类语言，以及可以从简单的某类语言构造复杂的某类语言。
语言之间的运算的封闭性定义4-16 语言的对运算的封闭定义给定字母表∑，Ψ是∑上的一类语言，语言L1，L2СΨ，令α是语言上的二元运算：
4.3.2
(L1，L2)→α(L1，L2)；β是语言上的
一元运算：L1→β(L1)；若对于Ψ的任意语言L1和L2，α(L1，L2)也是Ψ 的语言，则称Ψ对于运算α是封闭的；若对于Ψ的任意语言L1，β(L1)也是Ψ 的语言，则称Ψ对于运算β是封闭的。
定理4-17 每个i（i=0，1，2，3）型语言对联
合，连接和迭代运算是封闭的。证明：

例如：文法G1为：S1→b，文法G2
为：S2→c，bS2→bb；则L(G1)={b}， L(G2)={c}；L1L2={bc}；而对于， S=>S1S2=>bS2=>bc；或 S=>S1S2=>bS2=>bb；即文法G5产生的语言为{bc,bb}，它不是语言L1和 L2的连接。
该问题产生的原因是S1和S2产生的
4.1.1
定义4-1 右线性文法
对于文法G=(∑，V，S，P)，若它的每
个产生式都是下列形式之一： A→xB或者A→y；其中：A，B∈V，x∈∑*，y∈∑+；则文法G是右线性文法（也称为正则文法RG）。
如果一个语言L可以由右线性文法产
生，则该语言是右线性语言。
定义4-2 上下文无关文法
定义4-11
设文法G=(∑，V，S，P)
，如果S不出现在任何产生式的右部(即S的仅仅负责推导的开始),则
如果G是CSG（CFG，RG），则
G=(∑，V，S，P∪{S}) 仍然是CSG（CFG，RG）；G产生的语言仍然为CSL（CFL，RL）。
定理4-13
如果L是CSL（
现在任何产生式的右边；则称文法G为上下文相关文法CSG（简称相关文法）。
如果一个语言能由一个相关文法产生，
则称这个语言是上下文相关语言（简称相关语言）。
根据以上的两个定义，可以得到
一个无关的文法不一定是相关的文法，
主要是空串产生式的情况。
某些文法不满足上述3类文法的要求； S→AB1 AB→0
根据空串定理：

G是一个上下文无关文法，存在一般的空串产生式A→ε，则存在另一个上下文无关文法G1 使得： ⑴L(G)=L(G1)； ⑵若εL(G)，则G1中没有任何空串产生式； ⑶若ε∈L(G)，则G′中有一个空串产生式S’→ε，且S’不出现在G1的其它任何产生式的右边；（S’是G1的开始符号）
串发生了串道，即S1产生的串可能将 S2产生的串作为下文，S2产生的串可能将S1产生的串作为上文； { S→S1S2 } U P1′ U P2″U {x′→x|x∈∑}U{x″→x |x∈∑} 则 L(G6)=L(G1)L(G2)；所以0型和1 型语言对连接封闭。
为解决这个问题，将∑复制为∑′和
也可叫作产生式。根据文法分类的定义，在RG, CFG, CSG中，都不能含有空产生式，所以任何RL,CFL,CSL中都不包含空语句。
空语句在一个语言中的存在并不影
响该语言有穷描述的存在，因为除了为生成空语句外，空产生式可以不被用于语言中其他任何句子的推导中。如果允许RG,CFG,CSG中含有空产生式，也就允许CSL,CFL,RL中包含空语句。
该文法不是右线性文法，不是无关文法，
也不是相关文法，只能属于短语结构文法。
Chomsky将文法分为四类，关系为：任意一个右线性文法本身是一个无关文
法；本身不一定是相关文法；任意一个无关文法本身不一定是相关文法；
设文法G=(∑，V，S，P)，则判断G是哪
类文法的方法如下： 1、G是短语结构文法； 2、如果所有产生式都有左边部分的长度小于等于右边部分长度，那么G是上下文有关文法；允许有S→ε，且S不出现在任何产生式的右边
对于文法G，如果对于G中的任意产
生式ν→ω，而ν只是一个非终结符，即 A→ω，A∈V，ω∈（∑ U V）*，则称文法G为上下文无关文法CFG（简称无关文法）。
如果一个语言能由一个无关文法产生，
则称这个语言是上下文无关语言（简称无关语言）。
定义4-3 上下文相关文法
对于文法G，如果G的每个产生式形如 u→v，且0<|u|≤|v|；但若ε∈L(G)，则允许有S→ε，且S不出
已知同一字母表∑
上的语言L1和L2，产生L1的文法G1=（∑，V1，S1， P1），产生L2的文法G2=（∑，V2， S2，P2），假定V1∩V2=Ф，S！ ∈V1，S！∈V2，设置 V=V1UV2U{S}。
对于联合运算
构造G3=（∑，V，S，P3），其中
P3={ S→S1} U{ S→S2}U P1 U P2，对于i=0，1，2，若G1和G2是i型文法，则G3也是；从S开始，使用 S→S1，得到L(G1)，或者使用S→S2，得到L(G2)，显然， L(G3)=L(G1)UL(G2)，所以，对于i=0， 1，2，Ψi对于联合封闭。
第四章 Chomsky文法体系及语言之间的运算
本章介绍
Chomsky的文法体系语言的运算和运算的封闭性(略) 正则集
4.1 Chomsky的文法体系文法的分类及文法之间的关系短语结构文法PSG=(∑,V，S，P)，产生式的形式是v→w，其中：v∈(∑UV)+，且至少包含一个非终结符； w∈（∑ U V）* 。
如果G1和G2是右线性文法，则G3不
是，构造文法G4=（∑，V，S，P4），其中P4为： {S→w1|S1→w1在P1中}U {S→w2|S2→w2在P2中}U P1U P2；则G4是右线性文法，且 L(G4)=L(G1)UL(G2)。
对于连接运算：构造G5=（∑，V，S，P5），其中
关语言；一个上下文无关语言是不是一个上下文相关语言呢？
从第二章可知：一个无关文法 ①没有任何空串产生式，或者 ②仅有一个空串产生式S→ε，且S不
出现在任何产生式的右边则该文法本身就是一个相关文法；它产生的无关语言也就是一个相关语言；
那么，如果一个无关文法中有一
般的空串产生式（如A→ε，A是一个非终结符，且不是开始符号），它产生的无关语言是不是相关语言呢？
封闭性：如果任意的、属于某一语言
类的语言在某一特定运算下所得到的结果仍然是该类语言，则称该语言类对此运算具有封闭性(closure property)。
有效封闭性：给定一个语言类的若干个语言的描述。如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的，并称此语言类对相应的运算具有有效封闭性(valid closure property)。
如果对于任意P，均有|| ≦||成
立，则称G为1型文法，或上下文有关文法 (CSG)。对应的L(G)叫作1型语言或者上下文有关语言(CSL)。

形式语言与自动机04章 Chomsky文法体系及语言之间的运算-1

合集下载

形式语言与自动机-课程介绍 ppt

形式语言与自动机理论-蒋宗礼-第四章参考答案

形式语言与自动机课件——语言及文法

形式语言与自动机理论-蒋宗礼-第四章参考答案

形式语言与自动机理论-04

形式语言与自动机理论-蒋宗礼-第四章参考答案

蒋宗礼送形式语言与自动机理论-资料

形式语言与自动机讲义(Part1)

形式语言与自动机-经典教学课件(完整版)资料讲解

形式语言04章 Chomsky文法体系及语言之间的运算

形式语言与自动机

形式语言与自动机文法的一般理论

形式语言与自动机理论-蒋宗礼-第四章参考答案

对应chomsky四种文法的四种语言之间的关系

形式语言与自动机课件——Chomsky范式和Greibach范式

生成Chomsky文法

文档推荐

最新文档