基础

DFA

确定的有限自动机DFA M是一个五元组$M =(S，\sum，δ ，S_0 ，F )$

(1) S 是一个非空有限集，它的每个元素称为一个状态。

(2) $\sum$ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表。

(3) δ是状态转换函数，是在$S×\sum→S$上的单值映射。

(4) $s0, s0 ∈S$，是唯一的一个初态。

(5) $F, F\subseteq S$，可空,是一个终态集,终态也称可接受状态或结束状态。

NFA

定义 一个NFA M是五元式$M=(S,\sum,δ,S_0,F)$

$S$ 有穷非空状态集合

$\sum$ 有穷的输入字母表集合

δ 从$S\subseteq∑^→2S$映射$S_0\subseteq S$ 是S的非空子集，称为初始状态集合F  S 是S的子集(可空),称为终止状态集合NFA和DFA的不同在于δ的值域是S的子集，δ：S Σ →2S开始状态有不止一个接受ε作为输入符号

正规式转DFA

  • 1(0|1)*101

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
        flowchart LR
            A(A)--1-->B
            B--$-->E
            E--0-->E
            E--1-->E
            E--$-->D
            D--1-->F
            F--0-->G
            G--1-->H((G))
        
        

    - 1(1010\*|1(010)\*1)*0

    	```mermaid
    	flowchart LR
    		A(A)--1-->B
    		B--$-->C
    		C--$-->D

NFA确定化—子集法

对给定的NFA N构造一张表，表的构成如下：

（1）设$∑={ a1,…, ak }$，表的每行含有$k+1$列。

（2）置首行首列为$ε-closure(S_0)$。

（3）若某行首列状态子集已确定,记为I，则置该行 的第i+1列为$I_{ai}(i=1, …, k)$。

（4）检查该行所有状态子集，将未出现在第一列者 填入到后面空行的第一列。

（5）重复(3)(4)直到第一列中状态子集不再扩大为止(在第$i+1$列上的所有状态子集均已 在第一列上出现)。 此时，将该表看成是一个状态转换矩阵。

（6）将该状态转换矩阵中所有状态子集重新命名， 得到状态转换矩阵，其所示的是与 给定的NFA N 等价的DFA M（未化简的DFA）。