数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究非确定有限自动机可以转换为确定有限自动机吗？
是的，我们可以将 NFA 转换为 DFA。对于每个 NFA，都存在一个等价的 DFA。等价性是根据语言接受来定义的。由于 NFA 不过是在输入符号上允许零个、一个或多个转换的有限自动机。它始终可以构建有限自动机，该自动机将并行模拟 DFA 在特定输入符号上的所有移动，然后得到一个有限自动机，在该自动机中，每个输入符号上都将恰好有一个转换。在这里，对应于 NFA，存在一个 DFA。为了构造等价于 NFA 的 DFA，应该记住 DFA 的状态是 NFA 状态的集合。
算法 NFA – 到 – DFA
输入 − NFA，状态集 N = {n0,n1……nn}，起始状态 n0。
输出 − DFA，状态集 D′={d0,d1,d2……dn}，起始状态 d0。
d0=ε−closure (n0)
D′={d0}
将 d0 设置为未标记
while there is an unmarked state d in D′. {
set d marked {
For each input symbol 'a' {
Let T be a set of states in NFA to which there is a transition on 'a' from some state ni in d d′=ε−closure (T).
If d′ is not already present in D′ {
D′=D′∪{d′}
Add transition d→d′,labeled 'a'
set d′ unmarked
}
}
}
}示例 − 为以下 LEX 程序设计词法分析器。
AUXILIARY DEFINITION S
letter = A|B|C|…….|Z
digit = 0 |1|2|………|9
TRANSLATION RULES
begin {return 1}
end {return 2}
If {return 3}
then {return 4}
else {return 5}
letter (letter+digit)* {value=Install ( );return 6}
digit + {value=Install ( );return 7}
< {value=1;return 8}
<= {value=2;return 8}
= {value=3;return 8}
< > {value=4;return 8}
> {value=5;return 8}
>= {value=6;return 8}解决方案
- 各种模式的组合 NFA 将是
- 将 NFA 转换为 DFA − 对应的 DFA 将是。
状态 {0, 1, 7, 11, 14, 19, 24, 26, 28, 30, 33, 35, 38, 40} 被组合并命名为 q0 以创建 DFA 的起始状态。
在组合的 NFA 中，从状态 1 到 2 和从状态 24 到 25 的转换是相同的，因为输入“b”是一个字母。
状态 2、25 被组合。类似地，其他状态也被组合。
状态 29、31 和 36 被组合，因为它们都在获得输入“<”后到达。
类似地，其他状态也被组合。
更新于: 2021年10月26日
1K+ 次浏览
广告