Nondeterministic Finite State Machines NFSM
What is NFSM?
For FSM, the current state and input symbol uniquely determines the next state. FSM But, the *Next state is uniquely given by the current state and the current input 当前状态 + 输入符号 → *可能有多个下一状态（甚至没有）
- 对于某个状态的相同输入，可能有相同的下一个状态
- $\varepsilon$-transition: 不需要读入也能进行跳转
对于 NFSM 只要有一条路径到达终态(accpet)，就接受
Formal Definition of NFSM
FSM is a 5-tuple $(S, \Sigma, f, s_0, Z)$ where:
- $S$: a finite states set（有限状态集）
- $\Sigma$: a finite alphabet table, input string $w=w_1w_2...w_n$, $w_i \in \Sigma$
- $f$: single value transition function, $f: S \times \Sigma \rightarrow S$（单值转移函数）
- $s_0 \in S$: initial state（初始状态）
- $Z \subseteq S$: the final states（终态集）
- The language recognized by M: $L(M) = \{x \mid f(s_0, x) \in Z\}$
注意：$f: S \times (\Sigma \cup {\varepsilon}) \rightarrow P(S)$ 相比于 FSM 这里不仅仅多了 $\varepsilon$-transition ，而且这里的 transition function 针对当前状态输入之后得到的是一个状态集合
Equivalence NFSM = FSM
Every NFSM has an equivalent DFSM
NFSM → DFSM: Subset Construction Algorithm
$\varepsilon$-closure(q) = 从状态 q 出发，只走 $\varepsilon$-transition（不消耗输入），能到达的所有状态（包括自己）
设原来的 NFSM 是 $N=(Q,\Sigma,\delta,q_0,Z)$。
转换成 DFSM 时：
1. 新状态
DFSM 的状态是 NFSM 状态集合的子集。 也就是 $Q' = P(Q)$。
2. 新起始状态
如果有 $\varepsilon$-transition，起始状态不是单纯 {q0}，而是：
$q_0' = E({q_0})$
其中 (E(\cdot)) 是 ε-closure，也就是从这些状态出发，只走 $\varepsilon$ 边，能到达的所有状态。课件也是这么写的。
3. 新转移
对 DFSM 的一个集合状态 R，读一个字符 a：
先看 NFSM 里从 (R) 中每个状态出发，经 (a) 能到哪里； 再把这些到达状态做 $\varepsilon$-closure。
也就是： $\delta'(R,a)=E(\delta(R,a))$
这正是课件给的公式。
4. 新终态
只要这个集合里包含原 NFSM 的某个终态，它就是 DFSM 的终态： $Z'={R\mid R\cap Z\neq \emptyset}$