有限自动机理论

有限自动机理论第一页，共一百七十三页，2022年，8月28日定义语言可以从两个方面进行：１）从产生语言的角度；２）从接收(或识别)语言的角度。第二页，共一百七十三页，2022年，8月28日形式语言研究内容产生一个语言:1)定义语言中的基本句子;2)根据其余句子的形成规则，产生出该语言所包含的所有句子。第三页，共一百七十三页，2022年，8月28日有限自动机研究内容

使用某种自动机模型来接收字符串接收的所有字符串形成的集合，也是一个语言第四页，共一百七十三页，2022年，8月28日统一的理论形式语言与自动机作为统一的理论,实际上包括3个方面的内容:1)形式语言理论(产生语言)2)自动机理论(接收语言)3)形式语言与自动机的等价性理论第五页，共一百七十三页，2022年，8月28日有限状态自动机FA

(FinitestateAutomaton)FA是为研究有限存储的计算过程正则语言而抽象出的一种计算模型。第六页，共一百七十三页，2022年，8月28日两类有限状态自动机接收器

判断是否接收输入串；转换器

对给定输入产生输出。第七页，共一百七十三页，2022年，8月28日FA还可以分成确定（DFA）与非确定（NFA）两种。第八页，共一百七十三页，2022年，8月28日等价性有限状态自动机识别的语言称为有限状态语言--FSL.从产生语言角度而言，FSL就是右线性语言--RLL从正则运算角度而言，FSL就是正则语言--RL。第九页，共一百七十三页，2022年，8月28日有限状态自动机除了它在理论上的价值外，还在数字电路设计、词法分析、文本编辑程序等领域得到广泛应用第十页，共一百七十三页，2022年，8月28日3.1有限状态自动机

有限状态自动机是具有离散输入和输出系统的一种数学模型。第十一页，共一百七十三页，2022年，8月28日有限状态自动机物理模型a1a2a3…aj…anan+1…FSC第十二页，共一百七十三页，2022年，8月28日一个输入存储带（输入带），带被分解为单元，每个单元存放一个输入符号(字母表上的符号)。整个输入串从带的左端点开始存放，而带的右端可以无限扩充；第十三页，共一百七十三页，2022年，8月28日一个有穷状态控制器（FSC）该控制器的状态只能是有限多个FSC通过一个读头读出当前带上单元的字符。第十四页，共一百七十三页，2022年，8月28日初始时，读头对应带的最左单元，每读出一个字符，读头向右自动移动一个单元。读头(暂时)不允许向左移动。第十五页，共一百七十三页，2022年，8月28日有限状态自动机的一个动作为：读头读出带上当前单元的字符FSC根据当前FSC的状态和读出的字符，进行状态改变；将读头向右移动一个单元。第十六页，共一百七十三页，2022年，8月28日有限态自动机的动作简化为：

FSC根据

当前状态和当前读取的带上字符进行状态改变。第十七页，共一百七十三页，2022年，8月28日定义3-1有限状态自动机FAFA是一个五元式FA=(Q，∑，δ，q0，F)

Q是有限状态的集合∑是字母表，也就是输入带上的字符的集合；第十八页，共一百七十三页，2022年，8月28日q0∈Q是开始状态；

FQ是接收状态(终止状态)集合；第十九页，共一百七十三页，2022年，8月28日δ是Q×∑→Q的状态转换函数，即δ(q，x)=q′代表自动机在状态q时，扫描字符x后到达状态q′第二十页，共一百七十三页，2022年，8月28日有限状态自动机的状态转换函数的个数应该为|Q|*|∑|对于Q中的每个状态，都应该定义对应∑的每个字母的状态转换。第二十一页，共一百七十三页，2022年，8月28日DFA这种有限状态自动机为确定的有限状态自动机DFA。第二十二页，共一百七十三页，2022年，8月28日例3-1DFA=({q0,q1},{0,1},δ,q0,{q0})其中δ：第二十三页，共一百七十三页，2022年，8月28日δ的表示：函数形式δ(q0，0)=q1δ(q0，1)=q1δ(q1，0)=q1δ(q1，1)=q0第二十四页，共一百七十三页，2022年，8月28日δ的表示：状态矩阵Q∑

0q01q1q1q1q1q0第二十五页，共一百七十三页，2022年，8月28日δ的表示:状态图形式状态图是一个有向、有循环的图一个节点表示一个状态；若有δ(q，x)=q′，则状态q到状态q′有一条有向边，并用字母x作标记。第二十六页，共一百七十三页，2022年，8月28日δ的表示

‘→’指向的状态是开始状态两个圆圈代表接收状态；第二十七页，共一百七十三页，2022年，8月28日δ的表示：状态图q11010q0第二十八页，共一百七十三页，2022年，8月28日用状态图表示一个DFA有向边的数目就是状态转换函数的个数。

第二十九页，共一百七十三页，2022年，8月28日3.2有限状态自动机识别语言对于DFA，给定串w=x1x2…xn；初始时，DFA处于开始状态q0从左到右逐个字符地扫描串w第三十页，共一百七十三页，2022年，8月28日在δ(q0，x1)=q1的作用下

DFA处于状态q1在δ(q1，x2)=q2的的作用下

DFA处于状态q2

…第三十一页，共一百七十三页，2022年，8月28日当将串w扫描结束后，若DFA处于某一个接收状态，则有限状态自动机能够接收串w第三十二页，共一百七十三页，2022年，8月28日对于可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，

到达某个接收状态。第三十三页，共一百七十三页，2022年，8月28日对于不可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，

处于非接收状态。第三十四页，共一百七十三页，2022年，8月28日对于字母表∑上的DFA能识别的所有串的集合，就是DFA能接收的语言:L(DFA)也称为有限状态语言（FSL）第三十五页，共一百七十三页，2022年，8月28日思考如何形式化定义L(DFA)?第三十六页，共一百七十三页，2022年，8月28日定义3-4扩展的状态转换函数给定DFA，扩展的状态转换函数δ*：Q×∑*→Q即δ*(q,w)=q′即DFA在一个状态q时，扫描串w后到达唯一确定的状态q′第三十七页，共一百七十三页，2022年，8月28日递归扩展的状态转换函数

δ*(q,ε)=q；δ*(q,a)=δ(q,a)其中a∈∑；第三十八页，共一百七十三页，2022年，8月28日对于串w=αa（α∈∑+）δ*（q，w）=δ*(q，αa）=δ(δ*(q,α),a)第三十九页，共一百七十三页，2022年，8月28日或者对于串w=aαδ*(q，w)=δ*(q，aα)=δ*(δ(q，a),α)第四十页，共一百七十三页，2022年，8月28日定义3-6DFA接收的语言DFA=(Q,∑,δ,q0，F)接收的语言L(DFA)={w|δ*(q0,w)∈F}第四十一页，共一百七十三页，2022年，8月28日思考如何描述在某个时刻，DFA所处的情况？第四十二页，共一百七十三页，2022年，8月28日定义3-7DFA的瞬时描述（格局）格局是一个二元式：qy

q是DFA当前状态y是输入带上还没有被扫描到的串读头将扫描y串的第1个符号第四十三页，共一百七十三页，2022年，8月28日在扫描串的过程中，格局在发生转换(改变)格局的(一次)转换的原因是由于δ函数的(一次)作用第四十四页，共一百七十三页，2022年，8月28日如果当前格局为：qar有δ函数：δ(q，a)=q′则下一格局为：q′r

；格局的转换可以记为：

qar=>q′r；第四十五页，共一百七十三页，2022年，8月28日DFA的特殊格局初始格局为：q0w接收格局为：

qfε其中，qf是某个接收状态第四十六页，共一百七十三页，2022年，8月28日使用=>*代表格局的任意次转换使用=>+代表格局的多次转换第四十七页，共一百七十三页，2022年，8月28日可以使用格局的转换方式定义FSL第四十八页，共一百七十三页，2022年，8月28日DFA接收的语言L(DFA)={w|q0w=>*qfε；w∈∑*且qf∈F}第四十九页，共一百七十三页，2022年，8月28日定义3-8DFA停机DFA将输入串扫描结束时

(自动)停机第五十页，共一百七十三页，2022年，8月28日注意1：DFA将输入串扫描结束停机时，如果DFA处于某一个接收状态，则表示接收整个输入串；反之，则表示不接收整个输入串;第五十一页，共一百七十三页，2022年，8月28日注意2：对于状态q,如果不能识别字母a

则将状态转换到一个特殊的状态：陷阱状态qt即δ(q，a)=qt第五十二页，共一百七十三页，2022年，8月28日

陷阱状态qt不能够改变为其他状态即对于a

∈∑

δ(qt

，a)=qt第五十三页，共一百七十三页，2022年，8月28日构造DFA，分别接收语言｛0，1｝*｛0，1｝+｛0｝∑={0}

{01}第五十四页，共一百七十三页，2022年，8月28日定理3-1每个FSL都是一个右线性语言分析：

已知接收FSL的DFA构造右线性文法产生该FSL第五十五页，共一百七十三页，2022年，8月28日证明思路状态转换函数和产生式的等价作用δ(q,,a)=q’

A→aB接收a

产生a

状态变化非终结符号变化结论:DFA状态等价于文法非终结符第五十六页，共一百七十三页，2022年，8月28日思考DFA的接收状态的作用第五十七页，共一百七十三页，2022年，8月28日证明假设L是字母表∑上的FSL，则L=L(DFA)第五十八页，共一百七十三页，2022年，8月28日DFA=（Q，∑，δ，q0，F）

构造右线性文法G=(∑,Q,q0，P）其中P为：第五十九页，共一百七十三页，2022年，8月28日{q→aq′|δ(q，a)=q′}U{q→a|δ(q，a)∈F}特别，若q0是接收状态，则

q0→ε第六十页，共一百七十三页，2022年，8月28日对于串w=x1x2…xn：DFA：则文法有δ(q0,,x1)=q1q0→x1q1；δ(q1,x2)=q2q1→x2q2；… …δ(qn-2,xn-1)=qn-1qn-2→xn-1qn-1δ(qn-1,xn)=qn

qn-1→xnqn

或qn-1→xn

第六十一页，共一百七十三页，2022年，8月28日所以DFA文法δ*(q，α)=q′q=>*αq′δ*(q0，w)∈Fq0=>*w第六十二页，共一百七十三页，2022年，8月28日例3-2DFA与文法的转换FSL={(0,1)1*0}*接收该语言的DFA为：第六十三页，共一百七十三页，2022年，8月28日q11001q0第六十四页，共一百七十三页，2022年，8月28日构造正则文法产生该语言：q0→0q1|1q1|εq1→0q0|1q1|0第六十五页，共一百七十三页，2022年，8月28日定理3-2FSL对补运算封闭第六十六页，共一百七十三页，2022年，8月28日证明：设L1是∑上的FSL,且L1=L(DFA1)，DFA1=（Q，∑，δ，q0，F）第六十七页，共一百七十三页，2022年，8月28日构造DFA2=（Q，∑，δ，q0，Q）DFA2接收的语言是L1的对应的全集,即∑*第六十八页，共一百七十三页，2022年，8月28日构造DFA3=(Q，∑，δ，q0，Q-F)DFA3接收的语言是L1的补L3=L(DFA3)也是FSL语言。第六十九页，共一百七十三页，2022年，8月28日注意此时的DFA1的δ函数的个数为

|Q|*|∑|第七十页，共一百七十三页，2022年，8月28日基本的等价替换对于状态转换图，有基本的等价替换变换为00,11第七十一页，共一百七十三页，2022年，8月28日3.3DFA识别语言的例子

构造DFA，接收语言L={ab}

第七十二页，共一百七十三页，2022年，8月28日基本结构（接收基本句子）q1abq0q2第七十三页，共一百七十三页，2022年，8月28日增加陷阱状态后的DFAq1abq0qtbaa,ba,bq2第七十四页，共一百七十三页，2022年，8月28日思考1如果将该DFA的所有状态都设置为接收状态(包括陷阱状态)，接收的语言是？

第七十五页，共一百七十三页，2022年，8月28日思考2

如果将该自动机的接收状态和非接收状态对调接收的语言是？第七十六页，共一百七十三页，2022年，8月28日例3-4构造DFA识别语言L={x000y|x,y∈{0,1}*}第七十七页，共一百七十三页，2022年，8月28日分析该语言的特点是语言中的每个串都包含连续的3个0（即每个串都包含子串000）第七十八页，共一百七十三页，2022年，8月28日因此，对于任何输入串，有限状态自动机的任务就是要检查该输入串中是否存在子串000，一旦发现输入串包含有000，则表示整个输入串是句子。第七十九页，共一百七十三页，2022年，8月28日因此，在确认输入串包含000后，就可以逐一地读入000后面的全部字符，并接收该输入串。第八十页，共一百七十三页，2022年，8月28日思考问题的关键是？如何发现子串000。第八十一页，共一百七十三页，2022年，8月28日由于字符是逐一读入的，当从输入串中读入一个0时，它有可能是000的第1个0，需要记住已经出现过一个0；第八十二页，共一百七十三页，2022年，8月28日如果紧接着读入的是字符1，则刚读入的0就不是000的第1个0需要重新寻找000子串的第1个0；第八十三页，共一百七十三页，2022年，8月28日如果紧接着读入的还是0，它有可能是000的第2个0，也需要记住这个0，继续读入字符，若是0，则发现000否则，需要重新寻找000。第八十四页，共一百七十三页，2022年，8月28日初始状态：q0接收0，到达状态q1接收00,到达状态q2接收000,到达状态q3第八十五页，共一百七十三页，2022年，8月28日因此，基本的状态转移函数为：

δ(q0，0)=q1δ(q1，0)=q2δ(q2，0)=q3用于接收基本句子000第八十六页，共一百七十三页，2022年，8月28日接收000的状态图q0000q1q2q3第八十七页，共一百七十三页，2022年，8月28日其他状态转移函数为：

δ(q0，1)=q0期待0的出现

δ(q1，1)=q0

重新寻找000

δ(q2，1)=q0

重新寻找000δ(q3，0)=q3扫描后续字符δ(q3，1)=q3扫描后续字符第八十八页，共一百七十三页，2022年，8月28日状态转移图q00111000,1q1q2q3第八十九页，共一百七十三页，2022年，8月28日思考如果需要接收语言

L∪

{ε}如何修改有限状态自动机?

思路：考虑开始状态的作用第九十页，共一百七十三页，2022年，8月28日思考:如果DFA的开始状态只负责识别输入串的第一个字母；文法的开始符号只负责串的推导的开始；优点是？第九十一页，共一百七十三页，2022年，8月28日状态图为10qs01000,1q1q2q3q011第九十二页，共一百七十三页，2022年，8月28日例3-5构造DFA

识别语言L={x001y|x，y∈{0，1}*}第九十三页，共一百七十三页，2022年，8月28日分析：对于任何输入串，DFA的任务就是要检查该输入串中是否存在001

第九十四页，共一百七十三页，2022年，8月28日初始状态：q0q1已接收0q2已接收00q3已接收001第九十五页，共一百七十三页，2022年，8月28日q2q1q0状态转移图01q31010,10第九十六页，共一百七十三页，2022年，8月28日例3-6构造DFA识别语言L={x000|x∈{0，1}*}

第九十七页，共一百七十三页，2022年，8月28日q2q3q1q001110001第九十八页，共一百七十三页，2022年，8月28日例3-7构造DFA识别语言L={x000}∪{x001}其中，x∈{0，1}*第九十九页，共一百七十三页，2022年，8月28日q2q1q001q310001q4101第一百页，共一百七十三页，2022年，8月28日例3-8构造DFA识别语言L={02k+3m|m,k>=0}

第一百零一页，共一百七十三页，2022年，8月28日实际上：2k+3m可以表示任意的非负整数(除1外)

该语言为0*-{0}

第一百零二页，共一百七十三页，2022年，8月28日状态转移图000q1q2q0第一百零三页，共一百七十三页，2022年，8月28日思考：构造DFA识别语言L={02k+3m|m,k>0}考查题1第一百零四页，共一百七十三页，2022年，8月28日例3-9构造DFA识别{0，1}上的语言，该语言的每个句子以0开头，以1结尾。

第一百零五页，共一百七十三页，2022年，8月28日状态转移图010q1q210qt0,11q0第一百零六页，共一百七十三页，2022年，8月28日例3-10构造DFA识别{0，1}上的语言，该语言的每个字符串不包含00子串(语言允许ε)第一百零七页，共一百七十三页，2022年，8月28日000,1qtq1q0q21011第一百零八页，共一百七十三页，2022年，8月28日或000,1qtq1q011第一百零九页，共一百七十三页，2022年，8月28日构造DFA识别{0，1}上的语言，该语言的每个字符串不包含00（语言不允许ε

）第一百一十页，共一百七十三页，2022年，8月28日例3-11构造DFA识别{0，1，2}上的语言，该语言的每个字符串代表的数字能整除3。第一百一十一页，共一百七十三页，2022年，8月28日分析如果一个十进制整数的所有位的数字的和能够整除3，那么，这个十进制整数就能够整除3；第一百一十二页，共一百七十三页，2022年，8月28日一个十进制整数除以3，余数只能是1、2和0；第一百一十三页，共一百七十三页，2022年，8月28日将整数当作一个字符串，从左到右逐一地读入；使用3个状态分别代表已读入的数字的和除以3的余数情况：(即读入的整数对3的余数情况）第一百一十四页，共一百七十三页，2022年，8月28日q0：已读入的整数除以3，余数为0q1：已读入的整数除以3，余数为1q2：已读入的整数除以3，余数为2第一百一十五页，共一百七十三页，2022年，8月28日思考已知qi(i=0,1,2)，n=0,1,2，应该如何确定j？

qiqjn第一百一十六页，共一百七十三页，2022年，8月28日扫描子串w后,处于某个状态qi，读入当前数字,状态转换情况为第一百一十七页，共一百七十三页，2022年，8月28日q0在此状态读入0，引导DFA到达下一状态的输入串为w0,w0的各位数字和除以3，余数为0。所以，DFA在q0状态读入0，应该继续保持q0状态；第一百一十八页，共一百七十三页，2022年，8月28日q0在此状态读入1，引导DFA到达下一状态的输入串为w1，w1的各位数字和除以3，余数为1。所以，DFA在q0状态读入1，应该到达q1状态；第一百一十九页，共一百七十三页，2022年，8月28日q0在此状态读入2，引导DFA到达下一状态的输入串为w2，w2的各位数字和除以3，余数为2。所以，DFA在q0状态读入2，应该到达q2状态；

…第一百二十页，共一百七十三页，2022年，8月28日第一百二十一页，共一百七十三页，2022年，8月28日存在的问题接收的串包括以0开始的数字串；还能够接收空串第一百二十二页，共一百七十三页，2022年，8月28日思考如何进行改进，使得接收的串不能以0开始，不能接收空串。第一百二十三页，共一百七十三页，2022年，8月28日定义3-9set集合对于状态q，能将DFA从q0转换到q状态的所有字符串的集合为：set(q)={w|w∈∑*,δ*(q0,w)=q}第一百二十四页，共一百七十三页，2022年，8月28日则有限状态自动机DFA接收的语言可以定义为：

L(DFA)=∪

set(qα)其中：qα∈F第一百二十五页，共一百七十三页，2022年，8月28日按状态进行划分对于DFA，可以定义关系R

若

x,y∈∑*，q∈Q则

xRy当且仅当

x∈set(q),y∈set(q)

第一百二十六页，共一百七十三页，2022年，8月28日该关系是集合∑*上的一个等价关系，利用该关系，可以将∑*划分为不多于|Q|个的等价类。第一百二十七页，共一百七十三页，2022年，8月28日DFA可以按照语言的特点给出字母表∑*的一个划分，这种划分相当于∑*上的一个等价分类。DFA每个状态对应着一个等价类第一百二十八页，共一百七十三页，2022年，8月28日利用一个状态去表示一个等价类是构造DFA的一条有效思路。第一百二十九页，共一百七十三页，2022年，8月28日例3-12构造DFA,识别{0,1,2,4,5,6,7,8,9}上的语言，该语言的每个字符串代表的数字能整除3。第一百三十页，共一百七十三页，2022年，8月28日仍然只使用3个状态分别代表已经读入的整数字的和除以3的不同的余数的情况：第一百三十一页，共一百七十三页，2022年，8月28日状态与对应的等价类q0：余数为0的输入串的等价类q1：余数为1的输入串的等价类q2：余数为2的输入串的等价类第一百三十二页，共一百七十三页，2022年，8月28日第一百三十三页，共一百七十三页，2022年，8月28日例3-13构造DFA,识别{0，1}上的语言，该语言的每个字符串挡成二进制数时，代表的数字能整除3。第一百三十四页，共一百七十三页，2022年，8月28日DFA的每个状态对应一个等价类利用一个状态去表示一个等价类除以3的余数只能为0、1和2第一百三十五页，共一百七十三页，2022年，8月28日q0：余数为0的输入串的等价类；q1：余数为1的输入串的等价类；q2：余数为2的输入串的等价类；第一百三十六页，共一百七十三页，2022年，8月28日不能接收空串，所以，还需要一个开始状态qS第一百三十七页，共一百七十三页，2022年，8月28日设w是当前读入的输入串；qS：在开始状态读入0时，w=0，进入状态q0；读入1时，w=1，进入状态q1；第一百三十八页，共一百七十三页，2022年，8月28日q0能引导DFA到达此状态的w除以3余数为0，因此(w)10=3n+0第一百三十九页，共一百七十三页，2022年，8月28日q0在此状态读入0，引导DFA到达下一状态的输入串为w0，则(w0)10=2(3n+0)+0=3×2n+0表明w0也属于q0对应的等价类。所以，DFA在q0状态读入0，应该继续保持q0状态；第一百四十页，共一百七十三页，2022年，8月28日q0在此状态读入1，引导DFA到达下一状态的输入串为w1，则(w1)10=2(3n+0)+1=3×2n+1表明w1属于q1对应的等价类。所以，DFA在q0状态读入1，应该到达q1状态；第一百四十一页，共一百七十三页，2022年，8月28日q1能引导DFA到达此状态的w除以3余数为1，因此

(w)10=3n+1第一百四十二页，共一百七十三页，2022年，8月28日q1在此状态读入0，引导DFA到达下一状态的输入串为w0，则(w0)10=2(3n+1)+0=3×2n+2

表明w0属于q2对应的等价类。所以，DFA在q1状态读入0，应该到达q2状态；第一百四十三页，共一百七十三页，2022年，8月28日q1在此状态读入1，引导DFA到达下一状态的输入串为w1，则(w1)10=2(3n+1)+1=3×2n+3表明w1属于q0对应的等价类。所以，DFA在q1状态读入1，应该到达q0状态；第一百四十四页，共一百七十三页，2022年，8月28日q2能引导DFA到达此状态的w除以3余数为2，因此，(w)10=3n+2第一百四十五页，共一百七十三页，2022年，8月28日q2在此状态读入0，引导DFA到达下一状态的输入串为w0，则(w0)10=2(3n+2)+0=3×2n+4表明w0属于q1对应的等价类。所以，DFA在q2状态读入0，应该到达q1状态；第一百四十六页，共一百七十三页，2022年，8月28日q2在此状态读入1，引导自动机到达下一状态的输入串为w1，则(w1)10=2(3n+2)+1=3×2n+5表明w1属于q2对应的等价类。所以，自动机在q2状态读入1，继续保持q2状态；第一百四十七页，共一百七十三页，2022年，8月28日状态图第一百四十八页，共一百七十三页，2022年，8月28日例3-14构造DFA，识别{0，1}上的语言，该语言的每个字符串为二进制数时，代表的数字能被5整除。第一百四十九页，共一百七十三页，2022年，8月28日分析：对5的余数只能为0、1、2、3和4使用5个状态分别代表已经读入的数字除以5的不同的余数的等价类：qi：已经读入的数除以5，余数为i的输入串的等价类；其中i=0,1,2,3,4不能接收空串，需要一个开始状态qS第一百五十页，共一百七十三页，2022年，8月28日第一百五十一页，共一百七十三页，2022年，8月28日例3-15构造DFA，识别

{1,2,3}上的语言，该语言的每个字符串挡成十进制数时，代表的数字能被4整除。第一百五十二页，共一百七十三页，2022年，8月28日第一百五十三页，共一百七十三页，2022年，8月28日思考：构造DFA，识别{0，1,2，3，4，5，6，7，8，9}上的语言，该语言的每个字符串挡成十进制数时，代表的数字能整除7

。…第一百五十四页，共一百七十三页，2022年，8月28日总结：构造DFA，识别∑={x1,x2,x3,…xm}上的语言该语言的每个字符串挡成base进制数时代表的数字能整除N。

或对N的余数为K。第一百五十五页，共一百七十三页，2022年，8月28日分析：对N的余数只能为0、1、