DFA

确定的有限状态机 deterministic finite state automation
- 每种情况出度、入度为1
- 陷阱状态，接受状态
  
  有向图DAG 有向边的个数就是状态转移函数 $\delta$ 的个数
DFA 的接受语言
- 可接受串，
<aside>

Trick

基础句子→ 构造DAG

</aside>

给定语言，构造DFA 接受。
每个FSL=L(DFA) 都是右线性语言RLG。

已知 $DFA=(q,\Sigma,\delta,\epsilon_0,F)$，要求构造$G_{右}=(\Sigma,V,S,P)$

RLG 从左至右产生串

$q_i\to x_{i+1}q_{i+1}$

$q_{n-1}\to End$

陷阱状态对应文法中的无用终结符
FSL 对对补运算封闭
- $DFA_3=(Q,\Sigma,\delta,q_0,Q-F)$
- 接受状态为$Q$，接受语言为全集
- $Q-F$，接受语言为补集（接受状态与非接收状态对调）

NFA

<aside>

不确定的有限状态机

$$ \text{NFA} = (Q,\Sigma,\delta,Q_0,F) $$

$Q$ 是一个有限状态的集合，$Q_0\subset Q$ 是开始状态集合 $F\subset Q$是接受状态集合 $\delta:Q\times\Sigma\to 2^Q$

</aside>

$|\delta|=0$对DFA成立，允许指向空集的转移函数不定义。

任何一个DFA都可以看作一个NFA，其所有转移函数映射对应的所有子集元素数为1，即源转移函数值：

$$ \delta(q,a)=\{\delta_{\text{DFA}}(q,a)\} $$
NFA停机包括两种可能：
1. 输入串扫描结束
2. 对应$\delta$没有定义（DFA的陷阱状态）
对应 NFA 可能处于：接受状态终止→Yes、非接受状态终止→Retry another path、中途停止（中止）→Retry another path【注意用词区别】【存在至少一条路径可接受，则串$w$能被NFA接受】

NFA接受的串的集合→ NFA 接受的语言$L(\text{NFA})=\{\delta{w}=\text{accept}\}$
形式化定义语言
- DFA 扩展状态转移函数$\delta ^:Q\times \Sigma^\to Q$
- NFA 扩展状态转移函数 $\delta^:2^Q\times \Sigma^\to2^Q$
  - 递归定义
    
    1 初始状态集合 $\delta^*(P,\epsilon)=P$
    
    2 递归演进 $\delta^*(P,a)=\cup_{q\in P}\delta(q,a)$
    
    $\delta^(P,\alpha a)=\delta^(\delta^(P,\alpha),a)$集合先扫描$\alpha$获得可行状态集$\{q\}=\delta^(P,a)$，再接着演进
  $\delta^*(Q_0,w)\cap F\ne \empty:$
DFA→ NFA, NFA?→DFA

DFA的确定化

必要性：FSL⇒ $FSL=l(DFA)=L(NFA)$

充分性：NFA?→DFA 使得 $L(NFA)=L(DFA)$

$$ DFA^\prime=(Q^\prime,\Sigma,\delta^\prime,q_0^\prime,F^\prime) $$

要把集合当作一个复合（组合）状态 $Q^\prime =2^Q$

$$ \delta^\prime()=\cup\delta() $$

接受状态：包括原先接受状态的集合。