自动机理论
自动机是机器的抽象模型, 通过移动一系列状态或配置来对输入执行计算. 在计算的每个状态, 转换函数基于当前配置的有限部分确定下一配置. 因此, 一旦计算达到接受配置, 它就接受该输入.
自动机可分为四类:
有限状态机 (Finite-State Machine, FSM)
下推自动机(Pushdown automata, PDA)
线性有界自动机(Linear-Bound automata, LBA)
图灵机(Turing machine)
形式语言
乔姆斯基把语言定义为:按照一定规律构成的句子和符号串的有限或无限的集合.
这种定义是宽泛而无实义的, 所以我们有下面这个定义:
语言
文法
每一种自动机都对应于一种形式语言.
- 对应于有限状态机的是正则语言(Regular Language)
- 对应于下推自动机的是上下文无关语言(Context-Free Canguage)
- 对应于线性有界自动机的被称为上下文相关语言(Context Sensitive Language)
- 对应于图灵机的则是递归可枚举语言(Recursively Enumerable)
有限自动机
一个有限自动机(Finite Automaton)是指一个能被有限个状态的计算形式.
定义:
确定有限自动机(Deterministic Finite Automaton, DFA)
是指
非确定有限自动机(Non-deterministic Finite Automaton,
NFA) 是指
任何 NFA 都可以转化为一个对应的 DFA.
定义
即状态集合
通过迭代算法可计算出
; ; if
, , jump to step 2, else goto step 4; return
.
令
易知:
. 若
, 则有 且一般没有 .
然后定义
为状态集合
进一步, 定义
为
对于两个状态集合
为新的 DFA 内的状态转移集合.
对于状态集合
为新的 DFA 的输出函数.
子集构造算法:
, , , ; , ; let
be a start of , ; ; ; ; ; pop
, ; ?goto #3:goto #9; ?goto #2:goto #10; return
.
显然,
事实上, DFA 和 NFA 根本的区别就在于 DFA 不接受
Hopcroft 算法可以将 DFA 转化为等价的、状态数量更少的 DFA.
首先定义
为状态集合
同时定义
为
定义等价类之间的状态转移为
定义等价类的输出为
于是有 Hopcroft 算法:
设
, , , , ; , ; ; forall
: pop from , forall : ; ; ; return
.
正则文法
有限自动机接受的是正则语言, 相应的文法则被称为正则文法.
称文法
; , ; , ; , .
其中,
易知
规则 2 叫做连接性(concatenation), 规则 3 叫做替换性(alternation), 规则 4 叫做 Kleene 闭包(Kleene clousre).
正则文法的代数性质:
结合律(associativity):
; 交换律(commutativity):
; 分配律(distribution):
; 幂等性(Idempotency):
.
Thompson 构造法 可以将正则表达式转化为等价的 NFA, 然后再用子集构造法转化为 DFA:
, returns: for
, returns: for
, returns: for
, returns: for
, return .
值得注意的是,两个构造之间的链接应当使用
正则泵引理(Pumping Lemma of Regular): 如果语言
; ; .
证明:
假设
则上述三个条件均被满足.
下推自动机
定义:
确定下推自动机(Deterministic Pushdown Automaton,
DPDA) 是指无冲突、无遗漏的下推自动机,即
非确定下推自动机(Non-deterministic Pushdown Automaton,
NPDA) 则允许状态无约束转移,即
值得注意的是,不是所有的 NPDA 都可以转化成 DPDA.
计算定义: 对任何的下推自动机
, 对 . 其中 ; , 使得 或 .
例子: PDA 识别
构造
; ; ; ; 被定义为: ; ; , ; , ; , ; ; 未被提及的
都有 .
被定义为: ; ; 其他
.
则
上下文无关文法
称文法
满足 使得 ; - 如果
, 总有 , 只要 , 就有 .
乔姆斯基范式(Chomsky Normal Form, CNF):如果文法
, where ; , where ; .
则
上下文无关泵引理(Pumping Lemma of Context-Free):
如果语言
; ; .
证明:
假设
令
则该路径上至少有两个不同的节点
有
线性有界自动机
定义:
LBA 的计算形式被定义为: 对任何的有界线性自动机
, 对 . 其中 ; 总有
或 , 且对后者要求 . 其中 是指 第 个字符被替换为 .
对于非确定的 LBA 还允许
例子: LBA 识别
构造
; ; ; , 从而 ; 被定义为: ; ; , ; , ; ; , ; ; ; , ; ; 对其他未被提及的三元组
都有 .
被定义为: ; ; 对其他状态
都有 .
则
对有界线性自动机
上下文相关文法
称文法
- 任何
中的规则都有形如 的形式.
其中
命题:文法
我们允许上下文相关的文法中含有空产生式,以保证上下文有关文法是上下文无关文法的真超集。 而任何一个不含有空产生式的上下问无关文法也会是上下文相关的。
Kuroda 范式: 文法中所有产生式都满足如下的一种形式:
; ; ; .
其中
所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。
递归可枚举
递归集合是指一个自然数集
如果
可数集合
递归可枚举集合对应的问题是半可判定问题, 递归集对应的是可判定问题.
图灵机的停机问题是半可判定的.