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

def（正则表达式）：

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

ϵ 是正则表达式;

∀a ∈ Σ, a 是正则表达式;

如果 r 是正则表达式, 则 (r) 是正则表达式;

如果 r 与 s 是正则表达式, 则 r|s, rs, r∗ 也是正则表达式。

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

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

L(ϵ) = {ϵ}

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

L((r)) = L(r)

两大要素：

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

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

字母表 Σ (ϵ !∈ Σ)

有穷的状态集合 S

唯一的初始状态 s0 ∈ S

状态转移函数 δ

δ : S × (Σ ∪ {ϵ}) → 2S

接受状态集合 F ⊆ S

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

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

关于自动机的两个问题：

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

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

字母表 Σ (ϵ !∈ Σ)

有穷的状态集合 S

唯一的初始状态 s0 ∈ S

状态转移函数 δ

δ : S × Σ → S

接受状态集合 F ⊆ S

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

NFA vs DFA

回顾一下正则表达式的递归定义：def（正则表达式）：

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

Tompson构造法就是从这四条规则出发，定义了四个基本状态

ϵ 是正则表达式

a ∈ Σ 是正则表达式

如果 s 是正则表达式, 则 (s) 是正则表达式

没什么好说的

如果 s, t 是正则表达式, 则 s|t 是正则表达式

如果 s, t 是正则表达式, 则 st 是正则表达式

如果 r, s 是正则表达式, 则r∗ 也是正则表达式

思想：用DFA模拟NFA

构造出的DFA，只要包含的NFA状态中有NFA接受状态，则该DFA状态为DFA接受状态

NFA如2.3

DFA最小化算法的基本思想：等价的状态可以合并

最小化的直接想法就是，如果状态等价，就将其合并

问题在于：如何定义等价状态？

尝试1：

这个定义是错误的，有时过于紧，有时过于松，反例如下：

A ∼ C ∼ E 但是, 接受状态与非接受状态必定不等价

尝试2：

√

这个定义是递归的，该从何下手？

——反其道而行之，划分，而非合并！

纸上得来终觉浅，绝知此事要躬行，我们直接从一个例子入手：

注：这里的操作顺序不唯一

因为接受状态和非接受状态必定不等价，定义Π0 = {F, S \ F}

因此，合并AC

思想上类似于floyed-warshell算法

Q的初始化：

∅ (注意: 它不是正则表达式) 的规定

init

step0

step1

step2