形式语言与编译(三)NFA 、e |
您所在的位置:网站首页 › nfa和dfa等价证明 › 形式语言与编译(三)NFA 、e |
DFA 、NFA、 \(\varepsilon-NFA\) 的等价性
这三种自动机定义的语言是同一种语言,都是正规语言 DFA定义的语言可以被NFA接受;NFA定义的语言可以被DFA接受 每一个NFA都能转化为等价的DFA 每个DFA都是NFA的特例 如何将一个NFA转化为DFA观察:NFA中每一个状态映射为一个状态子集 IDEA: 每个状态子集映射为单一的DFA状态 (子集构造方法 subset construction theory) 包含原来状态中终止状态的状态定义为新的终止状态 有了原始的NFA的状态,构造的对应的DFA的子集状态可能有\(2^n\)个。所以我们可以把所有的可能状态列出来,然后连线就可以了。看看每一个状态都有可能去哪些状态。反正所有的状态已经列出来了。。。(妙!!!) 记得最后判定这些列出来的子集含不含终止状态!!! 使得每一个NFA的状态子集DFA都有唯一的状态与之对应 注意:有时候对于所有已经划分好的NFA状态子集进行连线时发现,会有一些状态不可达,也就是这些状态与其他状态彼此孤立。因此需要删除不可达状态。也就是下面所示: 删除不需要的(不可达)状态,然后就得到真正的DFA,上图完了还得标上终止状态。 NFA到DFA的子集构造算法描述 算法总结: 枚举所有的可能子集 确定具体的迁移 仅保留从{q0}出发的可达状态最后可以对状态集合命名,比如上面的\(\{q_0\}\)命名成A 但是当状态数比较大的时候,比如状态数为10,那么是不是意味着要生成\(2^{10}\)个子集合,但是最终却要删去这\(2^{10}\) 中的绝大多数。感觉白白创建,白白浪费资源 优化方法: 为避免枚举幂集,采用"惰性创建状态的方法"。 其实就是不经过上面图中中间表格,而是由第一个表格直接生成具有可达状态的第三个表格,省去了中间巨量无用幂集的创建。直接生成最后有用的可达状态 惰性创建(动态创建)法本着按需引进 的目的 不清楚表格一共有多少行,我们一行一行分析。这就和子集构造法不一样了,子集构造法是一下子把这个表有多少行,每一行是什么都先知道,然后连线的 拿着刚开始的初始状态,一行一行往下进行;当有新状态产生的时候,把这个新产生的状态添加到我们需要确定的可达状态子集 ,一直到没有新状态产生。 随着处理过程,需要引进状态,我们再引进。 这个动态构造算法比子集构造法要好。节省时间、空间、还不用删去不可达状态。实验课推荐这个方法!!! 定理:由NFA通过子集构造法或者动态构造法得到的DFA,和我们原来的NFA,这两个自动机是等价的,有\(L(DFA)=L(NFA)\) 证明过程可以由归纳法。也就是前面讲的扩展转移函数 和 **串=串+一个字符 ** 但是!!! 我们也有这个担忧 一般来说DFA的状态数要比NFA大得多 \(\varepsilon-NFA\) (不接受符号自由转移)其实,\(\varepsilon\)就是不接受任何字符可以转换状态的。\(\varepsilon\)增加了状态机的灵活性 感觉有个\(\varepsilon\)被接受的概率显著增大了,几乎能从40%到93%!!!,就是这么神乎其神 超级灵活,但是也有不接受的,比如上面的11,还是不能接受 例题:构造NFA,接受这样一个串,偶数个0或者奇数个1。(两个自动机用\(\varepsilon\)连接就行) 就是用来处理OR的 带\(\varepsilon\) 的NFA就是做题方便,还是帮助人理解、思考。正真在计算机中处理,还是要变成DFA。 可以先知道带\(\varepsilon\) 的NFA与DFA处理能力是一样的 只有DFA是面向机器的,NFA、\(\varepsilon\) -NFA是面向人的(或者说是面向做题的(滑稽!)) 最终在机器中都得落实到DFA中。但是一般问题也不是说不能用DFA做,是可以做的,就是比较麻烦!!! 由于\(\varepsilon\) 弧比较自由,因此引入团或者叫闭包的概念。就是说它们非常相似,是一伙的。 \(\varepsilon\) -cloure of a state q 我们也叫做 E-CLOURE(q).就是q状态通过\(\varepsilon\)连接起来的那些状态的集合 消除\(\varepsilon\) 有如下几个规则 通过\(\varepsilon\) 能够到达最终状态的状态 都是最终状态 通过一个终结符前前后后有多个\(\varepsilon\) ,可以将这些合并成最后只有一个终结符 \(\varepsilon\)\(\varepsilon\)\(\varepsilon\) a\(\varepsilon\)\(\varepsilon\)\(\varepsilon\)\(\varepsilon\) -> a算法思想:\(\varepsilon\)-NFA 转化成 NFA 再转化成 DFA \(\varepsilon\)-NFA =NFA = DFA 三者的功能是一样的 证明略 都是接受正规语言RE |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |