非确定性和Kleene定理.docx
- 文档编号:7217904
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:19
- 大小:94.40KB
非确定性和Kleene定理.docx
《非确定性和Kleene定理.docx》由会员分享,可在线阅读,更多相关《非确定性和Kleene定理.docx(19页珍藏版)》请在冰点文库上搜索。
非确定性和Kleene定理
4非确定性和Kleene定理
4.1非确定型有限自动机
为了证明正则语言等价于能够被FA识别的语言,我们先对FA作一些方便性的扩充。
仍然具有有限的状态数,且识别语言的能力保持不变。
一些限制放宽了,更容易构造和解释。
例子4.1图4-1a显示了例子3.14构造的FA,它接受的语言是(11+110)*0,图4-1b显示了一个不同于一般FA的例子,状态q4没有转移箭头,而状态q0在输入字符为1时有两个转移箭头。
状态 q4没有转移箭头,含义是不存在一个起始字符为a(本例为0或1)的输入字符串能够使得状态从q4转移到某个接受状态,我们可以增加一个失败(或死,dead)状态f,对于输入字符a,状态q4转移到f,失败状态的含义是只有进入没有离开的转移箭头。
显然任何被成功接受的字符串都不会进入失败状态,因此为了简化图面,往往省略失败状态,而不会影响自动机的接受能力。
状态q0在同一个输入字符时有多个转移箭头,看起来是对传统FA的很大的突破。
我们无法象传统FA机那样线性地记录字符串在FA中的转移过程,而在某些步骤出现了歧义,因此FA机要并行地运算各种可能。
但这种带多向转移的图似乎更适合正则表达式,比如图4-1b,从q0到q0有两个循环,一个表示的字符串是(11)*,另一个表示的是(110)*,综合起来,从q0到q0的字符串是(11+110)*,则从q0到q4的字符串是(11+110)*0。
反过来,根据正则表达式(11+110)*0也能够很直观地画出相应的带多向转移的FA。
由于同一个字符串可能带来FA多个状态转移路径,因此现在问题变成,是否存在一条到达接受状态的路径,这类似于根据正则表达式生成字符串,某些步骤可以有多种尝试,只要其中一种尝试生成了字符串,则认为该字符串符合这个正则表达式。
因此这类FA给正则语言的分析引入了一个新的概念,即猜测尝试。
现在不考虑这种具体实现的问题,而考虑如何形式化定义这类FA。
我们只需要修改(或扩充)传统FA的转移函数的定义。
传统的转移函数输入一个字符,转移到一个状态,即Q中的一个元素,例子4.1中的转移函数则转移到0个或多个状态,即Q的一个子集,包括空集。
我们称这种转移函数是非确定的,而这样的FA称为非确定型FA(nondeterministicFA,NFA),而传统的FA称为确定型FA(deterministicFA,DFA)。
目前我们看起来NFA比DFA要强大很多,以后将证明任何一个NFA都能构造一个完全模拟它的DFA,因此非确定型没有增强FA的能力。
定义4.1非确定型有限自动机(NFA)是一个5元组,M=(Q,,q0,,A),Q和是非空有限集,q0Q,AQ,转移函数定义为:
:
Qx2Q
2Q是Q的幂集,即所有Q的子集组成的集合,则函数的值从确定型的一个状态放松成一个状态集。
思考:
初始状态可不可以由一个状态扩充成一个状态集?
类似地扩充连续转移函数(或称字符串的转移函数)*的定义,其形式仍然是:
*(p,xa)=(*(p,x),a)
自然想到用递归定义,首先,空串不影响状态变迁,但转移函数的值是一个集合,而不是单个状态,因此:
*(p,)={p}
而对于非空字符串x=a1a2...an,*(p,x)的值也应该是一个集合,设q*(p,x),含义是存在一个状态路径:
p0,p1,...,pn,其中p0=p,pn=q,对每一个i,0
pi*(pi-1,ai)
定义4.2a(NFA的*函数的非递归定义)给定NFAM=(Q,,q0,,A),p是任意一个状态,则*(p,)=p,对于任意一个字符串x=a1a2...an,*(p,x)是所有满足下面条件的状态q组成的集合。
存在一个状态路径p0,p1,...,pn,其中p0=p,pn=q,对每一个i,0
pi*(pi-1,ai)
为了得到递归定义,令x=yan。
根据定义4.2a,对于*(p,x)的任意一个状态q,都存在*(p,y)中的一个状态r,使得q(r,an)。
反过来,对于*(p,y)中的任何一个状态r,(r,an)的元素都属于*(p,yan),即可以递归定义如下:
*(p,yan)={q|q(r,an)且r*(p,y)}
进一步的简化形式见下面的定义4.2b。
定义4.2b(NFA的*函数的递归定义)给定NFAM=(Q,,q0,,A),函数*:
Qx*2Q定义如下:
1.*(q,)={q}
2.*(q,ya)=
显然,*(q,a)=(q,a)仍然成立,因此递归的起点实际上可以是长度为1的字符串。
定义4.3NFAM=(Q,,q0,,A)接受字符串x的条件是*(q0,x)A。
M接受(或识别)的语言由所有被M接受的字符串组成,记为L(M)。
一个语言L被M识别当且仅当L=L(M)。
例子4.2M=(Q,,q0,,A),Q={q0,q1,q2,q3},={0,1},A={q3},的定义如下表:
q
(q,0)
(q,1)
q0
{q0}
{q0,q1}
q1
{q2}
{q2}
q2
{q3}
{q3}
q3
参见图4-2,现在要确定M接受的语言。
分析:
对一些字符串计算*(q0,x),x的长度逐渐增加。
首先计算长度为1的字符串(直接根据上面的转移表),
*(q0,0)={q0},*(q0,0)={q0,q1}
*(q0,11)
*(q0,01)
*(q0,111)
*(q0,011)
见104页
M接受的语言的正则表达式是:
{0,1}*{1}{0,1}2。
这是我们在例子3.15中讲到的L3,右数第3个字符为1。
参照图4-2的NFA,能够很容易地构造出接受语言Ln的、带n+1个状态的NFA。
在例子3.14,我们说明了接受Ln的DFA至少需要2n个状态,这里显示了接受同样语言的NFA往往比最简单的DFA具有少得多的状态。
尽管NFA在概念上作了很有效的扩充,接受字符串的方式也简洁得多,但NFA接受语言的能力并没有增加,任何能被NFA接受的语言也能被DFA接受。
我们将给出一个构造性证明,显示消除NFA的非确定性的通用方法,得到的DFA保持了NFA识别字符串的性质,因此识别同样的语言。
我们知道NFA状态转移函数的结果是一个集合,而DFA相应结果是一个元素,因此将NFA转变成一个DFA的简单方法就是把集合看成一个更大集合(幂集)的元素,而原来的单个元素看成只有一个元素的集合,这种方法称为子集构造法(subsetconstruction),DFA中的状态是NFA的状态集的子集。
这是一种类似空间换时间的方法,假设NFA的状态个数为n,则DFA的状态个数为2n(近似),但是DFA在识别一个长度为m的字符串时,只需要m次状态移动,设字母表共有k个字符,则NFA可能需要k+k2+...+km次状态转移,形成一个深度为m,宽度为k的搜索树。
定理4.1对于任何一个NFAM接受的语言L,都存在一个DFAM接受。
证明:
设NFAM={Q,,q0,A,},则构造DFAM1={Q1,,q1,A1,1}如下:
Q1=2Q
q1={q0}
1(q,a)=
A1={qQ1|qA}
最后一点揭示了NFA接受字符串x,只需要存在一条转移路径最终到达接受状态就可以了,不需要所有的转移路径都到达接受状态。
为了证明NFAM和DFAM1接受同样的语言,只需证明下面一个事实,对任意的字符串x,
1*(q1,x)=*(q0,x)
注意此处1*和*定义的不同,1是DFA的连续转移函数(参见定义3.3),是NFA的连续转移函数(参见定义4.3),它将状态映射到状态集的子集。
证明:
字符串x存在递归定义,因此可以在x上使用结构归纳法来证明。
1)归纳基础,x=,要证明1*(q1,x)=*(q0,x)。
1*(q1,x)=1*(q1,)=q1={q0}
*(q0,x)=*(q0,)={q0}
因此,归纳基础成立。
2)归纳推理,任给x,设1*(q1,x)=*(q0,x),要证明1*(q1,xa)=*(q0,xa)。
1*(q1,xa)=1(1*(q1,x),a)=1(*(q0,x),a)=
=*(q0,xa)
归纳推理成立,证明完毕。
字符串x被M接受,当且仅当*(q0,x)A,当且仅当1*(q1,x)A,当且仅当1*(q1,x)A1,当且仅当x被M1接受。
定理4.1的证明提供了一个消除NFA非确定性的算法,我们用下面的例子说明这个算法。
例子4.3给例子4.2给出的NFA构造相应的DFA。
分析:
例子4.2给出的NFA共有4个状态,因此相应的DFA至多有16个状态,如果采用例子3.16的方法,只保留那些初始状态能够到达的状态,则状态数将大大减少。
设相应的DFAM1={Q1,,q1,A1,1},其中q1={q0}。
则从初始状态出发,逐步构造DFA的状态和转移函数。
1({q0},0)={q0}
1({q0},1)={q0,q1}---新状态
1({q0,q1},0)=(q0,0)(q1,0)={q0}{q2}={q0,q2}---新状态
1({q0,q1},1)=(q0,1)(q1,1)={q0,q1}{q2}={q0,q1,q2}---新状态
1({q0,q2},0)=(q0,0)(q2,0)={q0}{q3}={q0,q3}---新状态
1({q0,q2},1)=(q0,1)(q2,1)={q0,q1}{q3}={q0,q1,q3}---新状态
1({q0,q1,q2},0)=...
1({q0,q1,q2},1)=...
...
上面的过程可以用一个表来描述,这个表就是前面讲到的状态转移表。
表中每一格对应上面的每一行计算式。
q
(q,0)
(q,1)
{q0}
{q0}
{q0,q1}
{q0,q1}
{q0,q2}
{q0,q1,q2}
{q0,q2}
{q0,q3}
{q0,q1,q3}
{q0,q1,q2}
...
...
...
整个过程可以用一个算法(程序)来完成,多次迭代,直到没有新状态产生才停止。
而且能够保证根据这种方法构造的DFA是对应该NFA的最少状态DFA。
参见图4-3。
问题:
写出构造NFA的相应DFA的算法。
例子4.4同样的方法可用来处理例子4.1b中NFA,计算得到的整个转移状态表如下:
q
(q,0)
(q,1)
{q0}
{q4}
{q1,q2}
{q4}
{q1,q2}
{q0,q3}
{q0,q3}
{q0,q4}
{q1,q2}
{q0,q4}
{q4}
{q1,q2}
如果用q0代替{q0},p代替{q4},r代替{q1,q2},s代替,t代替{q0,q3},u代替{q0,q4},则得到图4-1a。
4.2带空转移的非确定型有限自动机
为了简化正则表达式和有限自动机的接受语言能力相当的证明,本节进一步扩充自动机的定义。
下面例子显示了这种扩充的作用。
例子4.5构造正则表达式E=0*(01)*的相应的有限自动机。
分析:
显然容易构造0*和(01)*的FA,分别如图4-4a和图4-4b所示。
现在考虑如何利用这两个FA完成整个FA的构造,即如何构造两个FA的连接运算。
图4-4c给出了一个NFA,将这两个FA组合起来,能够接受语言L(E)。
考虑的关键是给图4-4b的初始状态的添加初始字符。
我们知道每个独立FA隐含的初始字符是空字符,为了消除这个,图4-4c增加了一条从q0到q2的连接两个FA的转移箭头。
上述方法在两个FA间添加的一些转移箭头很不直观、很不明显,不是一种很规范、可形式化的方法。
为了简化两个FA的连接运算,我们允许NFA有更多猜测下一步状态的自由,即状态q0可以在未接受任何字符的情况下转移到q1,如图4-4d所示。
前面显示了NFA的一个优点是比接受同样的语言的DFA需要少得多的状态数和更简洁的转移函数表,现在进一步放松条件后,新的NFA可能需要更少的状态数和转移箭头。
问题:
状态q0能否和状态q1合并?
定义4.4带空转移的NFA(记为NFA-)是一个5元组M=(Q,,q0,,A),其中Q和是非空有限集,q0Q,AQ,转移函数定义为:
:
Qx({})2Q
类似NFA的定义(参见定义4.1),我们需要扩展定义连续转移函数,以便适用于NFA-,它的基本思想是一致的,即*(q,x)表示的是字符串在NFA-中从状态q出发合法流动,最终停止在的状态。
现在需要扩充定义的概念是“字符串在NFA-中的合法流动”,或称为“NFA-合法地处理字符串”。
图4-5所示的简单例子可以说明这个概念。
我们在字符串01中插入空字符,得到01=x,显然x能够被图4-5所示NFA-接受。
问题:
在一个长度为n的字符串中插入,可能的结果是
,实际使用中将带来组合爆炸,不是可行的方法。
类似定义4.2a,我们给出定义4.5a。
定义4.5a(NFA-的连续转移函数*的非递归定义)任给一个NFA-M=(Q,,q0,,A),p和q是属于Q的任意两个状态,任给一个上的字符串x=a1a2...an,如果存在一个整数m>=n,序列b1,b2,...,bm{}满足b1b2...bm=x,存在一组状态p=p0,p1,...,pm=q,对于每个1<=i<=m,都有pi(pi-1,bi),则在字符串x驱动下,M的状态从p转移到q。
函数*(p,x)的值是所有在x驱动下,从状态p转移到的所有状态组成的集合。
例如图4-5中,字符串01可以驱动状态从q0转移到f,字符串可以驱动状态从r到t,或每个状态到自身。
类似定义4.2b,我们给出递归定义,仍然利用字符串前缀计算的结果来定义整个字符串计算的结果,值得注意的是,我们还需要扩充递归基础的定义。
显然*(q,)的结果不仅包含q,还应该包含从q出发经过转移到达的其他状态。
这里引入一个新的概念,空闭包(-closure,空转移闭包),表示从某个状态(或状态集)出发经过一次或多次空转移到达的所有状态组成的集合。
定义4.6状态集的空闭包(-closureofasetofstates),给定NFA-M=(Q,,q0,,A),S是Q的子集,空闭包(S)递归定义如下:
1.S中每个元素都是(S)的元素;
2.如果q是(S)的元素,则(q,)中的每个元素都是(S)的元素;
3.(S)的元素只可能通过上面两步得到。
与大多数集合的递归定义不同的是,我们能够预先确定空闭包是一个有限集,因此可以将上面的递归定义转换成一个计算空闭包的算法(参见练习2.50)。
规则1提供了初始值,规则2则提供了添加元素的方法,当(S)不再增加时,则算法停止。
算法(计算(S)),输入状态集S,输出S的空闭包,设为T。
1.T=S
2.循环,直到T没有增加新元素
a)循环,逐个检查T中的元素q,
T=T(q,)。
定义4.5b(NFA-的连续转移函数*的递归定义)给定一个NFA-M=(Q,,q0,,A),连续转移函数*:
Qx*2Q定义如下:
1.*(q,)=({q})
2.*(q,ya)=(
)
问题:
对于DFA和NFA都有*(q,a)=(q,a),但对于NFA-,此式不成立。
对照定义4.2b,就是在NFA的连续转移函数计算的结果上,在进行一次空闭包计算。
在识别字符串的过程中,每读入一个字符,每次状态转移都要计算一次空闭包。
字符串x被NFA-M接受的判定条件与NFA一致,当且仅当*(q,x)A。
所有被M接受的字符串组成被M接受的语言,记为L(M)。
例子4.6考虑图4.6所示的NFA-,我们显示如何计算空闭包和连续转移函数。
分析:
({s})=({s,w})
=({s,w,q0})
=({s,w,q0,p,t})
=({s,w,q0,p,t})---没有新元素加入,计算结束
现在计算*(q0,010),根据递归定义,需要计算*(q0,01)、*(q0,0)、*(q0,),这里我们从底向上计算这组函数。
*(q0,)=({q0})
={q0,p,t}
*(q0,0)=(
)
=((q0,0)(p,0)(t,0))
=({p}{u})
=({p,u})
={p,u}
*(q0,01)=(
)
=((p,1)(u,1))
=({r})
={r}
*(q0,010)=(
)
=((r,0))
=({s})
={s,w,q0,p,t}
可见由于,*(q0,010)的结果含有w,w也是A的元素,因此字符串010被图4-6所示的NFA-接受。
另外,010的同等字符串是010,容易发现存在状态序列q0,p,p,r,s,w接受字符串010。
显然连续转移函数的定义提供了一种高效的算法来判定字符串是否被NFA-接受,如果采用插入空字符,然后借用NFA的连续转移函数的计算方法,其时间复杂度为指数级。
上述方法实际上是一种dynamicprogramming,Viterbi算法。
问题1:
写出计算NFA-的连续转移函数的算法。
问题2:
上述方法判定字符串是否被NFA-接受,它能否回答判定中隐含插入的空字符位置?
或判定中哪一步用到了空转移?
比如能否知道010,在第一步和最后步用到了空转移?
问题3:
NFA-可用于模糊查询,或两个字符串的模糊匹配,探寻如何在短的字符串中插入空字符,使得与长字符串达到最大匹配?
在4.1节我们说明了NFA接受语言的能力与DFA相当,现在我们要说明NFA-接受语言的能力与NFA相当,即每个NFA-能够找到一个接受能力相当的NFA。
定理4.2对于任何一个NFA-M=接受的语言L,都存在一个NFAM接受。
(与定理4.1对比)
证明:
设NFA-M={Q,,q0,A,},要构造NFAM1={Q1,,q1,A1,1}。
在定理4.1(为NFA构造相当的DFA)的证明中,我们通过重新定义状态集,从而消除了非确定性。
NFA-中的空转移也是一种非确定性,例如如果一个NFA-中存在:
(p,0)=q
(q,)=r
则状态p在输入字符0时,有两个转移状态q和r。
因此可以用类似(p,0)=r的式子代替(q,)=r,达到消除的目的。
显然凡是(q)中的状态都可类似处理,即通过给空闭包中的每个状态添加转移箭头,就可以删除空转移。
我们需要做的工作仅仅是消除一种特殊的非确定性情况。
通用的方法如下。
Q1=Q
q1=q0
我们利用空闭包实现NFA的转移函数的构造。
对于每个字符a,至多插入两个空字符(非连续的空字符,因为连续的空字符相当于一个空字符),写成a,因此在NFA-中可能一个字符的转移至多两次涉及空闭包。
1(q,a)=(
)
由于
*(q,a)=*(q,a)
=(
)
=(
)
因此可以简写成
1(q,a)=*(q,a)
我们这样定义的目的是:
对任意的状态q和字符串x,1*(q,x)=*(q,x)都成立。
我们发现一个特例,当x=时,除非我们重新构造Q1,否则无论怎么构造1,都难以保证上式成立。
所幸的是,对任意非空字符串x,上式成立。
因此仅仅对A稍作修改,构造的A1,就能保证正确识别空串这个特例。
现在对字符串x实施结构归纳法来证明1*(q,x)=*(q,x)成立。
1.归纳基础,x=a单个字符
1*(q,a)=1(q,a)[1*是NFA的转移函数]=*(q,a)
2.归纳推理,设1*(q,y)=*(q,y),
1*(q,ya)=
=
=
而*(q,ya)=(
),因此需要证明
=(
)
=
=
---空闭包可移到外面
=
---*(q,y)已经计算了空闭包,
因此可去掉一层空闭包。
=
现在我们证明构造NFAM1接受NFA-M相同的语言,分两种情况讨论:
1.M中({q0})A,此时A1=A{q0},对判定的字符串x分两种情况讨论
a)x=
*(q0,)=({q0}),而({q0})A,被M接受
*(q0,)=(q0,)={q0},而{q0}A1={q0},被M1接受
因此同时被M和M1接受。
b)x
*(q0,x)=*(q0,x)=B
要证明BA当且仅当BA1。
分两种情况:
i.q0B,则
({q0})B,由于
({q0})A,因此
BA,x被M接受
另外,A1=A{q0},因此
BA1,x被M1接受
x被M和M1同时接受。
ii.q0B,则
BA=B(A{q0})=BA1,因此
x要么同时被M和M1接受,要么同时被M和M1拒绝。
2.M中({q0})A=,此时A1=A,对判定的字符串x分两种情况讨论
a)x=
*(q0,)=({q0}),而({q0})A=,被M拒绝;
*(q0,)=(q0,)={q0},因为({q0})A=,则{q0}A=,A1=A,因此{q0}A1=,被M1拒绝。
同时被M和M1拒绝。
b)x
*(q0,x)=*(q0,x)=B,由于A1=A
因此BA当且仅当BA1,即x要么同时被M和M1接受,要么同时被拒绝。
上面讨论证明,任意一个字符串x,要么同时被M和M1接受,要么同时被拒绝。
因此M和M1接受同样的语言。
定理4.2证明完毕。
问题1:
子集构造法能否类似定理4.1那样构造出相当的NFA?
问题2:
直接从NFA-构造DFA的算法?
NFA是DFA的更通用的模型,NFA-是NFA的更通用模型,即我们可以说DFA是NFA的特殊情况,NFA是NFA-的特殊情况。
定理4.1和定理4.2的结论可以用下面的定理4.3来总结。
定理4.3对于字母表上的任意语言L,下面三个命题是相当的
1.L可以被FA接受(此处FA就是DFA)
2.L可以被NFA接受
3.L可以被NFA-接受
证明:
根据定理4.1,2可以导出1;根据定理4.2,3可以导出2,现在只要证明1可以导出3。
设L是FAM=(Q,,q0,A,)接受的语言,构造接受L的NFA-M1=(Q,,q0,A,1)。
仅仅需要重新定义转移函数,1:
Q({})2Q,
1(q,)=
1(q,a)={(q,a)}
容易证明M1与M接受相同的语言。
正如定理4.1,定理4.2的证明提供了一个消除NFA-中空转移的算法,下面用两个例子来说明这个算法。
这些例子也可用来作为消除非确定性的练习。
例子4.7图4-7
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 确定性 Kleene 定理