计算理论：有限自动机

course notes › theory of computation

Finite Automata

Finite automata is a formal system with only a finite amount of information

  • Information represented by its state
  • State changes in response to inputs
  • Rules that tell how the state changes in response to inputs are called transitions

Acceptance：对一个输入的序列（input string），从起始状态开始按照 transition 的规则转换状态，该输入被接受 所有输入被读入后 FA 停留在终止状态

Language of an Automata: The set of strings accepted by an automata is the language of , denoted

不同的终止状态集合会带来不同的 language

Deterministic Finite Automata

Definition

A DFA is represented formally by a 5-tuple, ，consisting of

  • a finite set of states
  • a finite set of input symbols
  • a transition function
  • an initial state
  • a set of states distinguished as final states，

transition function takes two arguments: a state and an input symbol

更为严谨的定义需要 transition function 为 total function，即对任意一组状态和输入，其输出都是有定义的。但一般情况下遇到输出未定义的情况，可认为 DFA 停机

DFA 也可以以图的形式表示

  • 节点=状态
  • 边=transition function
  • 无源边 start 指向初始状态
  • 接收状态用 double circles 表示

或者以 transition table 的形式表示

  • 行为状态
  • 列为输入
  • 起始状态用箭头标注
  • 接收状态用 * 标注

Extend transition function: 接受一个 state 和一个 string 作为输入，递归定义如下

Basis.

Induction.

Language of DFA

各种各样的 Automata 都定义语言，对于 DFA ，其定义的语言的形式化定义如下

Regular language: a language is regular if it is the language accepted by some DFA

A Nonregular Language:

Proof.

使用反证法，假设存在一个 DFA 接受该语言，该 DFA 有 个状态。考虑字符串

则必然存在从起始状态到接收状态的路径

考虑前 次 transition，有 个 state，根据 PHP，必然有一个状态至少出现两次，假设其为 ，则 ，路径变为

则该 DFA 同样可接受 ，矛盾

Q.E.D.

Nondeterministic Finite Automata

Nondeterminism

NFA 的 transition 结果可以是一个状态的集合

An NFA is represented formally by a 5-tuple, ，consisting of

  • a finite set of states
  • a finite set of input symbols
  • a transition function
  • an initial state
  • a set of states distinguished as final states,

对于 NFA ， 的输出是一个状态的集合。其 Extended 的递归定义如下

Basis.

Induction.

对于 NFA ，其定义的语言如下

即只要存在一条运行路径结束于接收状态即可认为接受该 string

NFA with -transitions

允许状态间根据 转换的 NFA

定义 Closure of states:

  • = set of states you can reach from state following only arcs labeled
    • Basis.
    • Induction. 如果 且有一条从 到 的边标号为 ，则

在 -NFA 上可定义扩展的转换函数

Basis.

Induction.

-NFA 定义的 language 即为

Equivalence of DFA, NFA

DFA to NFA

A DFA can be turned into an NFA that accepts the same language:

If , let the NFA have

NFA to DFA: subset construction

从 NFA 构造 DFA 可使用 subset construction

对于 NFA ，目标是构造一个 DFA 满足

的开始状态为一个集合，其中唯一的元素是 的开始状态，且由于两者接受相同的语言，故 与 的 alphabet 相同，其余部分的构造如下

  • 是 的 power set，如果 那么 ，但实践中一般很多状态都是不可达的，可达状态的数量大约和 在同一数量级

  • 是满足 的 的集合

  • 的定义如下，对于任意

Critical Point: DFA 的状态为 NFA 状态的集合

证明其正确性只需证明对字符串 ，有

Proof.

对 的长度归纳即可

Basis.

Induction. 令 ，根据 I.H. 有

令

根据 NFA transition function 的定义，有

而根据上述证明的构造有

同样的，根据 DFA transition function 的定义，有

则

故

得证

Q.E.D.

由上述双向的等价可得

被一个 DFA 接受 被一个 NFA 接受

Equivalence of DFA, -NFA

DFA to -NFA

Obviously, every DFA is an -NFA

-NFA to DFA

可从一个 -NFA 构造一个接受同样语言的 DFA: remove -transitions

对于一个 -NFA ，目标是构造一个 DFA 使得

Proof.

与 接受相同语言，有相同的 alphabet，其余部分的构造为

  • 是 的 power set，且任意 满足 ，换言之， 是一个 -closed set

  • 是满足 的 的集合

  • 的定义为，对于任意

证明其正确性只需证明对任意字符串 满足

根据 的长度归纳证明即可

Q.E.D.