形式语言与自动机

形式语言与自动机清华大学计算机系茹逸中ryzcst@126.com参考文献：

IntroductiontoAutomataTheory,Languages,andComputation（并没有参考，这本书我丢了）王生原老师的形式语言与自动机课件（所有动画都是从这里拷的）王生原老师的编译原理课件（复习考试的时候看的）Q&AQ：你获得过什么奖？A：我获得过的最高等级的正式奖项是NOIP2010/2012一等奖。Q：听说第一课堂的课很难？A：是的。Q：听懂这门课需要什么先修知识？A：整数加法，整数减法，整数乘法，含有多个自变量的代数式。Q：那如果我听不懂这门课怎么办？A：（和周围的基友）嘿嘿嘿。Q&AQ：那如果我听得懂课呢？A：那你就来回答问题吧！你不仅能让课堂里的妹子（？）们投来崇拜的目光，还可以获得白巧克力饼干一块。Q：哇！那我怎么才能听得懂课呢？A：不知道。Q：TATA：（我是不会告诉你你还可以去第二课堂的）目录概述形式语言自动机正规语言与有限状态自动机正规语言正规语言的应用确定型有限状态自动机(DFA)非确定型有限状态自动机(NFA)DFA与NFA的等价性正规语言与NFA的等价性泵引理目录上下文无关语言与下推自动机上下文无关语言下推自动机上下文无关语言与下推自动机的等价性编译器编译器的基本流程词法分析语法分析LR(0)分析LR(1)分析概述Introduction1.1形式语言什么是形式语言？形式语言(Formallanguage)是用精确的数学或机器可处理的公式定义的语言。（来源于）在计算机形式语言理论中，形式语言是定义在字母表上的某些有限长字符串的集合。一个形式语言可以包含有限多或无限多字符串。1.1形式语言{this,that}就是一个形式语言，在这个语言中只包含两个字符串。{233,2333,23333…}(2后面跟多于1个的3)也是一个形式语言，在这个语言中包含无穷多个字符串，其中2333333属于这个语言，而23,2323不属于这个语言。C++语言是一种形式语言1.1形式语言形式语言与自然语言有什么区别？自然语言就是人类讲的语言，这种语言是自然进化而成的，其特点是界限模糊，规则不明确，计算机难以理解。形式语言则是为了某些特定的应用而人为设计的语言，它的特点是界限清晰，规则明确，计算机容易理解。1.1形式语言为什么要学习形式语言？装逼与计算机交流的必备工具在模式识别、文本分析、编译原理、计算理论等领域有重要作用1.1形式语言形式语言的分类：0型语言，又称递归可枚举语言，能力相当于图灵机(TuringMachine)1型语言，又称上下文有关语言，能力相当于线性有界自动机(linearboundedautomaton,LBA)2型语言，又称上下文无关语言，能力相当于下推自动机(pushdownautomaton,PDA)3型语言，又称正规语言，能力相当于有限状态自动机(finitestateautomaton,FSA)1.2自动机什么是自动机？

自动机是依赖输入的符号和内存区域内的符号，根据转移函数“跳转”过一系列状态，并在一个区域内读写符号的一种机器。为什么要学自动机？

一类自动机往往能够接受一类文法。自动机是最接近于计算机工作方式的一类模型。

1.2自动机自动机的分类：确定型有限状态自动机(DFA)和非确定型有限状态自动机(NFA)，它们可以接受正规语言。下推自动机(PDA)，可以接受上下文无关语言确定型下推自动机(DPDA)的能力比PDA差，可以接受某些上下文无关语言图灵机(TM)，可以接受递归可枚举语言确定型和非确定型的图灵机是等价的。与图灵机等价的还有多于一个计数器的计数器机、双栈机、半无穷纸带的图灵机等

正规语言与有限状态自动机RegularLanguageandFiniteStateMachine2.1正规语言

2.1正规语言

2.1正规语言

2.1正规语言

2.2正规语言的应用文本搜索网页爬虫文件管理词法分析2.2正规语言的应用Notepad++提供正规表达式的搜索.匹配任意字符.

|匹配表达式左边和右边的字符.

[]匹配列表之中的任何单个字符.例如,"[ab]"匹配"a"或者"b"."[0-9]"匹配任意数字.

[^]匹配列表之外的任何单个字符.例如,"[^ab]"匹配"a"和"b"以外的字符."[^0-9]"匹配任意非数字字符.

*其左边的字符被匹配任意次

+其左边的字符被匹配至少一次

?其左边的字符被匹配0次或者1次2.2正规语言的应用匹配不含前导0的非负整数[1-9][0-9]*|0匹配整数(-?[1-9][0-9]*)|0匹配整数或小数((-?[1-9][0-9]*)|0)(\.[0-9]+)?2.3确定型有限状态自动机

Q={q0,q1,q2,q3}

={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}q0q1q2q3确定有限自动机

转移图表示的DFAq1q2q3q0确定有限自动机DFA如何接受输入符号串q2q3q0q1确定有限自动机DFA如何接受输入符号串q2q0q1q3确定有限自动机DFA如何接受输入符号串q2q3q0q1确定有限自动机DFA如何接受输入符号串q1q2q3q0确定有限自动机DFA如何接受输入符号串q1q3q0q2确定有限自动机DFA如何接受输入符号串q1q0q2q3

确定有限自动机DFA如何接受输入符号串q1q2q3q0确定有限自动机DFA如何接受输入符号串q1q3q0q2确定有限自动机DFA如何接受输入符号串q1q2q3q0

确定有限自动机DFA如何接受输入符号串q1q2q3q0确定有限自动机DFA如何接受输入符号串q2q3q0q1确定有限自动机DFA如何接受输入符号串q2q0q1q3确定有限自动机DFA如何接受输入符号串q1q3q0q2确定有限自动机DFA如何接受输入符号串q1q2q3q0确定有限自动机DFA如何接受输入符号串q2q3q0q1

确定有限自动机DFA如何接受输入符号串2.4非确定型有限状态自动机

0100111010

非确定有限自动机NFA如何接受输入符号串

举例

(p

,

)

={p}

(p

,0)

={q}

(p

,01)

={q,r}

(p

,010)

={q}

(p

,0100)

={q}

(p

,01001)={q,r}

pq

r0{q}

{q}

{q,r}

1非确定有限自动机

扩展转移函数适合于输入字符串2.5DFA与NFA的等价性

pq

r0{q}

{q}

{q,r}

10

{q}1

{p}{q}

{r}{p,q}

{p,r

}

{q,r

}

{p,q,r

}

{q}{q,r}

{q}{q,r}{q}

{q}{q,r}{q}{q,r}

DFA和NFA的等价性

子集构造法举例2.6正规语言与NFA的等价性

正规语言转化为NFA

基础:1对于，构造为

3对于a，构造为a2对于，构造为

归纳构造过程(从正规表达式构造等价的

-NFA)

（Thompson

构造法）2.6正规语言与NFA的等价性

归纳:1对于R+S

，构造为

归纳构造过程(从正规表达式构造等价的

-NFA)

（Thompson

构造法）2.6正规语言与NFA的等价性

2对于RS

，构造为

3对于R*

，构造为

归纳:

归纳构造过程(从正规表达式构造等价的

-NFA)

（Thompson

构造法）2.5正规语言与NFA的等价性

设正规表达式1*0(0+1)*,构造等价的

-NFA.0+1

1*

举例(从正规表达式构造等价的

-NFA)2.6正规语言与NFA的等价性

(0+1)*

1*0(0+1)*

举例(从正规表达式构造等价的

-NFA)2.6正规语言与NFA的等价性

2.6正规语言与NFA的等价性

DFA转化为正规语言使用路径迭代法或者状态消去法在这里，我们介绍路径迭代法(类似于动态规划)2.6正规语言与NFA的等价性

将DFAD的状态集用{1,2,…,n}表达，且初态为1;对所有1

i,j

n,0

k

n，叠代计算R(ikj)，这里,R(ikj)为表示如下语言的正规表达式：w

L(R(ikj))iff从i到j有一条标记为w的路径,且这条路径上除i和j之外的所有状态的编号不大于k通过2的叠代过程，最终可计算出R(inj)（i,j=1,2,…,n）将所有R(1nj)（j为任一终态）相“

”

基础:k=0Case1i

j若不存在从i到j的弧，则R(i0j)=

；若仅存在一条从i到j的弧，且标记为a

，则R(i0j)=a；若存在多条从i到j的弧，且标记为a1,a2,…,am，则R(i0j)=a1

a2…am

；Case2i=j若不存在从i到自身的圈，则R(i0j)=

；若存在一个从i到自身的圈且标记为a

，则R(i0j)=

a；若存在多个从i到自身的圈，且标记为a1,a2,…,am

，则R(i0j)=

a1a2…am

；2.6正规语言与NFA的等价性

归纳:假设R(ki-j1)（i,j=1,2,…,n）已经求出.则叠代公式为R(ikj)=R(ki-j1)

R(ki-k1)(R(kk-k1))*R(kk-j1)Case1路径不经过k.此时，标记该路径的字符串属于L(R(ki-j1));Case2路径经过k至少一次.此时，标记该路径的字符串属于L(R(ki-k1)(R(kk-k1))*R(kk-j1)).如下图所示：分析:考虑从i到j的路径（除i和j之外的所有状态的编号不大于k

）R(ki-k1)(R(kk-k1))*R(kk-j1)2.6正规语言与NFA的等价性

2.7泵引理设L是正规语言,则存在常数n

1

,使得任一长度不小于n的字符串w

L,|w|n,都可以分成三个部分,即w=xyz,且满足下列条件：

1.y

.2.|xy|

n.3.对任何k

0,都有xykzL.2.7泵引理

2.7泵引理

2.7泵引理泵引理不是正规语言的充分条件L={aibjcki,j,k0,若i=1则j=k}2.7泵引理泵引理的其它应用蚂蚁从v0出发，沿着图G的边爬行。开始时，它的体力为1。每爬过一条边，它的体力都会下降为原来的ρ倍，ρ是小于1的正常数。蚂蚁爬到某个顶点时的幸福度，是它当时的体力与该点权值的乘积。蚂蚁可以爬过无穷多个点，求它最大幸福度和。2.7泵引理泵引理的其它应用CTSC2011幸福路径(by钟诚)蚂蚁从v0出发，沿着图G的边爬行。开始时，它的体力为1。每爬过一条边，它的体力都会下降为原来的ρ倍，ρ是小于1的正常数。蚂蚁爬到某个顶点时的幸福度，是它当时的体力与该点权值的乘积。蚂蚁可以爬过无穷多个点，求它最大幸福度和。2.7泵引理泵引理的其它应用清华集训2013day4(bycxm)给定一张有向图，有无穷多个猴子从起点出发，每回合可以走向任意一个相连的点，没有路走的猴子会消失。从S回合到T回合，每个点会出现一个金币，只要有猴子在这个点上即可得到金币。求从每个点得到的金币数。上下文无关语言与下推自动机Context-FreeLanguageandPushdownAutomaton3.1上下文无关语言

3.1上下文无关语言

3.1上下文无关语言

3.1上下文无关语言

3.1上下文无关语言

3.2下推自动机

举例所接受语言为L=0n1n

n

1

的一个PDA

P=({q0,q1,q2},

{0,1},{X,Z0},

,q0,Z0,{q2})

其中，转移函数定义如下

(q0,0,Z0)={(q0,XZ0)},(q0,0,X)={(q0,XX)},(q0,1,X)={(q1,)},(q1,1,X)={(q1,)}(q1,

,Z0)={(q2,Z0)}

对其余的参数值，

(q,a,Y)=3.2下推自动机3.3上下文无关语言与下推自动机的等价性

3.3上下文无关语言与下推自动机的等价性

编译器Compiler词法分析语法分析语义分析+中间代码生成中间代码生成+中间代码优化目标代码优化目标代码生成字符流形式的源程序单词流形式的源程序源程序的语法分析树目标代码优化的目标代码后端前端中间代码（1）┆中间代码（n）分析综合中端4.1编译器的基本流程

4.2词法分析在编译器中，利用正规语言进行词法分析。词法分析是编译器编译程序的一个重要步骤，它可以分析出程序中包含的各个词法单元，例如关键字、数字、符号等等。程序中的任何词法单元都是可以用正规表达式匹配的。例如(-?[1-9][0-9]*)|0可以匹配所有整数If可以匹配条件语句关键字While可以匹配循环语句关键字+可以匹配加法运算符…4.3语法分析

4.3语法分析4.3语法分析语法分析主要有两类方法。一类是自顶向下进行推导，即从S开始，每次将一个非终结符替换成某个推导式的右半部分。另一类是自底向下进行归约，即针对输入的单词流，每次将某个推导式的右半部分归约成一个非终结符。现在的编译器一般采用的是自底向上的归约方式，我们在这里仅介绍自底向上的归约方式。自顶向下的推导较为简单，有兴趣的同学可以查阅相关资料。4.3语法分析

4.3语法分析如何消除不确定性？采用LR分析L是指从左到右扫描单词序列R是指采用最右推导LR分析是移进-归约分析，它根据当前状态机所在的状态已经输入串的后续字符来选择移进或者按照某个推导式归约LR分析可以处理一部分的上下文无关语言，但是对于某些上下文无关语言，LR分析可能会产生移进/归约冲突(即算法不知道在当前状态下应该移进还是归约)或归约/归约冲突(即算法不知道在当前状态下应该按照哪个推导式归约)4.3语法分析LR(0)分析LR(0)分析是指在选择移进还是按照哪条推导式归约时向前看0个单词(即只根据当前状态而不顾后续输入进行选择)LR(1)分析LR(1)分析是指在选择移进还是按照哪条推导式归约时向前看1个单词4.4LR(0)分析

LR（0）状态机中的状态

LR（0）FSM

的状态是一个LR（0）项目集的闭包（closure）计算LR（0）项目集I

的闭包CLOSURE(I)的算法：

functionCLOSURE(I）

{J:=I;

repeatforJ中的每个项目A

.B

和产生式B

do若B

.

不在J中，则加

B

.

到J中

until

上一次循环不再有新项目加到J中

returnJ

};4.4LR(0)分析G[E]:(1)E

E+T(2)E

T

(3)T

(E)(4)T

dI0:E’

.EE

.E+T

E

.T

T

.(E)

T.dI4:T

(.E)E

.E+T

E

.T

T

.(E)

T.dI1:E’

E.E

E.+TI2:E

T.I3:T

d.I5:T

(E.)E

E.+TI2I3I6:E

E+.TT

.(E)

T.dI7:T

(E).I6I8:

E

E+T.I4I3(ETdETd(+)+Td(4.4LR(0)分析

LR（0）分析表的构造假定C={I0,I1,…，In}，令状态Ik对应的LR（0）分析表的栈顶状态为k；令含有项目S’

.S的状态为I0,因此0为初态。ACTION表项和GOTO表项可按如下方法构造：若项目A

α.aβ属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”;

若项目A

α.属于Ik,那么，对任何终结符a,置ACTION[k,a]为“用产生式A

α进行归约”，简记为“rj”;其中，假定A

α为文法G的第j个产生式；若项目S’

S.属于Ik,则置ACTION[k,#]为“接受”，简记为“acc”;若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,A)=j;分析表中凡不能用上述规则填入信息的空白格均置上“出错标志”4.4LR(0)分析G[E]:(1)E

E+T(2)E

T

(3)T

(E)(4)T

dI0:E’

.EE

.E+T

E

.T

T

.(E)

T.dI4:T

(.E)E

.E+T

E

.T

T

.(E)

T.dI1:E’

E.E

E.+TI2:E

T.I3:T

d.I5:T

(E.)E

E.+TI2I3I6:E

E+.TT

.(E)

T.dI7:T

(E).I6I8:

E

E+T.I4I3(ETdETd(+)+Td(4.4LR(0)分析LR（0）分析表的构造举例G’[E’]

栈顶状态ACTIONGOTOd+()#ET01234567812accs6r2（0）E’

E

（1）E

E+T

（2）E

T（3）T

(E)（4）T

dr2r2r4r4r4s4s3s3s452s6s7s3s48r2r2r4r4r3r3r3r3r3r1r1r1r1r14.4LR(0)分析LR(0)分析容易产生冲突文法G[E]:(1)E

E+T(2)E

T

(3)T

T

F(4)T

F(5)F

(E)(6)F

v

(7)F

dG[E]的增广文法G’[S]:(0)S

E(1)E

E+T(2)E

T

(3)T

T

F(4)T

F(5)F

(E)(6)F

v

(7)F

d4.4LR(0)分析LR(0)分析法产生冲突举例I0:S

.EE

.E+T

E

.TT

.T

F

T

.F

F

.(E)

F.vF.dI1:S

E.E

E.+TI3:T

F.I6:F

d.E(+I4:F

(.E)E

.E+T

E

.TT

.T

F

T

.F

F

.(E)

F.vF.dI9:F

(E.)E

E.+TI12:F

(E).I5:F

v.I2:E

T.T

T.

FI7:E

E+.TT

.T

F

T

.F

F

.(E)

F.vF.dI8:T

T.F

F

.(E)

F.vF.dI10:E

E+T.T

T.

F

I11:T

T

F.

T(Fvd

EI2TI3FI5vI6d)I7+F(I4vI5dI6TI3FI4(I5vI6dI8

增广文法G’[S]:(0)S

E(1)E

E+T(2)E

T

(3)T

T

F(4)T

F(5)F

(E)(6)F

v

(7)F

d4.4LR(0)分析4.5LR(1)分析

LR（1）FSM的构造举例增广文法G’[S]:(0)S

E(1)E

(L,E)(2)E

F

(3)L

L,E

(4)L

E(5)F

(F)(6)F

dI0:S

.E,#E

.(L,E),#

E

.F,#F

.(F),#F.d,#I1:S

E.,#I4:F

d.,#EI3:E

(.L,E),#

F

(.F),#L

.L,E,,

L

.E,,

F

.(F),,

)F.d,

,

)E

.(L,E),,E

.F,,I5:L

E.,,I2:E

F.,#I7:F

(F.),#E

F.,,I6:E

(L.,E),#L

L.,E,,

F(dEdLF(I9:F

d.,,

)I8:E

(.L,E),,F

(.F),,

)

L

.L,E,,

L

.E,,F

.(F),,

)F.d,

,

)E

.(L,E),,E

.F,,I16:F

(F).,#)4.5LR(1)分析I12:E

F.,,

)

EI11:E

(L,E.),#L

L,E.,,

I6:E

(L.,E),#L

L.,E,,

F(dI10:E

(L,.E),#L

L,.E,