第2章-文法和语言的基本知识(3).ppt

第二章文法和语言的基本知识习题课本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结课堂练习1.给出语言L={1n0m1m0n|n,m≥0}的文法。练习**本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性,主要内容有：1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。(4)若语言是无穷集合,设计该语言的文法一定是递归的。 (3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。分析根据语言句子的结构特征，设计出相应规则例1.给出语言L2={anbm|m≥n≥1}的文法P2:S→ABL2={ab,abb,abbb,…aabb,aabbb,aabbbb,… aaabbb,aabbbb，…}A→aAb|abB→bB|ε分析根据语言句子的结构特征，设计出相应规则例2.给出语言L1={a2n+1|n≥0}的文法P1:A→aB|aP1：A→aAa|a或L1={a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，…}B→aa|aBa分析根据语言句子的结构特征，设计出相应规则例3.给出语言L3={anbmck|n,m,k≥0}的文法P3:A→aA|bB|cC|εP3:A→aA|B或L3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc,…,ab,abb,…,bc,bcc，…}C→cC|εB→bB|cC|εC→cC|εB→bB|CL4={0,2,4,6,8,10,12,14,16,18,20,22,24,26,…}例4.写一个文法,使其语言是正偶数的集合,每个偶数不以0开头。P4:N→E|AEN→0|2|4|6|8|BN或分析不以0开头的偶数集合中串的结构特征:A→D|AD′E→0|2|4|6|8D→1|2|3|…|9D→0|1|2|3|…|9B→1|2|3|…|9|B0P4:本章小结P:S→a|0S0|1S1 例5.给出语言L={WaWt|W∈{0|1}*,Wt表示W的逆的文法。 分析根据语言句子的结构特征，设计出相应规则L={a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,…}W={ε,0,1,01,10,00,11,101,110,100,111,…} 2.已知一个文法，确定该文法所定义的语言。(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。(1)文法所定义的语言L(G[S])={x|S?x且x∈VT*}*①自然语言描述。例如,L={x|x∈{a,b}+且x中a,b个数相同}②式子描述。例如L={a2nbb|n≥0}。③正规式描述。(3)语言可用例1文法G[A]=({A},{a,b},{A→bA|a},A)所生成的语言是什么？分析∵A?bA?bbA?bbbA?…?bnA?bna∴L(G[A])={bna|n≥0}本章小结例2文法G[N]为:N→ND|DD→0|1|2|3|4|5|6|7|8|9(1)G[N]所生成的语言是什么？(2)给出句子0127的