Video在线视频

欢迎同学们来到《软件理论基础》的MOOC课堂

我们现在继续介绍

这一讲的第六节 文本搜索

在上一节里面我们介绍了

NFA表示的语言

和DFA表示的语言是一样的

也就是这两个自动机是等价的

都是正则语言

在NFA转化为DFA里面

它们的状态数那是一个指数级的

也就是说它们的复杂度是不一样的

状态量增加了

那变迁数当然也增加了

自动机的复杂度就增加了

但是有一种NFA转DFA

它们很特殊

这个状态它没有增加

这就是我们要讲的文本搜索

文本搜索是介绍了要设计一个NFA

接受这样的字符串

web就是web

或者ebb为后缀的这个字符串

当然也可以是其它的字符串

那整个的输入字母可能是ASCII

要构造一个这样的NFA

实际上很简单

这个NFA的构造

我们只用7个状态就可以了

这是接受w，e，b这条路径

这是接受e，b，b这条路径

我们用7个状态就构造出

这两个串为后缀的字符串

那现在如果要把这个NFA

转化为跟它等价的DFA

那跟上一节我们构造的算法来看

这里面的状态 它这7个的话

就可能有2的7次方这么一个状态

实际上我们可以不需要那么多状态

可以这样构造

这里给的是NFA

我要构造跟它等价的DFA

我首先状态 我不按那种幂集合来构造

像这个串 它的前缀我看有哪一些

web的前缀分别为w，we，web

那这三个前缀在NFA里面

从初态1经过它们这些串的路径

能够到达哪些状态呢

w 1 状态1

经过w可以到达状态1

同时初态1经过w也可以到达状态2

也就是说把w作为输入字母

从初态它可以到达的是1和2

we从初态1

它能够到达哪呢

这里还可以到达1、3、5

那web类似的

它就可以到达状态1、4、6这三个状态

这三个集合我们考虑它们构成的状态

下面我们再看串ebb

ebb它的前缀分别为e，eb，ebb

那它从初态能够分别到达的状态呢

是1，5、1，6、1，7

把这集合 这有6个集合

就有6个状态

假如初态是7个状态

我用7个状态

就可以把这个DFA 把它构造出来

初态是这里给的1

刚才前缀能到达的有1，2

有1，3，5

有1，4，6

还有1，5、1，6、1，7

因为在NFA里面4和7是终态

只有含有4和7的在这里面状态的

我们把它作为DFA的终态

那我们只要这七个状态

我就可以构造DFA了

这个DFA状态已经写了

下面就是状态转移

状态转移那分别我要讨论web，ebb

它们这些字母的转移

当然还要考虑ASCII、∑当中

其它字母的转移

首先我就看web这些字母的转移

在DFA里面它是怎么转移的

我看DFA的转移

实际上还是回到NFA里面

从状态初态1输入w的时候

从这个1可以到我们的状态2

当然也可以到状态1

所以我们在这里 w在这个地方

就有一条路径

状态2输入1到状态3

在这里就有1，2这个状态 输入1到这里

从1输入e到5

这里1输入e到1，5

那1，3，5这个里面的状态呢

输入b 能够到这个状态

5，6也是输入b

能够到达这个状态

6到7输入b

也能够到这里

这个1，4，6

6输入b到状态7

这里有条路径

这是DFA对每一个输入字母

都必须要转移

实际上它这个w里面

自己到自己应该有一个转移了

所以这里基本上我们其他状态里面

w 输入w的 基本上转到1，2这里面来

输入e的 基本上转到1，5这里面来了

增加了有这么一些转移

在转移是把web这个转移给定了

那剩下的ASCII还有很多

因为这里状态1有一个自环

所以到这里我们其他的

都把它转移到状态1

这里1和w转移出去了

剩下的就是自环

w和1转移出去了

剩下的都转移到状态1里面

这里也是 w，e，b都转移出去了

剩下的就转到状态1

这个1，4，6这个状态

也是web都有转移 剩下的都转移到1

这儿还有状态1，6、1，7都到状态1

也有转移

这样我们就构造了

跟这个NFA等价的DFA

这里面别看这么复杂

但是它状态的个数 跟这里是一样多的

这就跟我们之前介绍的算法来比

这里就简单非常非常多了

就说明文本搜索

它转成DFA 状态个数没增加

它接受的语言应该是一样的

下面我们介绍这么一个例子

输入字母是0，1

这个语言是倒数第三个符号是1的

这样的串的集合

我们要构造它的NFA

那构造NFA

你只要把倒数第三个是1

这个要确定出来

这q0是我们的初态

在初态这里面有一个自环0，1

接下来我们要把倒数第三个1

我们要确定出来

也就是说只要有一个1

我们转移到状态q1

那这个就作为倒数第三个了

那剩下后面两个

就是你把倒数第二个和倒数第一个

这个状态就描述出来

也是0，1到q3

这个输入的是1

那这接受的一定是倒数第三个是1的

所以这个就是一个接受状态

所以倒数第三个是1的

这个NFA非常简单

但是这个语言

如果你要用DFA表示

那可能就比较复杂

那你还要怎么去构造状态

怎么去找转移

这个时候构造了

可能你一时还没什么想法

当我们现在讲了NFA和DFA它们是等价的

可以从NFA把DFA构造出来

因为这个NFA 构造这个语言很简单

我们从这个NFA构造DFA

我们只需要采用我们上一节讲的算法

你比如说我们把这个NFA摆到这里

然后再通过那个算法

你们构造跟它等价的

这个DFA这个构造

大家看这个构造并不复杂

我们按原来算法可以构造出来

而且这些状态

我可以分别用其他的名字

像p0，p1，p2，p3一直到p7

用八个状态就OK了

就把这个DFA就表示出来了

用了这个算法

我就很容易把刚才的语言

把DFA画出来了

我就是从NFA来转化的

而且有了这个状态转移表

我把这个DFA的状态转移图可以给出来

这里告诉我们

从语言构造DFA的一种方法

当然这是倒数第三个是1的

这样的字符串

这样我们觉得在画这个图

还可以画出来这个DFA

如果是我们再把这个语言修改一下

你比如说 倒数第十个是1

然后我们看这个例子

输入字母是0，1

设计一个倒数第十个是1的DFA

刚才我们说倒数第三个是1的

我们用了八个状态

那倒数第十个是1的

要画这样的DFA

可能要用1000多个状态

那我们用什么方法

去表示这个自动机呢

我们介绍了状态转移图

我们还介绍了状态转移函数

还介绍了状态转移表

这三种表示形式各有自己的优势

你像这个语言

你用状态转移图来做的话

你可能是做不出来的

那下面我们用状态转移函数

来做这个题

这个自动机DFA的状态

我们怎么构造呢

假设设这些变量x是0或1

x1也是0或1

移到x2、x3、x10都是0或1

因为它们可以取0，可以取1

变量设置之后

在构造这个DFA的它的状态 我再构造

分别是x1、x2、xk

k大于或等于1 小于或等于10

我们状态给了之后

接下来我们的字母表当然是0，1

我们的初始状态 我就取空串

接下来终态

后面就是任意的了

我只要是第一个取1

其他的都不在乎

只要是这个串的长度是10

我就把这样的状态

就定为终态和接受状态

状态有了 输入字母有了

初始状态有了 终态有了

现在是状态转移

这是DFA的状态

x1、x2、xk

k呢 是大于或等于1

小于或等于10

我输入一个x

x因为它要么是0 要么是1

那输入这个x的时候

下面就看这个k 是小于10还是等于10

如果是小于10

那我就直接把x放在这个串之后

得到了这一个状态

就跟我们表示q这个状态

是一样的形式

因为x也是0或者1

那如果是这个k是等于10

等于10 你再输入这个字符的时候

那我们就把第一个x

就把它挤掉了

那就从x2开始一直到xk到x

这个当然长度就为10了

就是如果k等于10的话 就转移到10了

这个转移规则也是非常明确的

靠这个简单的方法

就构造出接受倒数第10个是1的

0的字符串

就是用状态转移函数来给出来的

这个方法不但是能够给出倒数第10个

你任意确定

你看我倒数第n个是1的这个字符串

你同样用这个方法来构造

这就是这个例子说明什么呢

我们的自动机表示形式有多种

你像状态转移图 状态转移表

状态转移函数

它们各自有自己的优势

今天这一章里面我们介绍了

另外一类自动机

叫非确定有限自动机 也就是NFA

我们给出了NFA的它的概念

它的形式化定义 还有它的语言

我们证明了NFA表示的语言

跟DFA表示的语言

实际上是一样的 都是正则语言

它们的转化算法我们给定了

从软件的角度

我们可以做这么一个软件

就写一个程序

将任何一个NFA转化为

跟它等价的DFA

这个程序构造并不复杂

因为我们可以把它作为一个作业

大家练习练习

虽然NFA可以转化为跟它等价的DFA

它的复杂度可能不一样

DFA的复杂度可能比NFA复杂很多

好 今天的课就讲到这里

谢谢大家