形式语言与自动机复习大纲

第一章可数集Vs.不行数集-自然数集、整数集、有理数集市可数的；-实数集是不行数的-可数集的暴集是不行数的语言的概念―斯大林广阔人群所理解的字和组合这些字的方法—韦伯斯特为相当大的团体的人所懂得并运用的字和组合这些字的方法的统一体一关键点字、组成规则，理解语义规则字母表alphabet和字母letter-字母表是一个非空、有穷集合；-字母表中的语言成为该字母表的一个字母，又叫符号symbol或者字符character字母表的乘积-字母表五1与92的乘积:云黄2={ab|aafl且b12}字母表的n次幕1aO={e}.e表示不包含任何字母的空字符串o\°n°n-1°312a=a a,n1字母表的闭包-字母表的正闭包:a+=aEa2Ea3--字母表的克林闭包a*=a°Ea+=a°EaEa Ea3•••前缀和后缀图灵机的基本定义、即时描述；图灵机接受的语言；可计算函数、递归可枚举语言、递归语言的概念课程教学大纲中规定的基本内容的覆盖程度比例为280%

8、试卷题型填空20%10,推断10%,简答20%,分析与计算50%

2.10+

2.15-设是一个字母表，x,y,zal*,且x二yz,则称y是x的前缀prefix,假如ze1，则称y是x的真前缀proper prefixsuffix,假如y e1,贝J称z是x的真后缀propersuffix设有一个字母表，X,y,z,w,VG*,且有x=yz,w=yv,y是x和w的公共前缀,假如X和w的任何公共前缀都是y的前缀,则y是X和W的最大公共前缀句子的并置与第-x,y££*,x,y的并置concatenation是这样一个字符串，该串由串x干脆连接串y所组成，记作xy并置也称为连接注0并置是定义在字符串上的一种运算-对于n20,串x的n次幕定义为x0=£；xn=xllHXo字串substring设工是一个字母表，w,x,y,ze E,且w二xyz,则称y是w的字串语言〃廿*,称L为字母表范上的一个语言Languagex称为上的一个句子不包含任何字符串的语言称作空语言，表示为C长度为0的字符串叫空句子，记作e o语言的乘积设Ei,2是字母表，乙1雪，4口左，语言L与L2的乘积是一个语言则LL={xy|xIL„yIL},该语言是字母表U比上的语言2a*上的并置运算具有如下性质对台*上的随意串X,y,z,结合律xyz=xyz左消去律xy xz,则y二z;若二右消去律若yx=zx,则y二z；唯一分解性存在唯一确定的al,a2,…an算使得x二al,a2,…an单位元素ex=xe=x归纳定义又称递归定义，用来定义一个集合的三个组成部分基础指出某些对象是该集合的元素，它们是该集合的最基本的元素归纳指出用集合的元素来构造集合的新元素的规则其一般形式为:假如a,b,…，z是被指定集合的元素，则用某种运算或者组合方法对a,b,…，z进行处理后所得的结果也是集合中的元素微小性限定指出一个对象是多定义的集合中的元素的充要条件是该对象可以通过有限次地运用基础和归纳条款中所给的规定构造出来归纳定义可用于给出无穷集合的有穷描述其次章考点文法的形式定义文法是一个四元组G=V,T,P,S,其中,V变量variables的非空有穷集VA V,A叫作一个语法变量syntacticGvariable,简称为变量，也可叫作非终极符号nonterminal0T终极符teminal的非空有穷集要求WaeT,a为终极符P由产生式production构成的非空有穷集合P的元素均具有形ar/3,读作a定义为《，其中awVuT+,且a中至少有V中的一个元素出现式/V T*o a称为产生式af的左部，夕称为产生式的a f6右部G OSS V,是文法G的起先符号start symbolG推导的相关概念P51句子与句型设文法G=V,T,P,S,则称LG={|T*且S—To}为文法G产生的语言Q GWLanguage,V℃LG,

①称为文法G产生的一个句子sentence设文法G=V,T,P,S,对V VT*,若Sne,则称a是G产生的一个句型sententialOW Dform定义设文法GEV,T,P,S冽2-6⑴G明作型文法type0grammar,或短语结构文法phase structuregrammar,PSG,对应地，⑹叫作0型语言或者短语结构语鼠PSL、递归可枚举集recursively enumerableset,r.e.⑵如果对于Yaf PEP,均有|阴》I a；成立，则称G为1型文法type1grammar或上下文有关文法context sensitivegrammar,CSG对应地,L⑹叫作11型音type1language或者上下文有关语言0context sensitivelanguage,CSL.G23如果对于Va-pGP,均有网白⑷，并且«eV成立，则称为型文法type2grammar,或上下文无关文法context freegrammar,CFG对应地,LG叫作02型语言type2language或者上下文无关语言context Ireelanguage,CFL04如果对于Vo-PEP,所咱均具有形式A^wBG其中A.B WV,aW T,则称为3型文法type3grammar,也可称为正则文法regular grammar.RG或者正规文法对应地，L G叫作3型语言lype3language,也可称为正则语言或者正规语言regularlanguage,RL文法的推导；正则文法与右线形文法的转换；右线性文法文法的构造例子文法的乔姆斯基体系第三章考点有穷状态自动机finite automaton,FA是一个五元组M=Q,E,8,q,F0Q——状态的非空有穷集合q£Q,q称为M的一个状态state£——输入字母表Input alphabet输入字符串都是£上的字符串o6------状态转移函数transition function,有时又叫做状态转换函数或者移动函数，3:QX XQ对q,aQX£,3q,a二p表示M在状态q读入字符a,将状态变成p,并将读头向右移动一个带方格而指向输入字符串的下一个字符q——qoeQ,是M的起先状态initial state,也可叫做初始状态或者启动状0态F——FcQ,是M的终止状态final state集合q£F,q称为M的终止状态，又称为接受状态accept stateo对于x£X*,假如6qO,x EF,则称x被M接受，假如80,w F,则称qM不接受Xo LM={x|x££*且6qO,x WF}称为由M接受识别的语言假如LM1=LM2,则称Ml与M2等价状态转移图的相关学问DFA构造的相关学问，步骤NFA的基本定义不确定的有穷状态自动机non-deterministic finiteautomaton,NFA M是一个五元组M二Q,E,5,qO,FQ,£,qO,F的意义同DFAo8:QX E-2Q,对q,a£QX£,8q,a={pl,p2，…，pm}表示M在状态q读入字符a,可以选择地将状态变成pl,,p2,…，或者pm,并将读头向右移动一个带方格而指向输入字符串的下一个字符依据NFA构造DFA的好用方法:为了避开不行达状态带来的无用计算,采纳如下策略改进定理3-1的构造方法首先，只把状态[qO]填入表的状态列中，假如表中的状态中有未处理的状态，则任选一个未处理的状态[qO,…，qn],对中的每个符号a,计算[qO,…，qn],a,并将结果填入相应的表项假如g0,…，qn],a在表的状态列中未出现过，则同时将它填入表的状态列如此重复下去，直到表的状态列中不存在未处理的状态FA与正则语言的相互转换方法桥梁是右左线性文法第四章考点正贝！1表达式regular expression,RE设工是一个字母表，⑴

①是X上的正则表达式，它表示语言

①；22是X上的正则表达式，它表示语言{£};3对于a是X上的正则表达式，它表示语言{a}；4假如r和s分别是E上表示语言R和S的RE,贝心r与s的“和”r+s是X上的RE,r+s表达的语言为RUS；r与s的“乘积”rs是X上的RE,rs表达的语言为RS；r的克林闭包r*是£上的RE,r*表达的语言为R*⑸只有满意1,2,3,4的表达式才是£上的正则表达式正则表达式的定义；正则表达式等价的FA的构造方法；四相各自的含义第六章考点文法G=V,T,P,S被称为是上下文无关的，假如除了形如A-£的产生式之外，对于Va f均有|B|2|a I，并且a GV成立设有CFG G=V,T,P,S,G的派生树derivation tree是满意如下条件的有序树ordered tree1树的每个顶点有一个标记X,且XeVUTU{e}o2树根的标记为So3假如一个非叶子顶点v标记为A,v的儿子从左到右依次为vl,v2,…，vn,并且它们分别标记为X1,X,…，则A-X风…井4假如X是一个非叶子顶2点的标记，则XGVo5假如顶点v标记为£,则v是该树的叶子，并且v是其父顶点的唯一儿子上下文无关文法的派生树别称生成树derivation tree,分析树parse tree,语法树syntax tree依次vl,v2是派生树T的两个不同顶点，假如存在顶点V,V至少有两个儿子，使得vl是v的较左儿子的后代，v2是v的较右儿子的后代,则称顶点vl在顶点v2的左边，顶点v2在顶点vl的右边结果yield派生树T的全部叶子顶点从左到右依次标记为XI,X2,…，Xn,则称符号串X1X2-XI1是T的结果一个文法可以有多棵派生树，它们可以有不同的结果称“G的结果为a的派生树”为G的对应于句型a的派生树，简称句型a的派生树规范派生和规范规约；派生和派生树的关系；二义性文法与先天二义性语言；自底向上和自顶向下的分析方法第七章考点下推自动机pushdown automaton,PDAM=Q,E,T,8,qO,ZO,F Q——状态的非空有穷集合q£Q,q称为M的一个状态state；E——输入字母表input alphabet要求M的输入字符串都是X上的字符串；or-------栈符号表stack alphabetA£「，叫做一个栈符号；oZ0-----ZOG r叫做起先符号start symbol,是M启动时候栈内惟一的一个符号所以，习惯地称其为栈底符号；qO——qOGQ,是M的起先状态initial state,也可叫做初始状态或者启动状态;F——F Q,是M的终止状态final state集合，简称为终态集q£F,q称为M的终止状态，也可称为接受状态accept state,简称为终态即时描述instantaneous description,IDq,w,丫£Q,『*称为M的一个即时描述它表示M处于状态q,w是当前还未处理的输入字符串，而且M正凝视着w的首字符，栈中的符号串为Y，Y的最左符号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上面，较右的符号在栈的较下面假如P,丫£8q,a,Z,a£E,且M在状态q、栈顶为Z、读入a时，选择进入状态P，用Y替换栈顶Z,记为q,aw,ZB|-M p,w,y B表示M做一次非空移动，ID从q,aw,ZB变成p,w,Y B假如P,Y£3q,£,Z,贝!!记为q,w,ZB|-MP,w,丫B表示M做一次空移动，ID从q,aw,ZB变成IDp,w,丫B卜Mn是kM的n次幕ql,wl,31卜Mnqn,wn,B n存在ID序列，并满意ql,wl,31卜Mq2,w2,B2\~M…|-Mqn,wn,B n川*是|-M的克林闭包q,w,a卜M*p,x,B卜M+是|-M的正闭包q,w,a|-M+p,x,B第八章考点:。