编译原理第四周

编译原理

一. 已知正则表达式$(1)((a|b)^*|aa)^*b$ 和正则表达式$(2)(a|b)^*b$,请分别构造出对应的 NFA 以及 DFA,
证明表达式(1)和(2)是等价的

$((a|b)^*|aa)^*b$ NFA:

DFA状态转换表：

NFA状态	DFA状态	a	b
$\{0, 1, 2, 3, 4, 6, 9, 10, 13, 14\}$	A	B	C
$\{1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 14\}$	B	B	C
$\{1, 2, 3, 4, 6, 7, 8, 9, 10, 13, 14, 15\}$	C	B	C

合并状态A, B：

NFA状态	DFA状态	a	b
$\{0, 1, 2, 3, 4, 6, 9, 10, 13, 14\}$	A	A	C
$\{1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 14\}$	C	A	C

最小化DFA：

$(a|b)^*b$ NFA:

DFA状态转换表：

NFA状态	DFA状态	a	b
$\{0, 1, 2, 3, 5, 8\}$	A	B	C
$\{2, 3, 4, 5, 7, 8\}$	B	B	C
$\{2, 3, 5, 6. 7, 8, 9\}$	C	B	C

合并状态A, B：

NFA状态	DFA状态	a	b
$\{0, 1, 2, 3, 4, 6, 9, 10, 13, 14\}$	A	A	C
$\{1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 14\}$	C	A	C

最小化DFA：

表达式（1） （2）的最小DFA是完全相同的， 所一两个表达式等价

二. 构造一个 DFA,它接受集合{0,1}上 0 和 1 的个数都是偶数的字符串

三. 画出下图所示 DFA 的状态迁移表,并将其最简化

DFA状态转换表：

DFA状态	1	2
A	B	E
B	G	C
C		G
D	A	C
E	G	C
G	G

合并B、E：

DFA状态	1	2
A	B	B
B	G	C
C		G
D	A	C
G	G