资源描述：
《形式语言与自动机――语言及文法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章语言及文法主要内容：定义形式语言的术语给出文法的定义和文法的分类要求掌握：语言和文法的形式定义文法如何设计CHOMSKY文法体系的分类。引言复习：什么是形式语言？什么是文法？什么是自动机？形式语言的定义方式？研究形式语言与自动机的意义？问题的提出？本章关注语言与文法如何描述（产生）左右括号匹配的语言？如何描述（产生）数学表达式？引言知识点：形式语言所研究的问题：产生语言，根据语言中的基本句子和其它句子的形成“规则”，得到（产生）语言所包含的所有句子。第一节语言的定义与运算一、语言的一些术语：字母表：字符的有限集合，记为T。字符串：由字
2、母表T中的字符构成的序列称字母表T上的字符串（句子）。常记为u,v,w,x,y,z；常用a,b,c,d标识单个字符。字母表（Alphabet）概念形式符号的集合记号常用T、表示举例英文字母表a,b,…,z,A,B,…,Z英文标点符号表,;:.?!’‘“”()…汉字表…,自,…,动,…,机,…化学元素表H,He,Li,…,T=a,n,y,任,意字符串（string）概念字母表T上的一个字符串（简称串），或称为字（word），为T中字符构成的一个有限序列。空串（emptystring）,用表示，不包含任何字符。举例设T=
3、a,b，则,a,ba,bbaba等都是串字符串w的长度，记为w，是包含在w中字符的个数举例=0，bbaba=5ai表示含有i个a的字符串连接（concatenation）设x,y为串,且xa1a2…am,yb1b2…bn,则x与y的连接xya1a2…amb1b2…bn连接运算的性质(xy)zx（yz）xxxxyx+y关于字符串的运算其它如取头字符，取尾部，子串匹配等设ω1,ω2,ω3是字母表T上的字符串，称：ω1是字符串ω1ω2的前缀，ω2是字符串ω1ω2的后缀，ω2是字符串ω1ω2ω3的子
4、串。空串是任何字符串的前缀，后缀及子串。例：abc的前缀aababcε.后缀cbcabcε.子串abcabbcabcε,即一个字符串可以看作是多个字符串的连接。关于字符串的运算字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1空串ε的逆还是ε字母表的幂运算幂运算Tn用来表示该字母表长度为n的所有串的集合。设T为字母表，n为任意自然数，定义（1）T0=（2）设xTn-1，aT，则axTn（3）Tn中的元素只能由（1）和（2）生成闭包T*=T0T1T2…闭包T+=T1T2T3…T*=
5、T+，T+=T*闭包的物理意义T的星号闭包T*：字母表T上的所有字符串和空串的集合。T的正闭包T+：字母表T上的所有字符串构成的集合。T*=T+∪{ε}举例设T=0，1，则T0=，T1=0，1，T2=00，01，10，11，…T*=，0，1，00，01，10，11，…T+=0，1，00，01，10，11，…概念设T为字母表，则任何集合LT*是字母表T上的一个语言（language）。隐含的概念：如何表述子集的“特性和规则”，举例-左右括号的匹配。英文单词集…,English,…,words,…
6、C语言程序集…字母表？汉语成语集…,马到成功,…化学分子式集…,H2O,…,NaCl,…any,任意语言（Languages）语言（Languages）举例：设T={a，b}则L1={anbn
7、n≥1}L3={bk
8、k是质数}L2={ε}只有一个空句子的语言L4={}=Φ空语言均为字母表T上的语言。由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。语言的基本运算语言的积：两个语言L1和L2的积L1L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接
9、得到的集合。设T={a,b}，L1和L2是T上的语言。L1={ab,ba}L2={aa,bb}则L1L2={abaa,abbb,baaa,babb}L2L1={aaab,aaba,bbab,bbba}L1L2≠L2L1语言的积不可交换。语言的基本运算语言的幂：语言的幂可归纳定义如下:L0={ε}Ln=L·Ln-1=Ln-1·Ln≥1上例中，L12={abab,abba,baab,baba}L22={aaaa,aabb,bbaa,bbbb}语言举例例1：括号匹配的语言及产生该语言指所有左右括号相匹配的字符串如何“产生”这个语言？规则？递归定义
10、提供了集合的定义方式。构造规律。基础：定义该集合的最基本的元素，“（）”递归：若S是合法串，则：（S）是合法串；SS是合法串；语言举例例2：程序设计语言中算数表达式的语言运算符A
