编译原理：深入理解正则表达式与NFA、DFA状态机

正则表达式

1 基本概念

1.1 正则

正则表达式是语法，正则语言是语义

def（正则表达式）：

给定字母表 Σ, Σ 上的正则表达式由且仅由以下规则定义:

ϵ 是正则表达式;
∀a ∈ Σ, a 是正则表达式;
如果 r 是正则表达式, 则 (r) 是正则表达式;
如果 r 与 s 是正则表达式, 则 r|s, rs, r^∗ 也是正则表达式。

运算优先级: () ≻ ∗ ≻ 连接 ≻ |

def（正则表达式对应的语言）：

L(ϵ) = {ϵ}

L(a) = {a}, ∀a ∈ Σ

L((r)) = L(r)

L(r|s) = L(r)∪L(s)

L(rs) = L(r)L(s)

L(r^∗) = (L(r))^∗

1.2 自动机

两大要素：

状态集S
状态转移函数δ

1.3 NFA

Nondeteministic Finite Automaton，非确定自动状态机

A 是一个五元组 A = (Σ, S, s0, δ, F):

字母表 Σ (ϵ !∈ Σ)
有穷的状态集合 S
唯一的初始状态 s0 ∈ S
状态转移函数 δ

δ : S × (Σ ∪ {ϵ}) → 2^S
接受状态集合 F ⊆ S

A 定义了一种语言 L(A): 它能接受的所有字符串构成的集合

约定：所有没有对应出边的字符默认指向一个不存在的 “空状态” ∅

关于自动机的两个问题：

给定字符串x，x是否属于L(A)

L(A)究竟是什么

1.4 DFA

Deterministic Finite Automaton，确定性有穷自动机

A 是一个五元组 A = (Σ, S, s0, δ, F):

字母表 Σ (ϵ !∈ Σ)
有穷的状态集合 S
唯一的初始状态 s0 ∈ S
状态转移函数 δ

δ : S × Σ → S
接受状态集合 F ⊆ S

约定: 所有没有对应出边的字符默认指向一个不存在的 “死状态”

NFA vs DFA

对于字母表中的每个符号，DFA中的每个状态都有且只有一条关于这个符号的出边（exiting transition）。NFA则未必，在同一个状态上可能有零条、一条甚至多条关于某一个符号的出边。

DFA的转换箭头上的标签必须是字母表中的，但NFA可以有标识为ϵ的边，NFA的状态可能有零条、一条甚至多条ϵ边。