资源描述：
《形式语言与自动机复习大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机复习大纲第一章可数集Vs.不可数集–自然数集、整数集、有理数集市可数的；–实数集是不可数的–可数集的幂集是不可数的语言的概念--斯大林：广大人群所理解的字和组合这些字的方法。--韦伯斯特：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。--关键点：字、组成规则，理解（语义）规则字母表（alphabet）和字母（letter）–字母表是一个非空、有穷集合；–字母表中的语言成为该字母表的一个字母，又叫符号（symbol）或者字符（character）字母表的乘积–字母表?1与?2的乘积:?1?2={ab
2、a??1且b??2}字
3、母表的n次幂1)?0={?}.(?表示不包含任何字母的空字符串)2)?n=?n-1?，n?1字母表的闭包–字母表的正闭包：?+=???2??3…–字母表的克林闭包：?*=?0??+=?0????2??3···前缀和后缀–设?是一个字母表，x，y，z??*，且x=yz，则称y是x的前缀（prefix），如果z??，则称y是x的真前缀（properprefix）。z是x的后缀（suffix），如果y??，则称z是x的真后缀（propersuffix）设有一个字母表，x,y,z,w,v??*,且有x=yz,w=yv,y是x和w的公共前缀，如果x和w的任何公共
4、前缀都是y的前缀，则y是x和w的最大公共前缀。句子的并置与幂–x，y∈∑*，x，y的并置（concatenation）是这样一个字符串，该串由串x直接连接串y所组成，记作xy。并置也称为连接。(注：并置是定义在字符串上的一种运算)–对于n≥0，串x的n次幂定义为：x0=ε；xn=xn-1x。字串（substring）设∑是一个字母表，w，x，y，z∈∑?，且w=xyz，则称y是w的字串。语言?L??*，称L为字母表?上的一个语言（Language）?x??*，x称为?上的一个句子。不包含任何字符串的语言称作空语言，表示为￠长度为0的字符串叫空句子，记作
5、ε。语言的乘积设∑1，∑2是字母表，L1??1,L2??2，语言L1与L2的乘积是一个语言：则L1L2={xy
6、x?L1,y?L2}，该语言是字母表?1??2上的语言。**?*上的并置运算具有如下性质：对?*上的任意串x,y,z,结合律:(xy)z=x(yz)左消去律:若xy=xz，则y=z;右消去律:若yx=zx，则y=z；唯一分解性:存在唯一确定的a1,a2,…an??使得x=a1,a2,…an单位元素:?x=x?=x归纳定义（又称递归定义，用来定义一个集合）的三个组成部分：基础：指出某些对象是该集合的元素，它们是该集合的最基本的元素归纳：指出用集
7、合的元素来构造集合的新元素的规则。其一般形式为：如果a，b，…，z是被指定集合的元素，则用某种运算或者组合方法对a，b，…，z进行处理后所得的结果也是集合中的元素。极小性限定：指出一个对象是多定义的集合中的元素的充要条件是该对象可以通过有限次地使用基础和归纳条款中所给的规定构造出来。归纳定义可用于给出无穷集合的有穷描述第二章考点：文法的形式定义文法是一个四元组：G=(V,T,P,S)，其中，V：变量（variables）的非空有穷集。?A?V，A叫作一个语法变量（syntacticvariable），简称为变量，也可叫作非终极符号（nontermina
8、l）。T：终极符（teminal）的非空有穷集。要求：?a?T,a为终极符。P：由产生式（production）构成的非空有穷集合。P的元素均具有形式???，读作?定义为?，其中???V?T??，且?中至少有V中的一个元素出现。???V?T?*。?称为产生式???的左部，?称为产生式的???右部。S：S?V，是文法G的开始符号（startsymbol）推导的相关概念（P51）句子与句型设文法G=(V,T,P,S)，则称L(G)?{?
9、??T*且S????}为文法G产生的语言*G()（Language），???L，?称为文法G产生的一个句子（senten
10、ce）。（V?T）*,若S??，设文法G=(V,T,P,S)，对???则称?是G产生的一个句型（sententialform）。文法的推导；正则文法（与右线形文法的转换）；右线性文法。文法的构造（例子）。文法的乔姆斯基体系。第三章考点有穷状态自动机(finiteautomaton,FA)是一个五元组：M=(Q,∑,δ,q0,F)Q——状态的非空有穷集合。q∈Q，q称为M的一个状态(state)。∑——输入字母表(Inputalphabet)。输入字符串都是∑上的字符串。δ——状态转移函数(transitionfunction)，有时又叫做状态转换函数或
11、者移动函数，δ:Q×∑Q。对(q,a)∈Q×∑，δ(q,a)=p表示M在状态q读入字符a，将状
