计算机理论基础

有限自动机

确定的/非确定的有限自动机，带/不带 ε 转移的非确定有限自动机以及各自之间的等价性。

  • 有限自动机（Finite State Automation） ：状态 是将事物区分开的一种标识，状态 + 输入 → 状态转移。
    • 具有 离散 输入（输出，不必须）系统的一种数学模型，特殊情况下也可无输入；
    • 有限的状态；
    • 根据每次转换的后继状态数量可区分为 确定的 有限自动机（DFA，后继状态唯一）和 不确定的 有限自动机（NFA，后继状态有多个）。

确定的有限自动机

  • 形式定义：DFA 是一个五元组，M = (Q, T, δ, q0, F)：
    • Q：有限的状态集合
    • T：有限的输入字母表
    • δ：转换函数，映射 Q × T → Q
    • q0：初始状态，q0 ∈ Q
    • F：终止状态集，F ⊆ Q
  • 输入一个字符串时，对转换函数 δ 扩展：δ' = Q × T* → Q，对任何 q ∈ Q，定义：
    • q'(q, ε) = q ：没有读到字符时，有限自动机状态不变
    • 对 a ∈ T 和 ω ∈ T*，有 δ'(q, ωa) = δ(δ'(q, ω), a)
  • 被 DFA 接收的字符串 ω 满足：δ(q0, ω) = p, p ∈ F，即 输入结束后能够使 DFA 状态到达终态 。
  • 格局 ：FSA 在某个时刻的工作状态可以用 (q, ω) 表明，其中 ω 为待输入字符串，q 为当前状态。
    • 初始格局：(q0, ω)
    • 终止格局：(q, ε), q ∈ F
    • 当 δ(q, a) 含有 q1，则用格局形式写为 (q, aω) |--- (q1, ω)，其中 ω ∈ T*，符号 |--- 表示从一个格局变换为另一个格局。

不确定的有限自动机

  • 形式定义：NFA 是一个五元组，M = (Q, T, δ, q0, F)，与 DFA 仅 δ 不同，NFA 的 δ 的映射范围为 Q × T → 2^Q，即 NFA 在某个状态下读入一个字符时，可转换的后继状态是 Q 的一个子集。
  • 输入字符串时对 δ 扩展：
    • 对 ε ∈ T*，有 `δ’(q, ε) = {q}’；
    • 对任意 a ∈ T, ω ∈ T*，有 `δ’(q, ωa) = {p | 对 δ’(q, ω) 中的某个状态 r，且 p 在 δ(r, a) 内}；
    • δ(P, ω) = ∪ δ(q, ω), q ∈ P, P ⊆ Q。
  • NFA 接受的语言为 `L(M) = {ω | δ(q0, ω) 含 F 中的一个状态}。

DFA 和 NFA 的等价性

  • DFA 是 NFA 的特例，NFA 必然能够接受 DFA 能接受的语言。
  • 从 NFA 构造等价的 DFA（子集构造法）：
    • 设 L 为某个 NFA，N = (QN, T, δN, q0, FN)，定义等价的 DFA 为 M = (QD, T, δD, {q0}, FD)；
    • 定义的 DFA 中，QD = {S | S ⊆ QN} = 2^Q，对 S ∈ QD 和 a ∈ T，有 δD(S, a) = ∪ δN(q, a), q ∈ S；
    • FD = {S | S ⊆ QN ∩ S ∩ FN ≠ ∅} （只要有一个在 F 中就可视为终止状态）；
    • 构造过程从 q0 开始，仅当某些状态已加入可达状态时，才加入 DFA 中。最坏情况下由 NFA 构造的 DFA 状态数目为 2^|QN|。

带 ε 转移的不确定的有限自动机

  • 有 ε 转换的 NFA 与无 ε 转换的 NFA 区别仅在于转换函数 δ 的不同，有 ε 转移的 NFA 在输入空串 ε（无输入）时也会引起状态转移，即 δ 是从 Q × (T ∪ {ε}) → 2^Q。
  • ε-闭包（closure）：
    • 状态 q 的 ε-闭包记为 ε-CLOSURE 或 ECLOSURE，定义为从 q 仅通过 ε 路径可以到达的状态（包括 q 自身）；
    • 状态子集 I 的 ε-闭包：ε-CLOSURE(I) = ∪ ε-CLOSURE(q), q ∈ I；
    • Ia：对状态子集 I ⊆ Q，任意 a ∈ T，Ia = ε-CLOSURE(P), P = δ(I, a)，即 P 是从 I 中状态经过一条标 a 的边可以到达的状态集合。
  • 扩展定义 δ’：Q × T* → 2^Q，对任何 q ∈ Q，有：
    • δ'(q, ε) = ε-CLOSURE(q)
    • δ'(q, ωa) = ε-CLOSURE(P), P = {p | 对某些 r ∈ δ'(q, ω) 且 p ∈ δ(r, a)}
  • δ(q, a) ≠ δ’(q, a)，因为 δ(q, a) 仅表示由 q 出发，仅沿着 一条 标 a 的路径能到达的状态，而 δ’(q, a) 表示经过标 a 或 ε 的路径得到状态集合的 ε-闭包，即 δ'(q, ωa) = ε-CLOSURE(δ( δ'(q, ω), a ))。

有 ε 转换的 NFA 和无 ε 转换的 NFA 等价

  • ε-NFA 是无 ε 转移的 NFA 的一般情况。设 M = (Q, T, δ, q0, F) 是一个 ε-NFA，可构造一个等价的无 ε 的 NFA：M1 = (Q, T, S1, q0, F1)
    • 对任何 a ∈ T，δ1(q, a) = δ'(q, a)；
    • 若 ε-CLORSURE(q0) ∩ F ≠ ∅，则 F1 = F ∪ {q0}，否则 F1 = F。
  • 构造方法：先确定 F，之后按照 δ1(q, a) = δ'(q, a) 来确定生成式集合。

专栏目录：计算机理论基础
此专栏的上一篇文章：形式语言
此专栏的下一篇文章：右线性语言

参考资料：《形式语言与自动机》，王柏、杨娟编著，北京邮电大学出版社

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/03/18/formal-languages-and-automata2/) 、作者信息（Forec）和本声明。

分享到