如果两台机器识别相同的语言，则称它们是等价的。换句话说确定型（DFA）和非确定型（NFA）有穷自动机识别相同的语言类；这个论述似乎出乎意料又是极为有用的。怎么说？出乎意料在于NFA好像比DFA能力更强，因此猜想NFA能识别更多的语言。极为有用在于给定的语言，描述识别这个语言的NFA有时比描述识别这个语言的DFA要容易的多。
定理：每台NFA都有等价DFA
证明思路：
具体证明如下：
设 ，求等价的DFA
N 状态图
接受状态
转移&接受
删除不可达状态
DFA状态图
注意这里的 不可达状态 指的是没有箭头指向的状态，意味着没有任何情况可以到达这个状态；
根据上图可写出 DFA 的5元组，至此就完成了 NFA 到 DFA 的转换
词法分析 NFA与DFA的等价性：对于每个NFA M ′都一定存在一个DFA M，使L(M′)=L(M)。 NFA...
前言 如果两台机器识别相同的语言，则称它们是等价的。换句话说确定型（DFA）和非确定型（NFA）有穷自动机识别相同...
每一台NFA都有一台等价的DFA 设是识别语言A的NFA，要构造一套DFA M 识别A。再给出完整的构造之前，先考...
实现一个正则表达式需要几步？ 就三步： 分析正则表达式并构建出NFA 根据NFA得出DFA 根据DFA匹配字符串当...
从正规式开始 一、先将正规式转换成NFA 通过下面的对应法则将正规式转换成NFA 例如： 二、再将NFA转成DFA...
DFA和NFA的区别 1.DFA没有epsilon transaction （必须读入字符） 2.对每一个确定的状...
上一节粗略介绍了回溯，它是NFA特有的功能，DFA不需要回溯，也就不需要保存状态再反复尝试。这样看来，NFA不是更...
正则表达式的引擎分为三种：NFA、DFA、POSIX NFAJavaScript 使用的是 NFA 的正则表达式引...
正则 正则表达式引擎匹配 正则引擎大体上可分为不同的两类：DFA和NFA，而NFA又基本上可以分为传统型NFA和P...
从NFA 到 DFA 的转换 image.png image.png 子集构造法 subset construct...
本文标题：NFA与DFA的等价性
本文链接：https://www.haomeiwen.com/subject/knmfultx.html
网友评论