自动机理论

自动机是机器的抽象模型, 通过移动一系列状态或配置来对输入执行计算. 在计算的每个状态, 转换函数基于当前配置的有限部分确定下一配置. 因此, 一旦计算达到接受配置, 它就接受该输入.

自动机可分为四类:

  1. 有限状态机 (Finite-State Machine, FSM)

  2. 下推自动机(Pushdown automata, PDA)

  3. 线性有界自动机(Linear-Bound automata, LBA)

  4. 图灵机(Turing machine)

形式语言

乔姆斯基把语言定义为:按照一定规律构成的句子和符号串的有限或无限的集合.

这种定义是宽泛而无实义的, 所以我们有下面这个定义:

语言 是指机器 接受的所有的字符串构成的集合.

文法 则是由终结符集合 , 非终结符集合 , 产生式集合 以及开始状态 构成的描述机器所能接受的语言的形式的一种表达方式.

每一种自动机都对应于一种形式语言.

  1. 对应于有限状态机的是正则语言(Regular Language)
  2. 对应于下推自动机的是上下文无关语言(Context-Free Canguage)
  3. 对应于线性有界自动机的被称为上下文相关语言(Context Sensitive Language)
  4. 对应于图灵机的则是递归可枚举语言(Recursively Enumerable)

有限自动机

一个有限自动机(Finite Automaton)是指一个能被有限个状态的计算形式.

定义: 是一个有限自动机, 如果输入集 , 输出集 , 状态集 都非空, 且 的状态转移函数, 的输出函数也都不是空映射.

确定有限自动机(Deterministic Finite Automaton, DFA) 是指 都是映射, 即对同一个状态和输入有至多一个结果.

非确定有限自动机(Non-deterministic Finite Automaton, NFA) 是指 至少有一个是超映射, 即对同一个状态和输入有多个结果. 因此非确定有限自动机存在回溯问题.

任何 NFA 都可以转化为一个对应的 DFA.

定义 ( 闭包):

.

即状态集合 闭包是指从 中的状态出发仅通过 边即可到达的所有状态构成的集合.

通过迭代算法可计算出 :

  1. ;

  2. ;

  3. if , , jump to step 2, else goto step 4;

  4. return .

-闭包的简单记法.

易知:

  1. .

  2. , 则有 且一般没有 .

然后定义

为状态集合 通过边 得到的 DFA 状态集合.

进一步, 定义

的可达 DFA 邻域。

对于两个状态集合 之间的状态转移, 定义

为新的 DFA 内的状态转移集合.

对于状态集合 的输出函数, 定义

为新的 DFA 的输出函数.

子集构造算法:

  1. , , , ;

  2. , ;

  3. let be a start of , ;

  4. ;

  5. ;

  6. ;

  7. ;

  8. pop , ;

  9. ?goto #3:goto #9;

  10. ?goto #2:goto #10;

  11. return .

显然, 中的元素就是 中的元素的子集。该算法的理论复杂度最高即当 时,为 .

事实上, DFA 和 NFA 根本的区别就在于 DFA 不接受 作为输入, 而 NFA 可以接受 作为输入. 这也是为什么 NFA 的状态转移函数和输出函数是超映射.

Hopcroft 算法可以将 DFA 转化为等价的、状态数量更少的 DFA.

首先定义

为状态集合 中由 决定的 等价类, .

同时定义

决定的分割.

定义等价类之间的状态转移为

,

定义等价类的输出为

.

于是有 Hopcroft 算法:

, 则:

  1. , , , , ;

  2. , ;

  3. ;

  4. forall : pop from , forall : ;

  5. ;

  6. ;

  7. return .

正则文法

有限自动机接受的是正则语言, 相应的文法则被称为正则文法.

称文法 是一个正则文法, 如果满足:

  1. ;

  2. , ;

  3. , ;

  4. , .

其中, 满足 .

易知 具有唯一性.

规则 2 叫做连接性(concatenation), 规则 3 叫做替换性(alternation), 规则 4 叫做 Kleene 闭包(Kleene clousre).

正则文法的代数性质:

  1. 结合律(associativity): ;

  2. 交换律(commutativity): ;

  3. 分配律(distribution): ;

  4. 幂等性(Idempotency): .

Thompson 构造法 可以将正则表达式转化为等价的 NFA, 然后再用子集构造法转化为 DFA:

  1. , returns:

  2. for , returns:

  3. for , returns:

  4. for , returns:

  5. for , return .

值得注意的是,两个构造之间的链接应当使用 .

正则泵引理(Pumping Lemma of Regular): 如果语言 是正则语言,则存在数 使得 , , 且有

  1. ;

  2. ;

  3. .

证明:

假设 对应的 DFA 为 , 假设 的状态数, 选择 , 则从开始到 被接受至少经过了 个状态, 根据鸽巢原理,至少有两个状态是同一个状态,不妨记为 . 记 为第一次进入 状态的符号, 为最后一次进入 状态的符号, 则令

则上述三个条件均被满足.

下推自动机

定义: 为下推自动机(Pushdown automaton, PDA), 如果输入集合 , 输出集, 状态集合 都是有限集合, 堆栈序列集合 中的每个元素是有限长的(但 自身可以是无限集合), 且 都不为空映射.

确定下推自动机(Deterministic Pushdown Automaton, DPDA) 是指无冲突、无遗漏的下推自动机,即 是一个单射.

非确定下推自动机(Non-deterministic Pushdown Automaton, NPDA) 则允许状态无约束转移,即 可以是一个超映射.

值得注意的是,不是所有的 NPDA 都可以转化成 DPDA.

计算定义: 对任何的下推自动机 , 计算路径是一个状态序列 , . 该路径满足如下条件:

  1. , 对 . 其中 ;

  2. , 使得 .

例子: PDA 识别 .

构造:

  • ;

  • ;

  • ;

  • ;

  • 被定义为:

    • ;

    • ;

    • , ;

    • , ;

    • , ;

    • ;

    • 未被提及的 都有 .

  • 被定义为:

    • ;

    • ;

    • 其他 .

识别 .

上下文无关文法

称文法 是一个上下文无关文法(Context-free grammar, CFG),如果 满足:

  1. 满足 使得 ;
  2. 如果 , 总有 , 只要 , 就有 .

乔姆斯基范式(Chomsky Normal Form, CNF):如果文法 满足:

  1. , where ;
  2. , where ;
  3. .

是一个 CFG, 反之 如果一个文法可以表示为 CNF, 则该文法为 CFG.

上下文无关泵引理(Pumping Lemma of Context-Free): 如果语言 是上下文无关语言,则存在数 使得 , , 且有

  1. ;

  2. ;

  3. .

证明:

假设 是语言 对应的上下文无关文法,令 , 令 的最长的解析树高度, 则 .

, 则 , 于是有 .

则该路径上至少有两个不同的节点 标记了相同的非终结符 , 假设节点 处为 , 节点 处为 , 则 令

. 则, 同时, 假设 , 则 , 这是不可能的,因此 .

则显然.

线性有界自动机

定义: 为线性有界自动机(Linear-bounded automaton, LBA), 如果输入集合 , 输出集, 状态集合 都是有限集合, 存储序列集合 是一个依赖于输入的有限序列集合,其中的每个字符序列的长度有一个依赖于输入的公共上限 , 且 都不为空映射. 其中, .

LBA 的计算形式被定义为: 对任何的有界线性自动机 , 计算路径是一个状态序列 , . 该路径满足如下条件:

  1. , 对 . 其中 ;

  2. 总有 , 且对后者要求 . 其中 是指 个字符被替换为 .

对于非确定的 LBA 还允许 .

例子: LBA 识别 .

构造 :

  • ;

  • ;

  • ;

  • , 从而 ;

  • 被定义为:

    • ;

    • ;

    • , ;

    • , ;

    • ;

    • , ;

    • ;

    • ;

    • , ;

    • ;

    • 对其他未被提及的三元组 都有 .

  • 被定义为:

    • ;

    • ;

    • 对其他状态 都有 .

识别 .

对有界线性自动机 ,其对输入 可能的配置数为 .

上下文相关文法

称文法 是上下文相关文法(Context-sensitive grammar, CFG),如果满足:

  • 任何 中的规则都有形如 的形式.

其中 .

命题:文法 是上下文无关文法,当且仅当 中任何形如 的产生式,都有 .

我们允许上下文相关的文法中含有空产生式,以保证上下文有关文法是上下文无关文法的真超集。 而任何一个不含有空产生式的上下问无关文法也会是上下文相关的。

Kuroda 范式: 文法中所有产生式都满足如下的一种形式:

  1. ;

  2. ;

  3. ;

  4. .

其中 , 而 .

所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。

递归可枚举

递归集合是指一个自然数集 的子集 , 如果存在一个全可计算函数 , 使得

如果 是递归集合,则 的补集是递归集合。 如果 是递归集合,则 是递归集合。集合 是递归集合,当且仅当 的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像(preimage)是递归集合.

可数集合 被称为递归可枚举的, 如果有一个图灵机, 在给定 的一个元素作为输入的时候总是停机, 并在给定的输入不属于 的时候永不停机.

递归可枚举集合对应的问题是半可判定问题, 递归集对应的是可判定问题.

图灵机的停机问题是半可判定的.