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

形式语言与自动机复习大纲 第一章 可数集 Vs. 不可数集 – 自然数集、整数集、有理数集市可数的； – 实数集是不可数的 – 可数集的幂集是不可数的 语言的概念 --斯大林：广大人群所理解的字和组合这些字的方法。 --韦伯斯特：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。 --关键点：字、组成规则，理解（语义）规则 字母表（alphabet）和字母（letter） – 字母表是一个非空、有穷集合； – 字母表中的语言成为该字母表的一个字母，又叫符号（symbol）或者字符 （character） 字母表的乘积 – 字母表?1与?2的乘积:?1?2={ab | a??1且b??2} 字母表的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的真前缀（proper prefix）。z是x的后缀（suffix），如 果y ??，则称z是x的真后缀（proper suffix） 设有一个字母表，x,y,z,w,v??*,且有x=yz,w=yv,y是x和w的公共前缀，如果x和w的任何公共前缀都是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的字符串叫空句子，记作ε。 语言的乘积 设∑1，∑2是字母表，L1??1,L2??2，语言L1与L2的乘积是一个语言： 则L1L2={xy | 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 归纳定义（又称递归定义，用来定义一个集合）的三个组成部分： 基础：指出某些对象是该集合的元素，它们是该集合的最基本的元素 归纳：指出用集合的元素来构造集合的新元素的规则。其一般形式为：如果a，b，…，z是被指定集合的元素，则用某种运算或者组合方法对a，b，…，z进行处理后所得的结果也是集合中的元素。 极小性限定：指出一个对象是多定义的集合中的元素的充要条件是该对象可以通过有限次地使用基础和归纳条款中所给的规定构造出来。 归纳定义可用于给出无穷集合的有穷描述 第二章考点： 文法的形式定义 文法是一个四元组： G = (V, T, P, S)，其中， V：变量（variables）的非空有穷集。?A?V，A叫作一个语法变量（syntactic variable），简称为变量，也可叫作非终极符号（nonterminal）。 T：终极符（teminal）的非空有穷集。要求： ?a?T,a为终极符。 P：由产生式（production）构成的非空有穷集合。P的元素均具有形式???，读作?定义为?，其中???V?T??，且?中至少有V中的一个元素出现。???V?T?* 。?称为产生式???的左部，?称为产生式的???右部。 S：S?V，是文法G的开始符号（start symbol） 推导的相关概念（P51） 句子与句型 设文法G=(V,T,P,S)，则称L(G)?{?|??T*且S????}