《有限自动机》

形式语言与自动机理论 清华大学

形式语言与自动机 陈有

Introduction to Autometa Theory, languages and computation

<aside>

有限自动机：

1. 有限状态自动机 https://en.wikipedia.org/wiki/Finite-state_machine Finite state Automation FA

   1. 确定 Deterministic Finite state Automation DFA
   2. 非确定 Non-deterministic Finite state Automation NFA

   【等价性】FA ↔ FAL ↔ RL 正则语言是 有限状态自动机接受的语言。（L(DFA)\subset L(NFA)）

2. 下推自动机 https://en.wikipedia.org/wiki/Pushdown_automaton PDA

3. 图灵机https://en.wikipedia.org/wiki/Turing_machine TM </aside>

FA

$$ \operatorname{FA} = (Q_{\text{of status}},\Sigma,\delta,q_o,F),\\ q_0\in Q,\ F\subseteq Q,\ \delta:Q\times \Sigma\to Q $$

DFA

• 确定的有限状态机 deterministic finite state automation

  • 每种情况出度、入度为1

  • 陷阱状态，接受状态

    有向图DAG 有向边的个数就是状态转移函数 $\delta$ 的个数

  • delta 有限状态机的状态转移函数

    → 函数形式

    → 状态矩阵

    $\delta(q,a)=q^\prime$→ 状态图，状态q到状态q’有一条 有向边，并用字符$a\in\Sigma$标记

    开始状态$q_0$ 用两个圆圈包裹

    <aside>

    DFA 的状态转移函数 不定义以下默认式

    $$ \delta(q,\epsilon)=q $$

    应为字母表里没有 空串

    ---

    DFA 的扩展的 状态转移函数，定义扫描串后的状态变化，进而包括空串

    $$ \delta^(q,w)=q^\prime,w\in \Sigma^ $$

    显然这要求 扫描后到达 唯一 确定 的状态$q^\prime$

    扩展状态转移函数的个数不定，可人工选择使用那些

    </aside>

• DFA 的接受语言 FSL

  • DFA 的停机条件：扫描完串之后

  • 可接受串

    DFA 从开始状态开始，扫描串停机后，处于某个 接受状态，则该串被接受 ⇒ 有限状态语言 FSL = L(DFA)

    $$ L(DFA)=\{w\mid \delta^*(q_0,w)\in F\}\subsetneq L(RG) $$

  <aside>

  Trick

  基础句子→ 构造DAG

  </aside>

  给定语言，构造DFA 接受。

  <aside>

  • 每个FSL=L(DFA) 都是右线性语言RLG。

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

    A→w, A→B is RG, \delta(q,a)=q’ is DFA

    DFA的状态 对应 RLG的非终结符

    RLG 从左至右产生串

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

    $q_{n-1}\to End$

    陷阱状态对应文法中的无用终结符

  </aside>

• 格局

  DFA的瞬时描述$(q,y),q\in Q,y$为即将扫描串（有概率非法）

  DFA 的状态转移函数$\delta$的一次作用带来一个格局转换

  $$ q_0w=>q_f\epsilon,\\ q_f\in F $$

  DFA接受的语言 可以看作 能够被格局转化为接受状态的串的集合

  $$ FSL=L(DFA)=\{w\mid q_0w=>q_f\epsilon,q_f\in F,w\in \Sigma^*\} $$

  <aside>

  set 集合

  能够将DFA从开始状态q0 转化到指定状态q的字符串的集合

  $$ set(q)=\{w\mid w\in \Sigma^,\delta^(q_0,w)=q\} $$

  </aside>

  DFA接受的语言 同样可以定义为 所有接受状态set集合的并集

  $$ FSL=L(DFA)=\cup set(q_\alpha \in F) $$

  这是从等价类的角度考虑，将不同类定义为不同状态，从而构建DFA

• FSL 对对补运算封闭

  这里的补是相对语言的全集$\Sigma^*$ 来说的

  • $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$