我觉得大学时候编译原理我学的还是挺明白的了,当最近因为工作需要用到编译原理这块的知识,好尴尬,全部不记得了!其实这个结果不出乎意料,因为学校的教育是教与背,学生们很少真正理解知识,也很难真正明白如何去应用,时间久了当然全部忘记。算了,不说了,搞的像个愤青。。。

痛定思痛,我决定静下心来再次学一遍、去真正理解,顺便结合需求使用场景,这个过程很美妙,而且保证未来这些知识点不再会轻易从脑海里流逝。


以考试为目的的学习,将会在考试结束开始忘记。

在此声明,本文记录了相关的知识点和举例,以帮我未来快速勾起回忆、梳理知识点,目的是未来需要时看上一眼我就全想起来了。本文不适合新手来读,因为里面没有深入讲解原理,也没有硬性的概念。如果你希望随时查看NFA和DFA的相关知识点,欢迎阅读本文,它可以帮助有相关知识背景的同学快速回顾。

FA——finite automata,有穷自动机,是描述机器特定类型算法的数学方法,有穷自动机可用作描述在输入串中识别模式的过程,因此可以被作为构造扫描程序。FA作为一种识别装置,它能准确地识别正规集。
DFA——deterministic finite automata,确定的有穷自动机。
NFA——nondeterministic finite automata,不确定的有穷自动机。

  • DFA
  • 一个确定的有穷自动机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
  • 一个不确定的有穷自动机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

    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}

    按照这一规则,我们可以将NFA转换成DFA。

    转换后的矩阵为:

    状态 \ 输入符号 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. 划分结束后,一个子集只对应一个状态,作为代表状态,删去其它一切等价状态,并将对应的弧射向这个代表状态。

    举个例子,如下图是一个DFA图:

    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 的相关知识点,总结完毕!