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

1、第一章可数集.不可数集-自然数集、整数集、有理数集市可数的；-实数集是不可数的-可数集的幂集是不可数的语言的概念斯大林：广大人群所理解的字和组合这些字的方法。韦伯斯特：为相当大的团体的人所懂得并使用的字和组合这 些字的方法的统一体。关键点：字、组成规则，理解（语义）规则 字母表（）和字母（）-字母表是一个 非空、有穷集合；-字母表中的语言成为该字母表的一个字母，又叫符号 （）或者字符（）字母表的乘积-字母表?1与?2的乘积:?1?2= | a ?1且b?2 字母表的n次幂1）?0=e. （e表示不包含任何字母的空字符串 ）12）?, n31字母表的闭包-字母表的正闭包：？ ？G?e?-字母表的

2、 克林闭包：?*= ?0 e ?G ?e2?前缀和后缀-设？是一个字母表，x, y, z?*，且，则称y是x的 前缀（），如果1，则称y是x的真前缀（）。z是x 的后缀（）,如果y el,则称z是x的真后缀（） 设有一个字母表，？*,且有是x和w的公共前缀，如果x和w的任何公共前缀都是 y的前缀，则y是x和w的最大公共前缀。 句子的并置与幂-x, y * , x, y的并置（）是这样一个字符串，该 串由串x直接连接串y所组成，记作。并置也称为连 接。（注：并置是定义在字符串上的一种运算 ）-对于n0,串x的n次幂定义为：0 1x = £； x。字串（）设刀是一个字母表，w, x, y

3、, zE ，且，则称y是w的字 串。"L ，称L为字母表？上的一个语言（）"x ?* , x称为？上的一个句子。不包含任何字符串的语言称作 空语言，表示为（Z长度为0的字符串叫空句子，记作£。语言的乘积设刀1,E 2是字母表，r，语言Li与L2的乘积是一个 则LiL2= | x ?Li?L2，该语言是字母表 ？1 ?2上的语言。?*上的并置运算具有如下性质：对?*上的任意串，结合律:()()左消去律:若，则；右消去律:若，贝V;唯一分解性:存在唯一确定的a12,?使得12,单位元素:=x归纳定义(又称递归定义，用来定义一个集合)的三个组成部分：基础：指出某些对象是

4、该集合的元素，它们是该集合的最基本的元素归纳：指出用集合的元素来构造集合的新元素的规则。其一般形式为：如果a, b,，z是被指定集合的元素，则用某种运 算或者组合方法对a, b,，z进行处理后所得的结果也是集合 中的元素。极小性限定：指出一个对象是多定义的集合中的元素的充要 条件是该对象可以通过有限次地使用基础和归纳条款中所给的 规定构造出来。归纳定义可用于给出无穷集合的有穷描述第一早考点：文法的形式定义文法是一个四元组:，其中，G = (V, T, P, S)V变量()的非空有穷集。，A叫作一个语法变量(),简称为变量，也可叫作非终极符号()。T:终极符()的非空有穷集。要求：为终极符。P:

5、由产生式()构成的非空有穷集合 。P的元素均具有形 式円，读作定义为，其中 I ，且中至少有V中的 一个兀素出现。X I 。回称为产生式上J的左部，凶称为产生式的I右部。S:，是文法G的开始符号()推导的相关概念(P51)句子与句型设文法()，则称 0为文法 G产生的语言()，, 称为文法G产生的一个句子()。设文法()，对,若亠，则称 是G产生的一个句型()。定文M设丈袪血(1) G 叫作 0 型文法(type 0 grammar), 短语结构文注(phrase structure grammartPSG).对应地AG网型语言或者短悟第构SgtPSDJ归可枚举集 (recursively e

6、numerable set,r+e.),如果对于加亠PE化沟有圍丨宀成立则称f；为1型文法(type 1grammar) i 或上下文有关文 ft (context sensitive grammar rCSG) 对应 JfcvL(G)IU| 作1 型语Ktype 1 language者上下文有关语言(context sensitive hnguage.CSD,«3)如果对于T S 均有网井且立则称心为：型文SCtype2 grammar) f或上下文无关文 £(context free grammar, CFG)a 对应地 叫作2 型语言(type 2 hnguagc)或

7、若上下文无关语言(context free languagerCFL)fl(4)如果对于 2阻Pm叩均具有形式A-w其中A1 B E VTu'6厂则称G为3型文法(type 3 grammar 1,也可称为正则文法<regular grammar, RG )或者正规丈嵐 对应地,L (G)叫作3型语育t type 3language) 丫也可称为正则语言或者正规语"S(regular hnguageTRL)fi文法的推导；正则文法(与右线形文法的转换) ；右线性文法。 文法的构造(例子)。文法的乔姆斯基体系。第二早考点有穷状态自动机(,) 是一个五元组：(Q,刀,8 0

8、, F)Q-状态的非空有穷集合。(I&Q, q称为M的一个状态()。 刀一一输入字母表()。输入字符串都是刀上的字符串。8状态转移函数()，有时又叫做状态转换函数或者移动函数，8X" Q 对() QXE,S ()表示 M在状态q读入字符a, 将状态变成p,并将读头向右移动一个带方格而指向输入字符串 的下一个字符。qo qo Q是M的开始状态()，也可叫做初始状态或者启动 状态。F，是M的终止状态()集合。qF, q称为M的终止状 态，又称为接受状态()。对于xGE*，如果5 (qO , x) F,则称x被M接受，如 果舀(q()，讦)',则称M不接受x。L(M)= x

9、 | x*且5 (qO ) F 称为由M接受(识别)的语言。如果L(M1) = L(M2)，则称 M1与M2等价。状态转移图的相关知识构造的相关知识，步骤的基本定义：不确定的有穷状态自动机(，)M是一个五元组：(Q ,刀,5 , qO )Q ,刀,qO , F的意义同。5 : Q XE 2q,对 ()EQXX,5 ()= p1 2 ,表示 M在状态q读入字符a,可以选择地将状态变成 p12 ,或者， 并将读头向右移动一个带方格而指向输入字符串的下一个字符。根据构造的实用方法：为了避免不可达状态带来的无用计算，采用如下策略改进定理3-1的构造方法：首先，只把状态qO填入表的状态列中，如果表中的状

10、态中有未处理的状态，则任选一个未处理的状态qO,，对6中的每个符号a,计算6(qO,a), 并将结果填入相应的表项。如果6(qO,a)在表的状态列中未出现过，则同时将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。与正则语言的相互转换方法（桥梁是右（左）线性文法）第四章考点：正则表达式（,）设刀是一个字母表，（1）是刀上的正则表达式，它表示语言；E是刀上的正则表达式，它表示语言 £ ；对于7a 刀，a是刀上的正则表达式，它表示语言a;如果r和s分别是刀上表示语言R和S的，则：r与s的“和”（）是刀上的，（）表达的语言为RU S;r与s的“乘积”（）是刀上的，（）表

11、达的语言为；r的克林闭包（r*）是刀上的，（r*）表达的语言为R*。 只有满足（1）,（2）,（3）,（4）的表达式才是刀上的正则表达式。正则表达式的定义；正则表达式等价的的构造方法；弟八早考点文法（V, T, P, S）被称为是上下文无关的，如果除了形如 A £ 的产生式之外，对于 H P,均有| B | > | a | ,并且a V成设有（V, T, P, S） , G的派生树（）是满足如下条件的（有序）树（）:(1)树的每个顶点有一个标记 X，且X VU TU £ 。树根的标记为S。(3)如果一个非叶子顶点 v标记为A, v的儿子从左到右依次 为v1 , v2

12、, ,，并且它们分别标记为 Xi , X 2，, 则P。 如果X是一个非叶子顶点的标记，则X V如果顶点v标记为£，则v是该树的叶子，并且v是其 父顶点的唯一儿子。上下文无关文法的派生树别称生成树()，分析树(),语法树()顺序v1 , v2是派生树T的两个不同顶点，如果存在顶点v ,v至 少有两个儿子，使得 v1是v的较左儿子的后代，v2是v的 较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在 顶点v1的右边。结果()派生树T的所有叶子顶点从左到右依次标记为X1 , X2 ,，贝V称符号串 X1X2是T的结果。一个文法可以有多棵派生树，它们可以有不同的结果。称“G的结果为a

13、的派生树”为G的对应于句型a的派生树， 简称句型a的派生树。规范派生和规范规约；派生和派生树的关系；二义性文法与先天 二义性语言；自底向上和自顶向下的分析方法。第七章考点：下推自动机（，）M = （ Q,刀,r , 5 , q0 , Z0 , F ）Q状态的非空有穷集合。9q Q q称为M的一个状态（）；刀一一输入字母表（）。要求M的输入字符串都是刀上的字符串；r栈符号表（）。9Ar，叫做一个栈符号；Z0Z0 叫做开始符号（），是M启动时候栈内惟一的一 个符号。所以，习惯地称其为栈底符号；q0qO Q是M的开始状态（），也可叫做初始状态或者启动状态；F F9Q是M的终止状态（）集合，简称为终态

14、集。9q F, q称为M的终止状态，也可称为接受状态（），简称为终态。即时描述（，）（q, w, 丫） （ Q,刀*, r *）称为 M的一个即时描述。它表示M处于状态q , w是当前还未处理的输入字符串，而且M正注视着w的首字符，栈中的符号串为y,Y的最左符号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上 面，较右的符号在栈的较下面。如果（p, Y ） 5 （q, a, Z）, aE，且M在状态q、栈顶为Z、 读入a时，选择进入状态p，用y替换栈顶Z ,记为(q, , Z B )卜M (p, w, yB)表示M做一次非空移动，从 (q, , Z B )变成(，yB )。如果(p, y )(q, £ )，则记为(q, w, Z B )卜M(p, w, yB)表示M做一次空移动，从(q, B )变成(p, w, yB )。卜是卜M的n次幂：(q1 , w1 , B 1)卜(,B n)存在序列，并满足(q1 , w1 , B 1)卜M(