Automation

• deterministic: 下一个状态是唯一确定的
• nondeterministic: 下一个状态可以不唯一确定
  • $\epsilon$移动，多种选择（含0种选择）产生不同备份
  • 无法移动时，该备份就消失
  • 有一个备份接受，整个计算就接受

$M$

$N_1$

计算树

非确定性自动机可以更简单的描述一个语言

筹码集（Tally Set）：一元字母表上的语言

$L(N_3)=\{0^k|k是2或3的倍数\}$

k个0的意思

NFA Definition

$N=(Q,\Sigma,\delta,q_0,F)$

• 有穷状态集
• 输入字母表
• 转移函数
• 初始状态
• 接受状态

NFA与DFA的等价性

等价：两台机器识别同样的语言

• 有穷自动机

NFA转DFA：一步一步走，然后删除不可达状态

定理：每台NFA都有等价DFA

一个语言是正则的，当且仅当有一台NFA识别他