资源描述：
《形式语言与自动机课件——语言及文法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1CollegeofComputerScience&Technology,BUPT第二章语言及文法主要内容：定义形式语言的术语给出文法的定义和文法的分类要求掌握：语言和文法的形式定义CHOMSKY文法体系的分类。2CollegeofComputerScience&Technology,BUPT第一节语言的定义与运算一、语言的一些术语：字母表：字符的有限集合，记为T。字符串：由字母表T中的字符构成的序列称字母表T上的字符串（句子）。常记为u,v,w,x,y,z；常用a,b,c,d标识单个字符。3CollegeofComputerScience&Technology,BUPT字母表（Alphab
2、et）概念形式符号的集合记号常用T、表示举例英文字母表a,b,…,z,A,B,…,Z英文标点符号表,;:.?!’‘“”()…汉字表…,自,…,动,…,机,…化学元素表H,He,Li,…,T=a,n,y,任,意4CollegeofComputerScience&Technology,BUPT字符串（string）概念字母表T上的一个字符串（简称串），或称为字（word），为T中字符构成的一个有限序列。空串（emptystring）,用表示，不包含任何字符。举例设T=a,b，则,a,ba,bbaba等都是串字符串w的长度，记为w，是包含在w中字符的个数举例
3、=0，bbaba=5ai表示含有i个a的字符串5CollegeofComputerScience&Technology,BUPT连接（concatenation）设x,y为串,且xa1a2…am,yb1b2…bn,则x与y的连接xya1a2…amb1b2…bn连接运算的性质(xy)zx（yz）xxxxyx+y关于字符串的运算6CollegeofComputerScience&Technology,BUPT其它如取头字符，取尾部，子串匹配等设ω1,ω2,ω3是字母表T上的字符串，称ω1是字符串ω1ω2的前缀，ω2是字符串ω1ω2的后缀，且ω2是字符串ω1ω2ω
4、3的子串。空串是任何字符串的前缀，后缀及子串。例：abc的前缀aababcε.后缀cbcabcε.子串abcabbcabcε,即一个字符串可以看作是多个字符串的连接。关于字符串的运算7CollegeofComputerScience&Technology,BUPT字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1空串ε的逆还是ε8CollegeofComputerScience&Technology,BUPT字母表的幂运算幂运算设T为字母表，n为任意自然数，定义（1）T0=（2）设xTn-1，aT，则axTn（3）Tn中的元素只能由（1）和（2）
5、生成闭包T*=T0T1T2…闭包T+=T1T2T3…T*=T+，T+=T*9CollegeofComputerScience&Technology,BUPT闭包的物理意义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，…10CollegeofComputerScience&Technology,BUPT语言（
6、Languages）概念设T为字母表，则任何集合LT*是字母表T上的一个语言（language）举例英文单词集…,English,…,words,…C语言程序集…字母表？汉语成语集…,马到成功,…化学分子式集…,H2O,…,NaCl,…any,任意11CollegeofComputerScience&Technology,BUPT语言（Languages）举例：设T={a，b}则L1={anbn
7、n≥1}L3={bk
8、k是质数}L2={ε}只有一个空句子的语言L4={}=Φ空语言均为字母表T上的语言。由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，
9、交，补，差。12CollegeofComputerScience&Technology,BUPT语言的基本运算语言的积：两个语言L1和L2的积L1L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T={a,b}，L1和L2是T上的语言。L1={ab,ba}L2={aa,bb}则L1L2={abaa,abbb,baaa,babb}L2L1={aaab,
