数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学正则表达式如何转换为有限自动机（NFA）？
正则表达式是标记的表示。但是，要识别标记，可能需要标记识别器，它就是一个有限自动机（NFA）。因此，可以将正则表达式转换为NFA。
正则表达式转换为NFA的算法
输入 − 正则表达式 R
输出 − 接受由 R 表示的语言的 NFA
方法
对于 ε，NFA 是
对于 a，NFA 是
对于 a + b，或 a | b，NFA 是
对于 ab，NFA 是
对于 a*，NFA 是
示例 1 − 为正则表达式 a(a+b)*ab 绘制 NFA
解答
示例 2 − 为 a + b + ab 绘制 NFA
解答
示例 3 − 为 letter (letter+digit)* 绘制 NFA
解答
示例 4 − 为 (0+1)*1(0+1) 绘制对应的 NFA
解答
ε−闭包 (s) − 它是由状态 s 通过仅 ε-转移所能到达的状态集。
- 如果 s、t、u 是状态。初始时，ε−闭包 (s) = {s}。
- 如果 s→t，则 ε−闭包 (s) = {s, t}。
- 如果 s→t→u，则 ε−闭包 (s) = {s, t, u}
将重复此过程，直到覆盖所有状态。
算法：ε−闭包 (T)
T 是一组状态，需要找到其 ε−闭包 (s)。
压入 将 T 中的所有状态压入堆栈
ε −闭包 (T) = T
While (stack not empty) {
Pop s, the top element of Stack
for each state t, with edge s→t {
if t is not present in ε−closure (T) {
ε−closure (T)=ε−closure (T)∪{t}
Push t on Stack
}
}
}示例 − 为以下 NFA 查找 ε−闭包(0)、ε−闭包(1)、ε−闭包(4)。
解答
ε−closure(0)={0,1,2,5,7}
ε−closure(1)={1,2,5}
ε−closure(4)={4,7,1,2,5}
更新于：2021年10月26日
26K+ 次浏览
广告