离散数学 (第七版) 课件 第六部分 形式语言与自动机

1

形式语言和

自动机初步

2第10章形式语言和自动机初步10.1形式语言和形式文法10.2有穷自动机10.3正则表达式10.4图灵机3字符串和形式语言形式文法形式文法的分类

0型文法

1型文法或上下文有关文法

2型文法或上下文无关文法

3型文法或正则文法正则文法与上下文无关文法的应用语法分析树10.1形式语言与形式文法4语言的基本要素汉语字符:汉字和标点符号字符集:合法字符的全体句子:一串汉字和标点符号语法:形成句子的规则形式语言字符字母表字符串形式文法

5字符串字母表Σ:非空的有穷集合字符串:Σ中符号的有穷序列

如Σ={a,b}

a,b,aab,babb字符串

的长度|

|:

中的字符个数

如|a|=1,

|aab|=3空字符串ε:长度为0,即不含任何符号的字符串an:n个a组成的字符串Σ*:Σ上字符串的全体6

子字符串(子串):

字符串中若干连续符号组成的字符串前缀:最左端的子串后缀:最右端的子串例如

=abbaab

a,ab,abb是

的前缀

aab,ab,b是

的后缀

ba是

的子串,但既不是前缀,也不是后缀

本身也是

的子串,且既是前缀,也是后缀

也是

的子串,且既是前缀,也是后缀7字符串的连接运算设

=a1a2…

an,

=b1b2…

bm,

=a1a2…

anb1b2…

bm称作

与

作的连接

如

=ab,

=baa,

=abbaa,

=baaab

对任意的字符串

,

,

(1)(

)γ=

(

)

即,连接运算满足结合律

(2)

=

=

即,空串

是连接运算的单位元

n个

的连接记作

n

如(ab)3=ababab,

0=

8形式语言定义:Σ*的子集称作字母表Σ上的形式语言,

简称语言例如Σ={a,b}

A={a,b,aa,bb}

B={an

|n∈N}

C={anbm|n,m≥1}

D={

}

空语言Ø9形式文法一个例子——标识符<标识符>:<字母>|<标识符><字母>|<标识符><数字><字母>:a|b|…|z|A|B|…|Z<数字>:0|1|…|910形式文法的定义定义

形式文法是一个有序4元组G=<V,T,S,P>,其中(1)V是非空有穷集合,V的元素称作变元或非终极符(2)T是非空有穷集合且V∩T=Ø,T的元素称作终极符(3)S∈V称作起始符(4)P是非空有穷集合,P的元素称作产生式或改写规则,形如

,其中

,

∈(V∪T)*且

≠

.11文法生成的语言设文法G=<V,T,S,P>,

,

∈(V∪T)*,

:存在

∈P和

,

∈(V∪T)*,使得

=

,

=

称

直接派生出

.

:存在

1,

2,…,

m,使得

=

1

2

…

m=

称

派生出

.恒有

(当m=1时)

是

的自反传递闭包12文法生成的语言

定义设文法G=<V,T,S,P>,G生成的语言

L(G)={

∈T*∣S

}

L(G)由所有满足下述条件的字符串组成:(1)仅含终结符;(2)可由起始符派生出来.定义如果L(G1)=L(G2),则称文法G1与G2等价.13举例例1

文法G1=<V,T,S,P>,其中V={S},T={a,b},

P:S→aSb|ab

L(G1)={anbn|n>0}例2

文法G2=<V,T,S,P>,其中V={A,B,S},T={0,1},

P:S→1A,A→0A|1A|0B,B→0

L(G2)={1x00|x

{0,1}*}例3

文法G3=<V,T,S,P>,其中V={A,B,S},T={0,1},

P:S→B0,B→A0,A→A1|A0,A→1

L(G3)=L(G2),G3与G2等价14例4

G=<V,T,S,P>,其中V={S,A,B,C,D,E},T={a},

P:(1)S→ACaB(2)Ca→aaC(3)CB→DB(4)CB→E(5)aD→Da(6)AD→AC(7)aE→Ea(8)AE→

试证明:

i1,S证:a2和a4的派生过程

S

ACaB(1)

AaaCB(2)

AaaE(4)AEaa2次(7)

a2(8)举例(续)15例4(续)

SAaaCB

AaaDB(3)

ADaaB2次(5)

ACaaB(6)

AaaaaCB2次(2)

AaaaaE(4)

AEaaaa4次(7)

a4(8)16例4(续)先用归纳法证明

i1,

当i=1时结论成立,假设对i结论成立,(3)2i次(5)(6)2i次(2)得证对i+1结论成立,故对所有的i成立.17例4(续)于是,

i1,

(4)2i次(7)(8)可以证明:

L(G)={|

i1}18形式文法的分类

—Chomsky谱系0型文法(短语结构文法,无限制文法)1型文法(上下文有关文法,CSG):

所有产生式

→

,满足|

|

|

|CFG

另一个等价的定义:所有的产生式形如

A

→

其中A

V,

,,

(V∪T)*,且

2型文法(上下文无关文法,CFG):

所有的产生式形如

A→

其中A

V,

(V∪T)*,19形式文法的分类(续)3型文法(正则文法):右线性文法和左线性文法的统称右线性文法:所有的产生式形如

A→

B或A→

左线性文法:所有的产生式形如

A→B

或A→

其中A,B

V,

T*例1是上下文无关文法例2是右线性文法,例3是左线性文法,都是正则文法例4是0型文法20Chomsky谱系0型语言:0型文法生成的语言1型语言(上下文有关语言,CSL):如果L-{

}可由1型文法生成,称L是1型语言2型语言(上下文无关语言,CGL):2型文法生成的语言3型语言(正则语言):3型文法生成的语言

如

{1x00|x

{0,1}*}是正则语言(例1){anbn|n>0}是上下文无关语言(例2,3){|i

1}是0型语言(例4)定理0型语言

1型语言

2型语言

3型语言定理设G是右(左)线性文法,则存在左(右)线性文法G

使得L(G

)=L(G).21正则文法和CFG的应用例描述算术表达式的文法

Gexp={{E,T,F},{a,+.-.*,/,(,)},E,P}其中E:算术表达式,T:项,F:因子,a:数或变量

P:E→E+T|E-T|TT→T

F|T/F|FF→(E)|

a这是上下文无关文法22巴克斯范式

BNF用来描述程序设计语言语法的一种形式系统标识符的定义<数字>::=0|1|2|…|9<字母>::=A|B|

|Z|a|b|…|z<标识符>::=<字母>|<标识符><字母>|<标识符><数字>BNF中::=相当于生成式中的→,带括号<>的是非终极符,不带刮号<>的是终极符.23BNF(续)数的定义<无正负号整数>::=<数字>|<无正负号整数><数字><整数>::=<无正负号整数>|+<无正负号整数>|-<无正负号整数><十进制小数>::=.<无正负号整数><指数部分>::=E<整数><整数小数部分>::=<无正负号整数>|<十进制小数>|<无正负号整数><十进制小数><无正负号数>::=<整数小数部分>|<指数部分>|<整数小数部分><指数部分><数>::=<无正负号数>|+<无正负号数>|-<无正负号数>如0,231,+12,.25,-0028.79,E+3,-E-02,35.20E6等

24语法分析树定义

设CFGG=<V,T,S,P>,如果有序树H满足条件:(1)每一个顶点有一个标记,树根的标记是起始符S,内点的标记是非终极符,树叶的标记是终极符或

,并且当树叶的标记是

时,它是其父亲的惟一的儿子.(2)若标记为A的分支点的儿子的标记从左到右构成字符串

(V

T)*,则A

P,那么称H是G的一棵语法分析树或生成树.H的所有树叶的标记从左到右构成的字符串

称作H的结果,记作<

>.25语法分析树例

用Gexp生成a+a

a.派生E

E+T

T+T

F+T

a+T

a+T

F

a+F

F

a+a

F

a+a

a派生没有提供如何执行+和

的信息,即没有给出a+a

a的语义.而语法分析树给出对该式的正确理解:先

后+,EE+TT

FFaaaTF2610.2

有穷自动机确定型有穷自动机(DFA)非确定型有穷自动机(NFA)带

转移的NFA(

-NFA)27确定型有穷自动机定义确定型有穷自动机(DFA)是一个有序5元组M=

Q,

,

,q0,F,其中

(1)状态集合Q:非空有穷集合

(2)输入字母表

:非空有穷集合

(3)

状态转移函数

:Q

Σ→Q(4)

初始状态q0

Q(5)

终结状态集F

Q

控制器an…ai…a2a128DFA接受的语言把

扩张到Q

*上

*:Q

*→Q,递归定义如下

q

Q,a

和w

*

*(q,

)=q

*(q,wa)=

(

*(q,w),a)定义

w

*,如果

*(q0,w)

F,则称M接受w.M接受的字符串的全体称作M接受的语言,记作

L(M),即

L(M)={w

*|

*(q0,w)

F}29DFA接受的语言(续)例1

M=

{q0,q1},{a},

,q0,{q1}

(q0,a)=q1,

(q1,a)=q0

L(M)={a2k+1

|kN}30例奇偶校验码M=

{q0,q1},{0,1},

,q0,{q1}

L(M)={

{0,1}*

|

含有偶数个1}O11100q0q131非确定型有穷自动机定义非确定型有穷自动机(NFA)

M=〈Q,

,

,q0,F〉,其中Q,

,q0,F的定义与DFA的相同,而

:Q

→P(Q)32实例

→q0

q1

*q2

q3*q401

{q0,q3}

{q2}{q4}{q4}

{q0,q1}

{q2}{q2}

{q4}例2一台NFA33NFA接受的语言

*:Q

*→Q

递归定义如下:q

Q,a

和w

*

*(q,

)={q}

*(q,wa)=定义

w

*,如果

*(q0,w)∩F≠

,则称M接受w.M接受的字符串的全体称作M接受的语言,记作L(M),即

L(M)={w

Σ*|

*(q0,w)∩F≠

}34例2(续)L(G)={x00y,x11y

|x,y{0,1}*}

wδ*(q0,w)110101101110110{q0,q1}{q0,q3}{q0,q1}{q0,q1,q2}{q0,q2,q3}35DFA与NFA的等价性

用M

=

Q

,

,

,q0

,F

模拟M=

Q,

,

,q0,F

Q

=P(Q),q0

={q0}F

={A

Q

|A∩F≠}

A

Q和a

Σ,

定理对每一个NFAM

都存在DFAM

使得L(M)=L(M

)36模拟实例NFAMDFAM

δ

01→q0q1*q2{q0,q1}{q0}{q2}

δ

01→{q0}

{q1}*{q2}{q0,q1}*{q0,q2}*{q1,q2}*{q0,q1,q2}

{q0,q1}{q0}{q2}

{q0,q1,q2}{q0}{q0,q1}{q0}{q2}

{q0,q1,q2}{q0}

37模拟实例(续)δ

01→{q0}

{q0,q1}*{q0,q1,q2}{q0,q1}{q0}{q0,q1,q2}{q0}{q0,q1,q2}{q0}不可达状态:从初始状态出发永远不可能达到的状态删去所有的不可达状态,不会改变FA接受的语言.如M

中的{q1},{q2},{q0,q2},{q1,q2}和都是不可达状态,删去这些状态得到M

38带

转移的非确定型有穷自动机ε

转移:不读如何符号,自动转移状态.

-NFA:

:Q(

∪{

})→P(Q)例3

-NFAM

01

→q0q1*q2{q1}

{q2}

{q2}

{q0}εεL(M)={(01)n|n

0}39用DFA模拟

-NFA定理

对每一个

-NFAM

都存在DFAM

使得

L(M)=L(M

)DFA,NFA和

-NFA接受同一个语言类设

-NFA

M=

Q,

,

,q0,F,q

Qq的

闭包E(q):从q出发,经过

转移能够到达的所有状态,递归定义如下

(1)E(q)包含q;(2)如果p

E(q),则

(p,

)

E(q).40用DFA模拟

-NFA(续)模拟的方法与用DFA模拟不带

的NFA的方法基本相同,只是要用E(q)代替q.用DFAM

=

Q

,

,

,q0

,F

模拟

-NFAM=

Q,

,

,q0,F

Q

=P(Q),q0

=E(q0)F

={A

Q

|A∩F≠}

A

Q和a

Σ,

构造DFAM

时不需要对不可达状态进行计算,做法如下:从q0

=E(q0)开始,对每一个a

计算

的值,然后对每一个新出现的子集计算

的值,重复进行,直至没有新的子集出现为止.41模拟实例——例3(续)

01

→q0q1*q2{q1}

{q2}

{q2}

{q0}

01→*{q0,q2}

{q1}

{q1}

{q0,q2}

-NFAMDFAM

qE(q)q0q1q2{q0,q2}{q1}{q0,q2}42有穷自动机和正则文法的等价性定理

对每一个右线性文法G都存在

-NFAM使得L(M)=L(G);反之,对每一个

-NFAM都存在右线性文法G使得L(G)=L(M).(FA识别的语言类与正则文法生成的语言类是同一个语言类

正则语言.)43DFA提供了识别正则语言的算法.例

奇偶检验码算法输入:

=a1a2

an

i

0;q0:i

i+1;ifi>nthen接受elseifai=0thengotoq0;q1:i

i+1;ifi>nthen拒绝elseifai=0thengotoq1elsegotoq0O11100q0q144用

-NFA提高设计效率非确定性没有增加FA的能力,但极大地提高了设计效率.例如,要检查一个0,1串是否含有子串00,设想NFA具有一种猜想能力,当它读到0时猜想这个0是否是子串00的第一个0.如果猜想是,就转移到状态q1;如果猜想不是,则保持状态q0.在状态q1,如果接着读到0,则转移到q2.这时已检查到子串00,此后状态停留在q2不动,q2是接受状态.4510.3正则表达式正则表达式用

-NFA模拟正则表达式46闭包定义

设L,L1,L2是字母表

上的语言,记

L1

L2={uv|u

L1且v

L2},称作L1和L2的连接,简记作L1L2.又记

L0={

},

Li=LLi-1,i

1闭包

L*=正闭包

L+=47例显然L*={u1u2

ut|t

0,ui

L,1

i

t},

L+={u1u2

ut|t

1,ui

L,1

i

t}.设A={a},B={b},则

A+={an|n

1},A*={an|n

0},B+={bn|n

1},B*={bn|n

0},

A+B+={anbm|n,m

1},A*B*={anbm|n,m

0},

AB={ab},(AB)+={(ab)n|n

1},(AB)*={(ab)n|n

0},

A

B={a,b},(A

B)*={u1

ut|t

0,ui=a或ui=b,1

i

t}.48正则表达式定义

字母表

上的正则表达式及其表示的语言:(1)是正则表达式,它表示空集,(2)

是正则表达式,它表示{

},(3)每一个a

是正则表达式,它表示{a},(4)若r和s分别是表示语言R和S的正则表达式,则(r+s),(r

s)和(r*)是正则表达式,分别表示R

S,R

S和R*,(5)有限次运用上述规则得到的表达式是正则表达式.正则表达式

表示的语言记作<

>.运算的优先等级:*,,+.可省略不必要的括号.r

s写成rs.rr*缩写成r+,<r+>=R+.49例<a+b+>={anbm|n,m

1}<1(0+1)*00>={1x00|x

{0,1}*}50用

-NFA模拟正则表达式

{

}

{a}

L1

L2L1

L251模拟实例

1(0+1)*00

52正则语言小结定理

下述命题是等价的,(1)L是正则语言,(2)存在右线性文法G使得L(G)=L,(3)存在左线性文法G使得L(G)=L,(4)存在DFAM使得L(M)=L,(5)存在NFAM使得L(M)=L,(6)存在

-NFAM使得L(M)=L,(7)存在正则表达式

使得<

>=L.5310.4图灵机图灵机的基本模型图灵机接受的语言

——递归可枚举语言54问题的提出1900年D.Hilbert在巴黎第二届数学家大会上提出著名的23个问题.第10个问题:如何判定整系数多项式是否有整数根?要求使用“有限次运算的过程”1970年证明不存在这样的判定算法,即这个问题是不可判定的,或不可计算的.55计算模型从20世纪30年代先后提出图灵机

A.M.Turing,1936年

转换演算

A.Church,1935年递归函数

K.Gödel,1936年正规算法

A.A.Markov,1951年无限寄存器机器

J.C.Shepherdson,1963年

…56Church-Turing论题已经证明这些模型都是等价的,即它们计算的函数类(识别的语言类)是相同的.Church-Turing论题:直观可计算的函数类就是图灵机以及任何与图灵机等价的计算模型可计算(可定义)的函数类57图灵机的基本模型定义图灵机(TM)

M=

Q,

,

,

,q0,B,A,其中

(1)状态集合Q:非空有穷集合;(2)输入字母表

:非空有穷集合;(3)带字母表

:非空有穷集合且

;(4)

初始状态q0

Q;控制器58图灵机的基本模型(续)(5)空白符B

-

;(6)接受状态集A

Q;(7)动作函数

是Q

到

{L,R}Q的部分函数,

即dom

Q

.

(q,s)=(s

,R