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

第一章
可数集 . 不可数集
– 自然数集、整数集、有理数集市可数的；
– 实数集是不可数的
– 可数集的幂集是不可数的
语言的概念
斯大林：广大人群所理解的字和组合这些字的方法。
韦伯斯特：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。
关键点：字、组成规则，理解（语义）规则
字母表（）和字母（）
– 字母表是一个非空、有穷集合；
– 字母表中的语言成为该字母表的一个字母，又叫符号（）或者字符（）
字母表的乘积
– 字母表å1与å2的乘积:å1å2={ | aåÎ1且båÎ2}
字母表的n次幂
1) å0={e}. (e表示不包含任何字母的空字符串)
2) åå1å，n³1
字母表的闭包
– 字母表的正闭包：å åÈå2Èå3…
– 字母表的克林闭包： å*= å0Èåå0ÈåÈå2Èå3···
前缀和后缀
– 设å是一个字母表，x，y，zåÎ*，且，则称y是x的前缀（），如果¹，则称y是x的真前缀（ ）。z是x的后缀（），如果y e¹，则称z是x的真后缀（ ）
设有一个字母表，å*,且有是x和w的公共前缀，如果x和w的任何公共前缀都是y的前缀，则y是x和w的最大公共前缀。
句子的并置与幂
– x，y∈∑*，x，y的并置（）是这样一个字符串，该串由串x直接连接串y所组成，记作。并置也称为连接。(注：并置是定义在字符串上的一种运算)
– 对于n≥0，串x的n次幂定义为：
x0=ε；1x。
字串（）
设∑是一个字母表，w，x，y，z∈∑å，且，则称y是w的字串。
语言
"LÍå*，称L为字母表å上的一个语言（）
"xÎå*，x称为å上的一个句子。
不包含任何字符串的语言称作空语言，表示为￠
长度为0的字符串叫空句子，记作ε。
语言的乘积
设∑1，∑2是字母表，，语言L1与L2的乘积是一个语言：
则L1L2={ | xÎL1ÎL2}，该语言是字母表å1å2上的语言。
å*上的并置运算具有如下性质：对å*上的任意串,
结合律: ()()
左消去律: 若，则;
右消去律: 若，则；
唯一分解性: 存在唯一确定的a12, …åÎ使得12, …
单位元素: = = x
归纳定义（又称递归定义，用来定义一个集合）的三个组成部分：
基础：指出某些对象是该集合的元素，它们是该集合的最基本的元素
归纳：指出用集合的元素来构造集合的新元素的规则。其一般形式为：如果a，b，…，z是被指定集合的元素，则用某种运算或者组合方法对a，b，…，z进行处理后所得的结果也是集合中的元素。
极小性限定：指出一个对象是多定义的集合中的元素的充要条件是该对象可以通过有限次地使用基础和归纳条款中所给的规定构造出来。
归纳定义可用于给出无穷集合的有穷描述
第二章考点：

文法的形式定义
文法是一个四元组：
G = (V, T, P, S)，其中，
V：变量（）的非空有穷集。，A叫作一个语法变量（ ），简称为变量，也可叫作非终极符号（）。
T：终极符（）的非空有穷集。要求： 为终极符。
P：由产生式（）构成的非空有穷集合。P的元素均具有形式，读作定义为，其中，且中至少有V中的一个元素出现。 。称为产生式的左部，称为产生式的右部。
S：，是文法G的开始符号（ ）
推导的相关概念（P51）
句子与句型
设文法()，则称为文法G产生的语言（），，称为文法G产生的一个句子（）。
设文法()，对,若，则称是G产生的一个句型（ ）。

文法的推导；正则文法（与右线形文法的转换）；右线性文法。文法的构造（例子）。
文法的乔姆斯基体系。

第三章考点
有穷状态自动机( , ) 是一个五元组：
(Q,∑,δ0, F)
Q——状态的非空有穷集合。"q∈Q，q称为M的一个状态()。
∑——输入字母表( )。输入字符串都是∑上的字符串。
δ——状态转移函数( )，有时又叫做状态转换函数或者移动函数，δ×∑Q。对()∈Q×∑，δ()表示M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。
q0——q0∈Q，是M的开始状态( )，也可叫做初始状态或者启动状态。
F——，是M的终止状态( )集合。"q∈F，q称为M的终止状态，又称为接受状态( )。
对于x∈∑*，如果δ(q0 , x)∈F，则称 x 被 M 接受，如果δ(q0 , w)ÏF，则称 M 不接受 x。L(M)={ x | x∈∑*且δ(q0 )∈F }称为由 M 接受(识别)的语言。
如果 L(M1) = L(M2)，则称 M1 与 M2 等价。
状态转移图的相关知识
构造的相关知识，步骤
的基本定义：不确定的有穷状态自动机( , )M是一个五元组：
(Q ,∑ ,δ, q0 )
Q ,∑ , q0 , F 的意义同。
δ: Q×∑2Q，对"()∈Q×∑，δ()= {p1 2 ,…, }表示M在状态q读入字符a，可以选择地将状态变成p12 ,… , 或者 ，并将读头向右移动一个带方格而指向输入字符串的下一个字符。
根据构造的实用方法：为了避免不可达状态带来的无用计算，采用如下策略改进定理3-1的构造方法：
首先，只把状态[q0]填入表的状态列中，
如果表中的状态中有未处理的状态，则任选一个未处理的状态[q0, … , ]，对6中的每个符号a，计算6([q0, … , ], a)，并将结果填入相应的表项。
如果6([q0, … , ], a)在表的状态列中未出现过，则同时将它填入表的状态列。
如此重复下去，直到表的状态列中不存在未处理的状态。
与正则语言的相互转换方法（桥梁是右（左）线性文法）。

第四章考点：
正则表达式 ( ，)
设∑是一个字母表，
(1)Φ是∑上的正则表达式，它表示语言Φ；
(2)ε是∑上的正则表达式，它表示语言{ε}；
(3) 对于 7a∈∑，a 是∑上的正则表达式，它表示语言{a}；
(4)如果 r 和 s 分别是 ∑ 上表示语言 R 和 S 的 ，则：
r 与 s 的“和” ()是∑上的，()表达的语言为R∪S；
r 与 s 的“乘积” ()是∑上的，()表达的语言为；
r 的克林闭包(r*)是∑上的，(r*)表达的语言为R*。
(5)只有满足(1),(2),(3),(4)的表达式才是∑上的正则表达式。
正则表达式的定义；正则表达式等价的的构造方法；。

第六章考点
文法(V, T, P, S) 被称为是上下文无关的，如果除了形如Aε的产生式之外，对于∈P，均有|β|≥|α|，并且α∈V 成立。
设有 (V, T, P, S)，G 的派生树( )是满足如下条件的(有序)树( ) ：
(1) 树的每个顶点有一个标记 X，且 X∈V∪T∪{ε} 。
(2) 树根的标记为 S。
(3) 如果一个非叶子顶点 v 标记为 A，v 的儿子从左到右依次为 v1 , v2 , … , ，并且它们分别标记为 X1 , X2 , …, ，则1X2…∈P。
(4) 如果 X 是一个非叶子顶点的标记，则 X∈V。
(5) 如果顶点 v 标记为ε，则 v 是该树的叶子，并且 v 是其父顶点的唯一儿子。
上下文无关文法的派生树
别称生成树( ),分析树( ),语法树( )
顺序
v1 , v2 是派生树 T 的两个不同顶点，如果存在顶点 v，v 至少有两个儿子，使得 v1 是 v 的较左儿子的后代，v2 是 v 的较右儿子的后代，则称顶点 v1 在顶点 v2 的左边，顶点 v2 在顶点 v1 的右边。
结果()
派生树 T 的所有叶子顶点从左到右依次标记为 X1 , X2 , …, ，则称符号串 X1X2… 是 T 的结果。
一个文法可以有多棵派生树，它们可以有不同的结果。
称 “G的结果为α的派生树”为 G 的对应于句型α的派生树，简称句型α的派生树。

规范派生和规范规约；派生和派生树的关系；二义性文法与先天二义性语言；自底向上和自顶向下的分析方法。
第七章考点：
下推自动机 ( ，)
M = ( Q,∑,Γ,δ, q0 , Z0 , F )
Q——状态的非空有穷集合。9q∈Q，q 称为M 的一个状态()；
∑——输入字母表 ( )。要求 M 的输入字符串都是∑上的字符串；
Γ——栈符号表 ( )。9A∈Γ，叫做一个栈符号；
Z0——Z0∈Γ叫做开始符号( )，是 M 启动时候栈内惟一的一个符号。所以，习惯地称其为栈底符号；
q0——q0∈Q，是 M 的开始状态( )，也可叫做初始状态或者启动状态；
F——F9Q，是 M 的终止状态( ) 集合，简称为终态集。9q∈F，q 称为 M 的终止状态，也可称为接受状态 ( )，简称为终态。
即时描述 ( ，)
(q, w,γ)∈( Q, ∑*,Γ*) 称为 M 的一个即时描述。
它表示 M 处于状态 q，w 是当前还未处理的输入字符串，而且 M 正注视着 w 的首字符，栈中的符号串为γ，γ的最左符号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上面，较右的符号在栈的较下面。
如果 (p,γ)∈δ(q, a, Z)，a∈∑，且 M 在状态 q、栈顶为 Z、读入 a 时，选择进入状态 p，用γ替换栈顶 Z，记为
(q, , Zβ)├M (p, w,γβ)
表示 M 做一次非空移动，从 (q, , Zβ) 变成(,γβ)。
如果 (p,γ)∈δ(q,ε)，则记为
(q, w, Zβ)├M(p, w,γβ)
表示 M 做一次空移动，从(q, β)变成 (p, w,γβ) 。
├是├M 的 n 次幂：(q1 , w1 ,β1)├( , ,βn)
存在 序列，并满足
(q1 , w1 ,β1)├M(q2 , w2 ,β2) ├M …├M( , ,βn)
├M*是├M 的克林闭包：(q, w,α)├M*(p, x,β)
├是├M 的正闭包：(q, w,α)├(p, x,β)

第八章考点：

图灵机的基本定义、即时描述；图灵机接受的语言；可计算函数、递归可枚举语言、递归语言的概念。

课程教学大纲中规定的基本内容的覆盖程度（比例）为：≥80%
8、试卷题型：填空（20%10），判断（10%），简答（20%），分析与计算（50%2.10+2.15）