理论计算机复习整理.docx

1.形式化2形式语言3数理逻辑：4理论计算机科学理论计算机科学是关于计算、算法、程序和计算机的数学理论。有许多分支，包括计算理论、.形式语言 理论、形式语义理论，等等。
2将以下NFA转化为等价的DFAo

据此画出状态转移图如下:
证明设M, N分别是接受A和B的两个DFA。
证毕正规语言的泵引理
定理2.1设£是正规语言，那么存在一个常数匕对L中任何长度不小于攵的串卬，存在x,yz,使得川二肛z 且\xy\<k,
1. \y\>hVz > 0. xy'z g L.
证明 设M是接受L的DFA,有k个状态。设卬=。［〃2・•・。〃 ££，其中吟k。那么M从开始状态处理 完W共经历n+1个状态，分别记为外,名,・・・,外。注意到n+lNk+1。因为M只有k个不同的状态，所 以在这n+1个状态中的前k+1个状态中一定有一个两个状态是相同的。令这两个状态为么其中 0<r<s<k-l.因此上述处理w的计算路径被这两个状态分割成三段，从左向右数，第1段是从qo开始到 q「结束，第2段从年开始到令结束，第3段从q,开始到小结束。我们把这三段路径上处理的串分别记为 x,yfzo从而易知x, y满足定理中的性质1和2。而对于任何立0,串盯弓在M中可以先经过第1 段计算路径处理完x,然后用连续i次第2段路径处理N最后用第3段路径处理z,最后停止在终止状 态如。因此，M接受X/Z,从而xy'z G L o □
注：泵引理中的常数攵称为泵常数。
例2.2令1=｛限9|1仑1｝。用泵引理证明L不是正规语言。
证明：用反证法。假设L是正规语言。那么L有一个泵常数匕 取w二aWt
根据泵引理，存在x,y,z使得w=xyz,其中|xy|Wk,卜巨1且xzeL.由|xy|gk可知y不含b,由|y|Nl可知y 至少含一个因此xz中的a的个数小于k且b的个数等于ko由此可得xz不在L中。矛盾。口
例2.3令L=｛ajbj | 访｝ o用泵引理证明L不是正规语言。
证明：假设L是正规语言。那么L有一个泵常数k。取VV=
根据泵引理，存在x,y,z使得w=xyz,其中|孙|〈人 W2 1且Vi 2 1.工/Z W L.易知y中至少含一个
a且不含b,所以xy,Z中a的个数为k!+(i・l)n,其中〃二|yl。
令左!+« —1)〃 =(左+ 1)!(1)
那么.k，k!、
i =+ 1.
n
由于/刍必，所以〃整除0,从而i是整数。对于这个整数i,等式(1)成立。从而xy'z中。的个数为(什1)!,
与其中b的个数相同。这说明孙‘Z不在L中。矛盾。口
例2.4令L={a«|n是素数}。用泵引理证明L不是正规语言。
证明：
练习2.5
令L = {卬卬| we{O,l}+} o用泵引理证明L不是正规语言。
1. Moore 机
在有限自动机的状态上添加输出动作，当自动机进入某个状态时，就输出该状态所对应的 字符。因此Moore机是在状态中输出的，当前的输出符号完全由当前的状态所确定。
定义1. 1 Moore机是一个六元组M = (。, £,△»源,%)
其中Q是有限状态集，q。是初始状态，2和△分别是输入和输出符号表，6是状态转移函 数，8是状态-输出函数，它们分别为如下映射
例1.2构造一个Moore机，对于输入的任何二进制自然数x,输出xmod(3)。
分析：我们为Moore机设置3个状态，分别表示模3运算的3个结果，即0, 1和2.
我们让Moore机从左向右扫描二进制输入串，假设当前扫描过的输入串模3的结果为i,那么 进入状态i,并输出i。当扫描完整个输入串时，最后到达的状态将输出所需要的计算结 果。
构造：令Q二{0,1,2}, 2二{0,1}, △ = {0,1,2),状态转移函数和状态-输出函数如以下图所 示
分：010, 1—1, 212
2. Mealy 机
在有限自动机的每个状态转移上添加输出动作，当自动机进行某个状态转移时，输出该转 移所对应的字符，这种带输出的有限自动机称为Mealy机。其形式定义请读者尝试写出来。
例2」以下Mealy机的功能是模拟二进制加法，处理的次序是从低位到高位。该自动机使 用两个状态，状态。进行不带进位的加法，状态1进行带进位的加法。由于Mealy机仅有 一条输入带，所以这两个加项需要编码为一条输入串。这里采用的编码方法是，从两个加 数的低位开始，将对应数位上的两个数字编码为一个符号，即(0,0),(0,1),(1,0)或者(1』)。 最后添加(0,0)结束。例如，我们将1和11编码为(1,1 )(0,1 )(0,0),那么以下Mealy机输出001, 反过来就是相加的结果100,即十进制的4o请读者尝试该Mealy机模拟1+2和2+5。
(0,0)/（0,1）,（1,0）Q°）/（0,1）,（1,0）/
定理2.2 Moore机与Mealy机是等价的。
证明方法：模拟法，即用两种自动机相互模拟对方的功能。
证明：1）设M是一个Moore机，构造一个Mealy机模拟M。
推迟输出：将状态的输出转移到该状态的出转移上。
2）设M是一个Mealy机，构造一个Moore机模拟M。
拆分状态：对于M的任何状态q和其入转移上的输出符号x,用［q, x］作为Moore机的状 态，负责输出x
□有限自动机的实现
一个简单的实现方法如下：
第1步确定该DFA的语义：
（1）确定其输入与输出方式；（2）确定程序中会用到的主要数据结构；
（3）确定各状态与转移下的读取、存储，输出、返回等分析动作；
第2步编写和调试程序：
（1）编写程序的主体局部，其中每个状态分别用一个语句标号表示，下一状态的选择用 条件控制语句实现，状态之间的转移用got。语句实现。
（2）添加头文件和变量声明语句。
有限自动机和正规表达式表示语言的能力是很有限的，只能表示正规语言。根据Myhill-Nerode定理, 正规语言的等价类是有限多的，而一些很简单的语言也会有无限多的等价类，例如｛0叮521｝。本讲将 介绍一种新的语言模型，称为上下文无关文法。它是美国语言学家乔姆斯基（Chomsky） 1956年提出的 一种语法形式，乔姆斯基称之为转换生成文法（transformational-generativegrammar）o.概念
语言是由语句构成的，语句是由字符构成的。在乔姆斯基的文法中，把构成语句的字符称为终极符 号，此外用假设干变元分别指代某一类型的短语，这些变元也称为非终极符号，其中指代句子的变元称为 文法的开始符。终极符号和变元合称文法符号，它们可以组成各种句型。上下无关文法用如下形式的表 达式定义变元所指代的短语类型：
A fa
其中A是非终极符号，a是文法符号串，描述了 A类短语的结构。这种表达式称为产生式。定义一个变 元可能需要多个产生式。假设变元A有如下两条产生式A fa At B
我们可以把它们合写为一条复合产生式A f
其中a和0分别称为该复合产生式的候选式(candidant)o下面我们给出上下文无关文法的形式定义。
定义1.1上下文无关文法(context-free grammar, CFG)是如下形式的四元组G=(Vn, Vt, P, S)
其中Vn和Vt是两个字符表，其中的字符分别称为非终极符号(non-terminal)和终极符号(terminal), S是Vn中一个特殊的非终极符号，称为开始符号(start symbol), P是产生式集合，其中的产生式 (production)是形如A-a的表达式，其中A是非终极符号，a是文法符号串或者空串。为了指明开始 符为S,我们将文法名字写成G[S]。
在下面的例子中，我们一般用大写字母表示非终极符，小写字母表示终极符，第1条产生式的左部变元 默认为开始符。因此，给出一个文法时，无需再指出这些符号，只需列出所有产生式即可。
1 .文法所生成的语言我们讨论如何根据给定的上下无关文法来确定它所定义的语言。我们可以把产生式的右部视为带变元的 正规表达式，其中有语言之间的连接、并和星闭包等3种正规运算。一个变元的复合产生式的右部定义 了该变元所指代的终极符号串集合。
定义2.1文法变元A所指代的语言记为L(A),终极符号a所指代的语言定义为L(a尸{a},空串所指代的 语言定义为L(g)={£},对于任何文法符号串a和团 定义更一般地，对于由多个文法符号串并联而成的串，其指代的语言定义为这些文法符号串所指代语言的并
集。对于文法变元A,假设A的所有产生式为人―。| |。/・・・|。〃，那么定义“A)="a)u〃％)U・・・U〃4)
定义2.2在文法G[S]中，开始符所指代的语言L(S)称为为文法G所生成的语言，另记为L(G),其中的 字符串称为该文法所生成的句子。
例2.3根据上述定义2.1和2.2中的规定，我们来尝试确定例1.4中文法Gi所生成的语言。根据该文法, 我们得如下方程组：
L ⑻=L(A)L(B)L(A) = L(nA)\JUn)="(A) U{〃}
L(B) = L(vB)UMv) = vL(B) U{v}由第2个方程可求得
£(A) = {nz|/>l}用归纳法不难证明上述结果是正确的。同理，由第3个方程可求得
£(B) = {vz|z>l}再由第1个方程立刻可得
L(S) = "|51}这就是Gi所生成的语言。
顺便说一下，如果我们把文法Gi中的终极符号n和v分别理解为名词和动词，那么根据A的产生式, A可理解为由名词组成的名词短语，根据B的产生式，B可理解为由动词组成的动词短语，从而根据S 的产生式可知S所指代的语句是由名词短语连接动词短语所组成的。
2 .推导
在乔姆斯基的文法理论中，把产生式用作推导规那么(derivation rule),可以开始符出发推出文法所生成 的任何句子。因此，我们把产生式A-a理解为A可推出a,或者A可重写为a,或者a可代入A,所 以产生式也称为重写规那么(rewrite rule)或者变元代入规那么(subsituation rule)。
定义2.1设G是上下文无关文法，假设存在产生式A-a,那么对于任何符号串u和v,有uAv=>uav
称为从串uAv到uav的一步推导(derivation)。对于任何文法符号串x和y,假设x=y或者x经过假设干步推 导可产生y,那么称x推导或者生成y,记为x=>*y。
例2.2在例1.4的文法Gi中，从A出发推导nnn,从B出发推导vvv,从S出发推导nnvv。
A=>nA=>nnA=>nnnB=>vB =>vvB =>vvv
S=>AB=>nAB=>nnB=>nnvB=>nnvv习惯上我们总是对于当前字符串中最左边的变元进行推导，这称为最左推导(left-most derivation)o今后, 在没有说明的情况下，所说的推导默认为最左推导。
上述推导过程需要重复写出已推出的字符，比拟麻烦，更简便的方式是用推导树记录推导过程。
定义2.3推导树：以变元为根和内结点，从一个变元推导出的字符从左到右分别是该结点的子结点，所 有树叶从左到右构成所推导的串。
例 4.2 A^0A|O Afi A|1该文法所生成的语言是(0|1)+,即所有非空的二元串。
练习4.3为以下正规语言设计上下文无关文法：
(1) 含偶数个0的二元串。
(2) 长度为偶数的二元串。
从上面的例子和练习，读者可以看到用递归产生式可以实现语言的星闭包运算。下面我们将看到， 用递归产生式还可以生成左右匹配的串，即语句内部的对称结构。例如以下语言中的语句都具有某种对 称结构：
L]={0T|〃21}
L2 = 1WWR I WG {0,1}+}这些语言分别由以下文法生成：
G :S f0Sl|01
G2:S^0S0|lSl|00|ll我们知道，这些语言都不是正规语言，不能用正规表达式或者有限自动机进行定义。因此，上下文无关 文法的语言描述能力是比拟强的，其秘密就在于递归产生式，可以生成左右匹配的字符串。
4.歧义文法从推导树看句子的短语结构：
(1)句子由短语组成，短语之间有两种关系：即结合关系和构成关系。结合关系是指假设干相邻短语之间 结合在一起构成上层短语；构成关系是指一个短语是另一个短语的成分。
(2)根据推导树可以看出所推出的句子的短语结构，即识别出该句子的所有短语及其之间的结合关系和 构成关系。因此，推导树也称为语法分析树(parsing tree)。
语法分析：在程序编译技术中，需要对源程序进行语法分析，其主要目的是构造源程序的语法分析树。 有一类方法是从根开始往下构造语法分析树，这种构造方法称为自上而下的语法分析，其实质是为源程 序构造最左推导。
定理5.1推导树与最左推导是一一对应的。
证明：用归纳法可证明，由最左推导只能构造出唯一的推导树，而由推导树也只能构造出唯一的最左推 导。因此，二者是一一对应的。
句子的语法结构是其语义的决定因素之一。不同的语法结构往往导致不同的语义。
定义5.2假设在某文法下一个字符串有两个不同的最左推导，那么该文法是歧义的(ambiguous )。
例5.3在以下文法G[E]中，i+i*i有两个不同的最左推导，所以是歧义文法。
E—E+E | E*E I (E) I i根据第1个推导树分析得的语法结构，i+i*i应解释为先做加法然后做乘法；而第2个推导树所确定的语 法结构那么说明，应先做后面的乘法再做前面的加法。因此，根据该文法无法确定一个正确的语义。
例5.4例5.3中的歧义文法可改写为如下非歧义性文法。
E - E+T|TT—T*F|F
F-(E)| i定理5.6上下文无关文法的歧义性是不可判定的。
定理5.7上下文无关语言的固有歧义性是不可判定的。

.正规表达式转化为带空转移的NFA
定义2.1我们用正规表达式标记有限自动机中的转移，表示该转移可以处理该正规表达式所表示的任何 输入串，这种有限自动机称为广义有限自动机，简称GFA。
GFA拆分法：将正规表达式转化为等价的lNFA。
.将有限自动机转化为正规表达式
GFA去状态法 第1步去掉陷阱状态。
第2步添加两端状态。在自动机转移图的两端添加一个新的开始状态X和一个新的接受状态Y,让X 空转移到原来的开始状态，并且让原来所有接受状态空转移到Yo 第3步合并转移。合并两个状态之间的所有方向相同的转移为一个转移，其标记为所有被合并的转移上 的标记的并。如以下图所示。
第4步挖去内部状态。去掉一个内部状态，将该状态的每个入转移与每个出转移分别连接为一个转移。 m个入转移与n个出转移相互连接后形成mn个新转移。设一对入转移和出转移上所标记的正规表达式 分别为w和v,那么连接后新转移上的标记如下定义：假设被去掉的状态上没有指向自己的转移，该标记为 WV；假设被去掉的状态上有一个标记为r的环，那么该标记为wr、。如以下图所示。
第5步 重复第3步和第4步，直到只剩下状态X到和Y以及二者间的一条转移，那么该转移上的正规表达 式就是所要求的结果。
3,将带空转移NFA转化为DFA的方法定义4.1(空转移闭包或£.闭包)对于带空转移的NFA来说，其某个状态q的空转移闭包，记为£-Oosure(q), 是由该状态自身，以及该NFA从此状态出发，经过假设干次空转移后，所能到达的所有状态构成的集合。
根据定义不难计算空转移闭包。我们可以在状态转移图上，跟踪空转移，标记出所有空转移所到达的状 态，然后将这些被标记的状态一一添加到所要求的闭包中即可。
状态子集闭包法
将s-NFA转化为等价DFA,按如下3步构造该DFA的转移矩阵。
第1步，算出e-NFA的开始状态的£-闭包，作为DFA的开始状态。
第2步，为每个DFA状态构造后继状态。令R为DFA的一个状态，a是一个输入符号。我们构造R的 a-转移后继状态S如下。
S = 6--Closured^ | 3p g R.q g 5(〃,〃)})即，假设H某状态p经过a转移可到达状态q,那么将q添加到S中，当没有状态可以添加时，再对S求空转 移闭包。此时所得的S就是R的a—转移后继状态。
第3步，将含NFA接受状态的DFA状态都指定为接受状态。
第6讲 米希尔-奈罗德定理与DFA最小化
一个正规语言的DFA是无穷多的，其中状态数最小的称为最小DFAo在实际应用中，作为一种算法, DFA当然是越小越好。本讲讨论如何将一个DFA等价变换为最小DFAo这个等价变换的理论基础是米 希尔-奈罗德定理。
3 .等价类：相互等价的所有元素构成的集合称为一个等价类。元素x所在的等价类记为［x］。
注意，［x］与［y］要么相等要么不相交。
n
4 .集合的划分:设｛4h ＜，＜是a的一组子集。假设4•互不相交且a=u a，那么称｛a ।Z=1
是A的一个划分(partition)。
命题1.设R是A上的一个等价关系，那么R的所有等价类构成A的一个划分。
命题2.设口是集合A的一个划分。定义A上二元关系An如下：
xRny当且仅当存在4 £ II, X, y £4那么心是等价关系。
推论3.一个集合上的等价关系与该集合的划分是一一对应的。
1 .字符串集合上的两个等价关系
我们先回顾一个定义，即有限自动机的状态所接受的语言。设M是一个有限自动机，“是其状态。 假设M从开始状态出发处理完串x后恰好到达状态外那么称q接受底夕接受的所有串构成q所接受的语言, 记为"q)°假设M是DFA,那么M可以确定地处理完任何串并且到达某个唯一状态，所以M的不同状态所接 受的语言是不相交的。因此，DFA各状态所接受的语言构成了输入串集合的划分。这个划分定义了一个等 价关系：假设两个输入串被DFA的同一个状态所接受，那么称这两个串在该有限自动机下是等价的。
x
定义1.2设/是一个DFA,其输入符号表为Z。我们在输入串集合Z*上定义二元关系Rm如下Rm=｛ (%被M的同一个状态所接受｝
显然Rm是2"上的等价关系，称之为M中的等价关系(equivalence in M)。
定义1.3设L是一个语言，其符号表为E。我们在Z*上定义二元关系&如下,R广｛(x, y)|(X/z)xz £ L = yz £ “
读者不难验证&是E*上的等价关系，我们称之为关于L的等价关系(equivalence toward L)o也许更文 艺点，可称之为“走向L的等价关系”。
我们可以这样来理解该等价关系。令x为一个串，那么任何串z作为后缀连接到x上只能导致两个结 果，即要么xz在L中要么xz不在L中。前者将x带到了 L中，后者将x带到了 L外。反过来，我们看
到所有串Z被X划分为两类，即｛zeE'IxzeL｝和｛Z£f IxzeL｝。前者可以视为X的正确向导 集，后者为x的错误向导集。因此，当且仅当两个串的正确向导集相同时才是关于L等价的。
引理1.4设L是正规语言，M是接受L的DFA,那么RM C & ,从而L的等价类数小于等于M的状态 数。
证明：设L的字母表为2,以下所讨论的串都是该字母表上的串。设(羽》)£氏加，那么对任何”2*,有
(xz. yz) e ,从而有xzeLo yzeL,即(x,y)£H「这证明对于任何串乂我们将
X在等价关系Rm和&下的等价类分别记为印M和印L.由于Rm7小，我们有=[划「因此，
的等价类个数大于等于&的等价类个数。又由于Rm的等价类就是"各状态所接受的语言，从而与这 些状态是一一对应的，所以Rm的等价类个数等于M的状态数。这证明引理的第二个结论成立。 □我们将用Rl的等价类作为状态构造一个接受L的最小DFAO
2 .米希尔•奈罗德定理
定理2.1 (Myhill-Nerode) 正规语言L的最小DFA的状态个数恰好等于Rl的等价类个数。
证明：1.构造最小DFA。根据上面的引理，&的等价类个数是有限的，我们用这些等价类作为有限自 动机的状态构造一个DFA如下：
其中状态集。=£*/&,即&等价类集合，2是L的符号表，开始状态S=⑻，Qf=｛[x]\xeL｝9即L内的串的 等价类都是接受状态，L外的串的等价类都是非接受状态，对于任何状态国和符号々£2 ,S([x].a) = [xa]9即自动机在状态区下扫描字符〃时就进入状态比旬。
2 .论证Ml的正确性。我们对输入串的长度用归纳法，将证明对于任何输入串龙£2* ,有x e L([x])
由于同是也 的开始状态，所以2£心([幻)。假设对于任何长度不超过某个数的串， 都有 xeL([x])o令。为任一输入符号。根据假设，也在处理完X后进入状态印。根据Ml的转移函数， Ml在状态印下处理字符。后进入状态[M],所以m被状态[刈]所接受。这样我们就证明了断言(2.1.1)。 由此不难推出如下结论：对于任何输入串x,都有L([x])=[x]
事实上，令y£[x],那么因=回，从而y££([对),所以[%]口，([%])。下面证明L([x])7[幻。令
Z G £([%]) o我们只需证明Z£[x]。根据(2.1.1),我们有Z£L([z])。因此，Z既被状态区所接受又 被状态国所接受。由于Ml是DFA,接受输入串的状态只能是唯一的，所以印二⑵。于是我们有Z£[x]。 这样我们就证明了乙([幻)=[同。由此可知，也接受的语言就是乙.论证Ml的最小性。根据上面的引理1.4,立刻可知Ml是最小DFA。□
推论2.2如果不考虑状态名称上差异，那么每个正规语言的最小DFA是唯一的。
证明：设M是正规语言L的最小DFAO M只要更改各状态的名称就完全变为定理2.1证明中所构造的 Ml。由于M是L的最小DFA,根据Myhill-Nerode定理，M的状态个数二&的等价类个数。因此，Rm的等价类个数二Rl的等价类个数。根据上面的引理， RmCl， 从而Rm =Rl.由此可知，对于任何输
入串x, M中都有相应地存在唯一状态q恰好接受x的等价类，即L(q)=[x]。因此，M中各状态与其所 接受的等价类之间是一一对应的。我们将接受区的状态改名为集合区。注意，由于不同状态所接受的等 价类是不相交的，所以这个改名是可行的，即不会导致两个不同状态使用同一个名称。令a是任何输入 符号，那么改名后的M在状态区下处理a后进入某个后继状态。由于该后继状态接受xa,所以该后继状 态所接受的等价类应当是[xa],从而该状态为[xa]。由此可以看出，改名后的M完全变成了定理2.1证明 中所构造的私。□3. DFA的最小化方法
首先，删除所有的无用状态，即从起始状态出发不能到达的状态。这样做并不改变原DFA的识别功能。
其次，对DFA的状态集合进行分割。
定义3.1设M是一个DFAoM的任何终止状态与非终止状态是可别离的。
1) M的两个状态p与q是可别离的，当且仅当存在串w分别从这两个状态出发可以到达终态与非终态。
引理3.2对于状态p和q,假设存在字符a,使得状态b(p,a)与3(q,a)是可别离的，那么p与q是可别离的。

U评氏可别离
~~>©引理3.3对于状态p和q,假设存在某个状态既与p不可别离又与q不可别离，那么p和q是不可别离的。
状态分割法：
第1步，将终止状态与非终止状态相别离，得初步划分(Q-Q「，Qf)
第2步，对当前划分中的每个子集做进一步的划分。方法如下：以当前所得的划分为标准，应用引理 3.2和3.3,确定当前子集中的所有可别离的状态对，据此划分该子集。重复第2步，直到没有可别离状 态对时为止。
注：根据引理3.2不难看出，状态分割法是正确的，即对于任何DFA,根据该方法所构造的DFA是等价 的并且是最小的。
例3.4给定NFA
图O 1

用状态子集法得DFA
现在我们需要最小化该DFA。
解：该DFA的状态集记为Q={0,1,2,3,4,5}首先将Q划分为拒绝状态集和接受状态集等两个局部。
口户{{0,1,2}, {3,4,5}}其次，对当前划分中的集合继续尝试划分。
口2={{01},{2}, {3,4,5}}
口3={{0},{1},{2}, {3,4,5}}根据口3, {3,4,5}中不存在可别离的状态对，所以“3就是最后所得的划分。
最后，画出所得最小DFA如下。

4.用Myhill-Nerode定理证明非正规语言
定理4.1 (Myhill-Nerode)语言L是正规的当且仅当&的等价类个数是有限的。
证明：假设L是正规语言，那么根据引理1.4, 及有有限个等价类。反之，假设&有有限个等价类，那么根据 Rl,可以按照Myhill-Nerode定理2.1证明中的方法构造出接受L的有限自动机区,所以L是正规语言。 □
例4. 1用Myhill-Nerode定理证明L二值叱5工1}不是正规语言。
关键：找出无限个等价类。
证明：设/nW孔。注意到aWEL且优任£。根据Rl的定义可知,an与心不等价。因此，侬］
和［a叫是两个不相同的等价类。从而L有无限多个等价类。根据Myhill-Nerode定理，L不是正规语 言。
练习4.2用Myhill-Nerode定理证明L={卬诚卬£(0|1)+}不是正规语言。
1. 正规语言类的封闭性
根据本讲义的定义易知，正规语言类在并、连接和星闭包等正规运算下都是封闭的。
定理假设A是正规语言，那么A，是正规语言。
注：A的补集是相对于A的字母表上所有串而言的。
证明设M是接受A的DFA。将M的接受状态改为非接受状态，将非接受状态改为接受状态，那么所得 的DFA接受A的补集。事实上，由于M是DFA,所以对于语言A的字母表上任何串来说，M都有某个 状态接受该输入串。因此，M的所有非接受状态所接受的串构成A的补集。 证毕
思考：假设M是接受语言A的NFA,那么将M的接受状态改为非接受状态，将非接受状态改为接受状态, 所得的NFA接受A补吗？
定义1.2 （乘积有限自动机）设M,N是两个具有相同输入符号表的DFA,那么M和N的乘积有限自动机 MN定义如下：
（1）假设M和N的开始状态为0和0,，那么MN的开始状态为（0,0）（2）假设（p,p'）是MN的状态，那么对于任何输入符号a, （p,p，）的a-转移后继状态为（q,q，）当且仅当p的a・转移 后继状态为q且p'的a-转移后继状态为
（3）对于MN的任何状态（p,p）该状态是MN的接受状态当且仅当p和p，分别是M和N的接受状态。
例L3令A为所有被2整除的二进制自然数，B为所有被3整除的二进制自然数。再令M, N是分别接 受A和B的DFA。试构造乘积有限自动机MN。
定理1.7假设A是正规语言，那么AR也是正规语言。
证明设M是接受A的DFA。由M构造接受AR的带空转移的NFA如下。
（1）逆转所有转移的方向；（2）添加一个新的开始状态，空转移到所有的接受状态；
（3）将M的开始状态指定为唯一的接受状，其中状态都是非接受状态。
不能证明这个NFA恰好接受ARO证毕
定理L8假设A, B是正规语言，那么A/3 = {z|存在使彳导X =尸}是正规语言。