RE转NFA，NFA转DFA

发表于 | 分类于 ，
字数统计: 341 字

简单笔记

Thompson算法 —— RE -> NFA

基本思想

  • 基本的RE直接构造
  • 复合的RE递归构造
1
2
3
4
5
6
e
  -> eps
  -> 单个字符c	// 前两种可以直接构造
  -> e1e2
  -> e1|e2
  -> e1*	// 后三种递归构造

eps

c

e1e2

e1|e2

e1*

实例

a(b|c)*

子集构造算法 —— NFA -> DFA

基本思想


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
- 0 	  			 => 记为q0，添加进Q状态集中，下同
- q0	——a——> 1
	==a(eps)==> 1 2 3 4 6 *9 => 记为q1
- q1	——b——> 5				// delta(q1)集合，对每个q1元素的b通路
	==b(eps)==> 5 8 *9 3 4 6 => 记为q2	// eps-闭包(eps-closure)
	——c——> 7
	==c(eps)==> 7 8 *9 3 4 6 => 记为q3
	
- q2	——c——> 7
	==c(eps)==> 7 8 9 3 4 6 == q3
	——b——> 5
	==b(eps)==> 5 8 9 3 4 6 == q2
- q3	——b——> 5
	==b(eps)==> 5 8 9 3 4 6 == q2
	——c——> 7
	==c(eps)==> 7 8 9 3 4 6 == q3

算法伪代码

由上面的基本思想，容易得到以下代码：

1
2
3
4
5
6
7
8
9
10
11
q0 <- eps_closure(n0)
Q <- {q0}
workList <- q0
while (!workList.empty())
	q <- workList.pop()
	for each character c	// 256个ASCII码
		t <- eps_closure(delta(q, c))
		if (t not in Q)
			add t to Q
			add t to workList
		D[q, c] <- t	// DFA记录此状态转换

eps-闭包的计算：深度优先

1
2
3
4
5
6
7
set closure = {}
void eps_closure(x)
	closure += {x}
	for each (y| x --eps--> y)
		if (!visited(y))
			eps_closure(y)	// 递归

eps-闭包的计算：宽度优先

1
2
3
4
5
6
7
8
9
10
11
set closure = {}
Q = []		// queue
void eps_closure(x)
	Q = [x]
	while (!Q.empty())
		q <- Q.deQueue()
		closure += q
		for each (y| q --eps--> y)
			if (!visited(y))
				Q.enQueue(y)