我觉得大学时候编译原理我学的还是挺明白的了,当最近因为工作需要用到编译原理这块的知识,好尴尬,全部不记得了!其实这个结果不出乎意料,因为学校的教育是教与背,学生们很少真正理解知识,也很难真正明白如何去应用,时间久了当然全部忘记。算了,不说了,搞的像个愤青。。。
痛定思痛,我决定静下心来再次学一遍、去真正理解,顺便结合需求使用场景,这个过程很美妙,而且保证未来这些知识点不再会轻易从脑海里流逝。
以考试为目的的学习,将会在考试结束开始忘记。
在此声明,本文记录了相关的知识点和举例,以帮我未来快速勾起回忆、梳理知识点,目的是未来需要时看上一眼我就全想起来了。本文不适合新手来读,因为里面没有深入讲解原理,也没有硬性的概念。如果你希望随时查看NFA和DFA的相关知识点,欢迎阅读本文,它可以帮助有相关知识背景的同学快速回顾。
FA——finite automata,有穷自动机,是描述机器特定类型算法的数学方法,有穷自动机可用作描述在输入串中识别模式的过程,因此可以被作为构造扫描程序。FA作为一种识别装置,它能准确地识别正规集。
DFA——deterministic finite automata,确定的有穷自动机。
NFA——nondeterministic finite automata,不确定的有穷自动机。
一个确定的有穷自动机DFA,可以用五元组M表示,M=(K,Σ,f,S,Z)
1. K是一个有穷集,它的每个元素称为一个状态。
2. Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号表。
3. f是转换函数,是在 K × Σ → K 上的映射,即如 f(ki, a) = kj (ki∈K, kj∈K)。即当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态。
4. S ∈ K 是唯一的一个初态。
5. Z ⊆ K 是一个终态集,即结束状态。
例如,DFA M =({s0, s1, s2},{a,b}, f , s0 ,{s2} )
状态转移函数:
f(s0, a) = s1
f(s0, b) = s2
f(s1, a) = s1
f(s1, b) = s2
f(s2, a) = s2
f(s2, b) = s1
状态转换矩阵:
状态 \ 输入符号 | a | b |
s0 | s1 | s2 |
s1 | s1 | s2 |
s2 | s2 | s1 |
DFA的特点是,任何状态k ∈ K,和输入符号a ∈ Σ,f(k,a) 唯一地确定了下一个状态。
一个不确定的有穷自动机NFA,同样用五元组M表示,M=(K,Σ,f,S,Z)
1. K是一个有穷集,它的每个元素称为一个状态。
2. Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号表。
3. f是转换函数,是在 K × Σ* → K 上的多值映射,Σ*代表接受空字符。
4. S ⊆ K 是初始状态集(注意和DFA不同)。
5. Z ⊆ K 是一个终态集,即结束状态。
例如,DFA M =({s0, s1, s2},{a,b}, f , {s0, s2}, {s1})
状态转移函数:
f(s0, a) = s2
f(s0, b) = {s0, s2}
f(s1, b) = s2
f(s2, b) = s1
状态 \ 输入符号 | a | b |
s0 | s2 | s0, s2 |
s1 | Ф | s2 |
s2 | Ф | s1 |
DFA的特点是,可以有多个初始状态,f多值映射,接受字符和空字符。
正规表达式两个重要的等价性:
1. 如果R是字母表 Σ 上的一个正规式,则必然存在一个NFA M,使得L(M) = L(R)。
2. 对于任意一个NFA M,一定存在一个DFA M’与其等价,即L(M) = L(M’)。
NFA --> DFA
状态集合I的ε_闭包
设I是FA M的状态子集,则以下状态属于ε_CLOSURE(I):
1. 若si ∈ I,则si ∈ ε_CLOSURE(I)
2. 若si ∈ I,则对从si出发经过任意条ε通路所能到达的状态sj,都有sj ∈ ε_CLOSURE(I) 。
定义Ia = ε_CLOSURE(J),其中:
I = {s1, s2, …, sn}
J = f(I, a) = f(s1, a) ∪ f(s2, a) ∪ … ∪ f(sn, a)
如上图,我们可以得到:
1. I={1}, ε_CLOSURE(I) = {1, 2}
2. I={5}, ε_CLOSURE(I) = {5, 6,2}
更深入的,I={1, 2},可以得到:
J = f(I, a) = f({1, 2}, a) = ε_CLOSURE(5, 3, 4) = {2, 3, 4, 5, 6, 7, 8}
转换后的矩阵为:
状态 \ 输入符号 | Ia | Ib |
0 | 1 | 2 |
1 | 1 | 3 |
2 | 1 | 2 |
3 | 1 | 4 |
4 | 1 | 2 |
DFA --> 最简DFA
转换方式如下:
1. 首先将DFA的状态集按照终态与非终态分为两个子集,形成初始划分H。
2. 对每个子集G进行变换:
a) 把G划分为新的子集,使得G的两个状态s1和s2属于同一子集,当且仅当对任何输入符号a,状态s1和s2的后继状态都属于同一子集。
b) 用G划分出的所有子集替换G,形成新的划分H'
3. 如果H' == H 执行4,否则令H = H',重复执行。
4. 划分结束后,一个子集只对应一个状态,作为代表状态,删去其它一切等价状态,并将对应的弧射向这个代表状态。
1. 初始集合划分为,集合A = {0, 1, 2,},集合B = {3, 4}。
2. 由于1a,2b落在了集合B中,因此集合A需要继续划分,为{0}{1}{2}。
3. 检查集合B,由于3a,3b,4a,4b都落在了本身集合B中,因此不进行划分。
4. 最终划分结果为{0}{1}{2}{3, 4},重命名为0/1/2/3。
5. 得到新的最近DFA。
至此,关于 NFA 和 DFA 的相关知识点,总结完毕!
Leave a Reply