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

第一章可数集 Vs. 不可数集 自然数集、整数集、有理数集市可数的； 实数集是不可数的 可数集的幂集是不可数的语言的概念-斯大林：广大人群所理解的字和组合这些字的方法。-韦伯斯特：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。-关键点：字、组成规则，理解（语义）规则字母表（alphabet）和字母（letter） 字母表是一个非空、有穷集合； 字母表中的语言成为该字母表的一个字母，又叫符号（symbol）或者字符（character）字母表的乘积 字母表1与2的乘积:12=ab | a1且b2字母表的n次幂1) 0=e. (e表示不包含任何字母的空字符串)2) n=n-1，n1字母表的闭包 字母表的正闭包：+= 23 字母表的克林闭包： *= 0+=023前缀和后缀 设是一个字母表，x，y，z*，且x=yz，则称y是x的前缀（prefix），如果ze，则称y是x的真前缀（proper prefix）。z是x的后缀（suffix），如果y e，则称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。并置也称为连接。(注：并置是定义在字符串上的一种运算) 对于n0，串x的n次幂定义为：x0=；xn=xn-1x。字串（substring） 设是一个字母表，w，x，y，z，且w=xyz，则称y是w的字串。语言L*，称L为字母表上的一个语言（Language）x*，x称为上的一个句子。不包含任何字符串的语言称作空语言，表示为长度为0的字符串叫空句子，记作。语言的乘积设1，2是字母表，语言L1与L2的乘积是一个语言：则L1L2=xy | xL1,yL2，该语言是字母表12上的语言。*上的并置运算具有如下性质：对*上的任意串x,y,z, 结合律: (xy)z=x(yz) 左消去律: 若xy=xz，则y=z; 右消去律: 若yx=zx，则y=z； 唯一分解性: 存在唯一确定的a1,a2, an使得x=a1,a2, an 单位元素: ex = xe = x 归纳定义（又称递归定义，用来定义一个集合）的三个组成部分：基础：指出某些对象是该集合的元素，它们是该集合的最基本的元素归纳：指出用集合的元素来构造集合的新元素的规则。其一般形式为：如果a，b，z是被指定集合的元素，则用某种运算或者组合方法对a，b，z进行处理后所得的结果也是集合中的元素。极小性限定：指出一个对象是多定义的集合中的元素的充要条件是该对象可以通过有限次地使用基础和归纳条款中所给的规定构造出来。归纳定义可用于给出无穷集合的有穷描述第二章考点：文法的形式定义文法是一个四元组： G = (V, T, P, S)，其中，V：变量（variables）的非空有穷集。AV，A叫作一个语法变量（syntactic variable），简称为变量，也可叫作非终极符号（nonterminal）。 T：终极符（teminal）的非空有穷集。要求： aT,a为终极符。 P：由产生式（production）构成的非空有穷集合。P的元素均具有形式，读作定义为，其中，且中至少有V中的一个元素出现。 。称为产生式的左部，称为产生式的右部。 S：SV，是文法G的开始符号（start symbol）推导的相关概念（P51）句子与句型 设文法G=(V,T,P,S)，则称为文法G产生的语言（Language），称为文法G产生的一个句子（sentence）。设文法G=(V,T,P,S)，对,若，则称是G产生的一个句型（sentential form）。文法的推导；正则文法（与右线形文法的转换）；右线性文法。文法的构造（例子）。文法的乔姆斯基体系。第三章考点有穷状态自动机(finite automaton, FA) 是一个五元组：M=(Q,q0, F)Q状态的非空有穷集合。qQ，q称为M的一个状态(state)。输入字母表(Input alphabet)。输入字符串都是上的字符串。 状态转移函数(transition function)，有时又叫做状态转换函数或者移动函数，:QQ。对(q,a)Q，(q,a)=p表示M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。q0q0Q，是M的开始状态(initial state)，也可叫做初始状态或者启动状态。FFQ，是M的终止状态(final state)集合。qF，q称为M的终止状态，又称为接受状态(accept state)。 对于x*，如果(q0 , x)F，则称 x 被 M 接受，如果(q0 , w)F，则称 M 不接受 x。L(M)= x | x*且(q0 ,x)F 称为由 M 接受(识别)的语言。如果 L(M1) = L(M2)，则称 M1 与 M2 等价。 状态转移图的相关知识DFA构造的相关知识，步骤NFA的基本定义：不确定的有穷状态自动机(non-deterministic finite automaton , NFA)M是一个五元组：M=(Q , , q0 ,F) Q , , q0 , F 的意义同DFA。: Q2Q，对(q,a)Q，(q,a)= p1 ,p2 , pm表示M在状态q读入字符a，可以选择地将状态变成p1,p2 , , 或者pm ，并将读头向右移动一个带方格而指向输入字符串的下一个字符。 根据NFA构造DFA的实用方法：为了避免不可达状态带来的无用计算，采用如下策略改进定理3-1的构造方法：首先，只把状态q0填入表的状态列中，如果表中的状态中有未处理的状态，则任选一个未处理的状态q0, , qn，对中的每个符号a，计算(q0, , qn, a)，并将结果填入相应的表项。如果(q0, , qn, a)在表的状态列中未出现过，则同时将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。FA与正则语言的相互转换方法（桥梁是右（左）线性文法）。第四章考点：正则表达式 (regular expression，RE)设是一个字母表，(1)是上的正则表达式，它表示语言；(2)是上的正则表达式，它表示语言；(3) 对于 a，a 是上的正则表达式，它表示语言a；(4)如果 r 和 s 分别是 上表示语言 R 和 S 的 RE，则： r 与 s 的“和” (r+s)是上的RE，(r+s)表达的语言为RS； r 与 s 的“乘积” (rs)是上的RE，(rs)表达的语言为RS； r 的克林闭包(r*)是上的RE，(r*)表达的语言为R*。(5)只有满足(1),(2),(3),(4)的表达式才是上的正则表达式。正则表达式的定义；正则表达式等价的FA的构造方法；。第六章考点文法G=(V, T, P, S) 被称为是上下文无关的，如果除了形如A的产生式之外，对于P，均有|，并且V 成立。设有 CFG G=(V, T, P, S)，G 的派生树(derivation tree)是满足如下条件的(有序)树(ordered tree) ：(1) 树的每个顶点有一个标记 X，且 XVT 。(2) 树根的标记为 S。 (3) 如果一个非叶子顶点 v 标记为 A，v 的儿子从左到右依次为 v1 , v2 , , vn，并且它们分别标记为 X1 , X2 , , Xn，则AX1X2XnP。(4) 如果 X 是一个非叶子顶点的标记，则 XV。(5) 如果顶点 v 标记为，则 v 是该树的叶子，并且 v 是其父顶点的唯一儿子。 上下文无关文法的派生树别称生成树(derivation tree),分析树(parse tree),语法树(syntax tree) 顺序v1 , v2 是派生树 T 的两个不同顶点，如果存在顶点 v，v 至少有两个儿子，使得 v1 是 v 的较左儿子的后代，v2 是 v 的较右儿子的后代，则称顶点 v1 在顶点 v2 的左边，顶点 v2 在顶点 v1 的右边。结果(yield) 派生树 T 的所有叶子顶点从左到右依次标记为 X1 , X2 , , Xn，则称符号串 X1X2Xn 是 T 的结果。 一个文法可以有多棵派生树，它们可以有不同的结果。称 “G的结果为的派生树”为 G 的对应于句型的派生树，简称句型的派生树。规范派生和规范规约；派生和派生树的关系；二义性文法与先天二义性语言；自底向上和自顶向下的分析方法。第七章考点：下推自动机 (pushdown automaton，PDA)M = ( Q, q0 , Z0 , F ) Q状态的非空有穷集合。qQ，q 称为M 的一个状态(state)；输入字母表 (input alphabet)。要求 M 的输入字符串都是上的字符串；栈符号表 (stack alphabet)。A，叫做一个栈符号；Z0Z0叫做开始符号(start symbol)，是 M 启动时候栈内惟一的一个符号。所以，习惯地称其为栈底符号；q0q0Q，是 M 的开始状态(initial state)，也可叫做初始状态或者启动状态；FFQ，是 M 的终止状态(final state) 集合，简称为终态集。qF，q 称为 M 的终止状态，也可称为接受状态 (accept state)，简称为终态。 即时描述 (instantaneous description，ID) (q, w,)( Q, *,*) 称为 M 的一个即时描述。它表示 M 处于状态 q，w 是当前还未处理的输入字符串，而且 M 正注视着 w 的首字符，栈中的符号串为，的最左符号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上面，较右的符号在栈的较下面。 如果 (p,)(q, a, Z)，a，且 M 在状态 q、栈顶为 Z、读入 a 时，选择进入状态 p，用替换栈顶 Z，记为(q, aw, Z)M (p, w,)表示 M 做一次非空移动，ID从 (q, aw, Z) 变成(p,w,)。如果 (p,)(q,Z)，则记为(q, w, Z)M(p, w,)表示 M 做一次空移动，ID从(q, aw,Z)变成 ID(p, w,) 。Mn是M 的 n 次幂：(q1 , w1 ,1)Mn(qn , wn ,n) 存在 ID 序列，并满