第三章-3-RE-NFA-DFA

知识

3.7将正则表达式转换为NFA（汤普森构造）

我们现在关注的是转变注册会计师。Expr。去NFA

这种结构使我们能够：

• 正则表达式（描述标记）

• NFA（描述语言特征）

• DFA（可以“计算机化”）

• 缩小DFA

构建过程是组件式的

以特定的顺序使用特定的技术从正则表达式的组件构建NFA。

注：构造是“语法导向”翻译，即正则表达式的语法是NFA构造和结构的决定因素。

汤普森构造

• 这是将正则表达式转换为NFA的一种方法。

• 还有其他的转换方法（效率更高）。

• 汤普森的构造是一种简单而系统的方法。

  它保证生成的NFA将有一个最终状态和一个开始状态。

• 构造从最简单的部分（字母符号）开始。

要为复杂正则表达式创建NFA，将其子表达式的NFA组合起来以创建其NFA。

• 识别空字符串ε

• 识别字母表∑中的符号a

• 如果N（r1）和N（r2）是正则表达式r1和r2的NFA

• 对于正则表达式r1 | r2

• 对于正则表达式r1 r2

• 对于正则表达式r*

构造算法：R.E。→ NFA

施工过程：

1：识别正则表达式的子表达式

∈

∑ symbols

r | s

rs

r* 2：为每个子表达式描述NFA的“片段”

拼凑NFA

1. 为了∈ 在正则表达式中，构造NFA

2. 对于A∈ ∑ 在正则表达式中，构造NFA

3. （a）如果s，t是正则表达式，N（s），N（t）它们的NFA s | t有NFA：

其中i和f是新的开始/结束状态，以及∈-从i到N（s）和N（t）的旧起始状态，以及从它们的所有最终状态到f，都引入了移动。 3. （b）如果s，t是正则表达式，则N（s），N（t）其NFAs st（串联）具有NFA：

式中，i是N（s）（或替换项下的新）的起始状态，f是N（t）（或新）的最终状态。重叠将N（s）的最终状态映射到N（t）的开始状态

3. （c）如果s是正则表达式，N（s）其NFA，s*（克莱恩星）有NFA：

其中：i是新的开始状态，f是新的最终状态

∈-将i移到f（接受空字符串）

∈-将i移到旧起点，旧终点移到f

∈-把旧的结局变为旧的开始（为什么？）

施工特性

设r为正则表达式，且为NFA N（r），则

1. N（r）有#个状态≤ r的2*（#符号+#运算符）

2. N（r）正好有一个开始和一个接受状态

3. N（r）的每个状态最多有一个输出边a∈ ∑ 或者最多两个∈’s

4. 小心地为所有状态指定唯一的名称！

NFA的直接模拟

模拟汤普森构造的NFA算法

DFA模拟

s ← s0
c ← nextchar;
while c ≠ eof do
	s ← move(s,c);
	c ← nextchar;
end;
if s is in F then return “yes”
else return “no”

NFA模拟

S ← ε-closure({s0})
c ← nextchar;
while c ≠ eof do
	S ← ε-closure(move(S,c));
	c ← nextchar;
end;
if S ∩ F ≠ Ø then return “yes”
else return “no”

最终注释：R.E.至NFA施工

• 因此，当NFA是使用以前的技术构造时，NFA可以通过算法来模拟

• 算法运行时间与|N |*|x |成正比，其中|N |是状态数，|x |是输入长度

• 或者，我们可以从NFA构造DFA，并使用生成的Dtran识别输入：

整合概念

• 设计词法分析器生成器

规则。Expr。→ NFA建设

NFA→ DFA转换

词法分析器的DFA模拟

• 每种模式都能识别词素

• 每个模式都由正则表达式描述

例题

汤普森结构

(a|b) * a

(ab*$c)\mathrm{\mid }(a(b\mathrm{\mid }cc)\; |\; (a(b|c$*))

解析此正则表达式的树：

练习

使用Thompson构造从正则表达式构造NFA。 a(a|b)${}^{+}^+$(b|c)(c|∈)

作业

一、使用Thompson构造法为正规式构造NFA，写出每个NFA处理符号串过程中的状态转换序列

一、使用Thompson构造法为下列正规式构造NFA，写出每个NFA处理符号串“ababbab”过程中的状态转换序列。

a) (a | b)*
b) (a* | b*)*
c) ((e | a)b*)*
d) (a | b)*abb(a | b)*

参考答案

a

a) (a | b)*

ababbab状态转换序列：

0→1→2→4→6→1→3→5→6→1→2→4→6→1→3→5→6→1→3→5→6→1→2→4→6→1→3→5→6→7

b

b) (a* | b*)*

ababbab状态转换序列：

0→1→2→4→6→8→10→1→3→5→7→9→10→1→2→4→6→8→10→1→3→5→7→5→7→9→10→1→2→4→6→8→10→1→3→5→7→9→10→11

c

c) ((e | a)b*)*

ababbab状态转换序列：

0→1→3→5→6→7→8→9→1→3→5→6→7→8→7→8→9→1→3→5→6→7→8→9→10

d

d) (a | b)*abb(a | b)*

ababbab状态转换序列：

0→1→2→4→6→1→3→5→6→7→8→9→10→11→12→14→16→11→13→15→16→17

二、利用子集构造法将 NFA 转换为 DFA，写出分析符号串过程中的状态转换

二、利用子集构造法将第一题得到的 NFA 转换为 DFA，同样写出分析符号串 ababbab 过程中的状态转换。

a) (a | b)*
b) (a* | b*)*
c) ((e | a)b*)*
d) (a | b)*abb(a | b)*

参考答案

a

a) (a | b)*

ε-closure({0}) = { 0, 1, 2, 3, 7 } = A
ε-closure(δ(A, a)) = {1, 2, 3, 4, 6, 7} = B
ε-closure(δ(A, b)) = {1, 2, 3, 5, 6, 7} = C
ε-closure(δ(B, a)) = B
ε-closure(δ(B, b)) = C
ε-closure(δ(C, a)) = B
ε-closure(δ(C, b)) = C

ababbab状态转换序列：

A→B→C→B→C→C→B→C

b

b) (a* | b*)*

ε-closure({0}) = { 0, 1, 2, 3, 4, 5, 8, 9, 10, 11 } = A
ε-closure(δ(A, a)) = {1, 2, 3, 4, 5, 6, 8, 9, 10, 11 } = B
ε-closure(δ(A, b)) = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11} = C
ε-closure(δ(B, a)) = B
ε-closure(δ(B, b)) = C
ε-closure(δ(C, a)) = B
ε-closure(δ(C, b)) = C

ababbab状态转换序列：

A→B→C→B→C→C→B→C

c

c) ((e | a)b*)*

ε-closure({0}) = { 0, 1, 2, 3, 4, 6, 7, 9, 10 } = A
ε-closure(δ(A, a)) = {1, 2, 3, 4, 5, 6, 7, 9, 10 } = B
ε-closure(δ(A, b)) = {1, 2, 3, 4, 6, 7, 8, 9, 10} = C
ε-closure(δ(B, a)) = B
ε-closure(δ(B, b)) = C
ε-closure(δ(C, a)) = B
ε-closure(δ(C, b)) = C

ababbab状态转换序列：

A→B→C→B→C→C→B→C

d

d) (a | b)*abb(a | b)*

ε-closure({0}) = { 0, 1, 2, 3, 7 } = A
ε-closure(δ(A, a)) = {1, 2, 3, 4, 6, 7, 8 } = B
ε-closure(δ(A, b)) = {1, 2, 3, 5, 6, 7 } = C
ε-closure(δ(B, a)) = B
ε-closure(δ(B, b)) = {1, 2, 3, 5, 6, 7, 9 } = D
ε-closure(δ(C, a)) = B
ε-closure(δ(C, b)) = C
ε-closure(δ(D, a)) = B
ε-closure(δ(D, b)) = {1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 17 } = E
ε-closure(δ(E, a)) = {1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 } = F
ε-closure(δ(E, b)) = {1, 2, 3, 5, 6, 7, 11, 12, 13, 15, 16, 17} = G
ε-closure(δ(F, a)) = F
ε-closure(δ(F, b)) = {1, 2, 3, 5, 6, 7, 9, 11, 12, 13, 15, 16, 17 } = H
ε-closure(δ(G, a)) = F
ε-closure(δ(G, b)) = G
ε-closure(δ(H, a)) = F
ε-closure(δ(H, b)) = {1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 15, 16, 17 } = I
ε-closure(δ(I, a)) = F
ε-closure(δ(I, b)) = G

ababbab状态转换序列： A→B→D→B→D→E→F→H