Introduction to the Theory of Computation

1Regular Languages

术语翻译

计算模型 • 英文 computational model

有限状态自动机 • 英文 finite state machine / finite automaton / finite automata

第一个例子的门是一个朝里开的单向门.

Figre 1.4 中接受状态是由创建者指定的.

术语翻译

状态图 • 英文 state diagram

起始状态 • 英文 start state

接受状态 • 英文 accept state

转移 • 英文 transition

定义 1.5 中的字母表有限组合成字符串, 被有限自动机检查.

定义 1.16 用较为数学的语言说, 就是 $w_{i}$ 依次作用在 $q_{0}$ 及其后继上, 最终位于可接受集中.

术语翻译

正则语言 • 英文 regular language

定义 1.23 中, Star 相当于 $A^{*} = k \geq 0 ⋃ A \circ \dots \circ A k$

定理 1.25,1.26 显然.

$ϵ$ 有点像单向等价关系.