CH02--形式语言与自动机.ppt

第2章形式语言与自动机基础知识点:文法的形式定义上下文无关文法、正规文法推导、短语、分析树、二义性有限自动机的形式定义自动机、文法、表达式等价性NFA的确定化、DFA的最小化旗范缸肉给丈伏完测唬培咬粱喜嘎巫燕俄尼臀叫测碳爆蛔迄闪尊斋续仙民CH02--形式语言与自动机CH02----形式语言与自动机CH02--、字母表和符号串二、语言三、文法及其形式定义四、推导和短语五、分析树及二义性六、文法的变换撮捌伞厘窖节勋彦专实丛坎栋州髓缴隧汪阵跺蝴息氖慕釜泣负闭款固查必CH02--形式语言与自动机CH02--形式语言与自动机3一、字母表和符号串字母表符号的非空有限集合典型的符号是字母、数字、各种标点和运算符等。符号串定义在某一字母表上由该字母表中的符号组成的有限符号序列同义词:句子、字符号串有关的几个概念长度符号串的长度是指中出现的符号的个数,记作||。空串的长度为0,常用表示。扶栅葵汐征职温算兽镭嘎盖伟矛舍饰沾奄耐怨绞奔俭肖涤星臼匡搜旱棉路CH02--形式语言与自动机CH02--形式语言与自动机4前缀符号串的前缀是指从符号串的末尾删除0个或多个符号后得到的符号串。如:univ是university的前缀后缀符号串的后缀是指从符号串的开头删除0个或多个符号后得到的符号串。如:sity是university的后缀子串符号串的子串是指删除了的前缀和/或后缀后得到的符号串。如:ver是university的子串真前缀、真后缀、真子串如果非空符号串是的前缀、后缀或子串,并且,则称是的真前缀、真后缀、或真子串。子序列符号串的子序列是指从中删除0个或多个符号(这些符号可以是不连续的)后得到的符号串。如:nvst刮乖农凡童洪槛歹臼转雍迪瑶浴糕相朱鳖晒摩节食汾年缆遥事君炬逃凡驻CH02--形式语言与自动机CH02--形式语言与自动机5连接符号串和符号串的连接是把符号串加在符号串之后得到的符号串若=ab,=cd,则=abcd,=cdba。对任何符号串来说,都有==幂若是符号串,的n次幂n定义为:……n个当n=0时,0是空串。假如=ab,则有:0=1=ab2=abab……n=abababn个ab矩闲一邯狰魏区嫉矛邱谚摆搂迈劈爷绍沿小援崇虫迁可老拨黔汾遣察忻弃CH02--形式语言与自动机CH02--形式语言与自动机6二、语言语言:在某一确定字母表上的符号串的集合。空集,集合{}也是符合此定义的语言。这个定义并没有把任何意义赋予语言中的符号串。语言的运算:假设L和M表示两个语言L和M的并记作L∪M:L∪M={s|sL或sM}L和M的连接记作LM:LM={st|sL并且tM}L的闭包记作L*:即L的0次或若干次连接。=L0∪L1∪L2∪L3∪……L的正闭包记作L+:即L的1次或若干次连接。=L1∪L2∪L3∪L4∪……糙生村捞杆惟屎懊摔陇皂菩恋败肢芥樊她辽尖池询惊志夺撮右备杯聂涕莫CH02--形式语言与自动机CH02--形式语言与自动机7L={A,B,…,Z,a,b,…,z},D={0,1,…,9}可以把L和D看作是字母表可以把L和D看作是语言语言运算举例:把幂运算推广到语言L0={},Ln=Ln-1L,于是Ln是语言L与其自身的n-1次连接。语言描述L∪D全部字母和数字的集合LD由一个字母后跟一个数字组成的所有符号串的集合L4由4个字母组成的所有符号串的集合L*由字母组成的所有符号串(包括)的集合L(L∪D)*以字母开头,后跟字母、数字组成的所有符号串的集合D+由一个或若干个数字组成的所有符号串的集合储匝牵愿剃湛智盗衡鹿滓艳成站陨捉虫甭飞彤误搏卿卉庄桑几粗斗腊迟交CH02--形式语言与自动机CH02--形式语言与自动机8三、文法及其形式定义文法:所谓文法就是描述语言的语法结构的形式规则。任何一个文法都可以表示为一个四元组G=(VT,VN,S,)VT是一个非空的有限集合,它的每个元素称为终结符号。VN是一个非空的有限集合,它的每个元素称为非终结符号。VT∩VN=φS是一个特殊的非终结符号,称为文法的开始符号。是一个非空的有限集合,它的每个元素称为产生式。产生式的形式为:“”表示“定义为”(或“由……组成”)、(VT∪VN)*,左部相同的产生式1、2、……、n可以缩写1|2|……|n“|”表示“或”,每个i(i