有穷自动机

DFA

确定型有穷自动机(DFA) 是一个五元组 \(A=(Q,\sum , \delta ,q_0,F)\)

• \(Q\) 是有限状态的集合
• \(\sum\) 输入符号的集合（字母表）
• \(\delta\) 是 \(Q\) 和 \(\sum\) 的关系表
• \(q_o\in Q\) 是开始状态
• \(F\subseteq Q\) 是结束或者可接受的状态集合

DFA 的语言是这个 DFA 接受的所有的串所组成的集合 \(L(A)=w|\hat{\delta}(q_0,w)\in F\)

定义 \(\hat{\delta}\) 如下：

• \(\hat{\delta}(q,\varepsilon)=q\)
• \(\hat{\delta}(q,w)=\delta(\hat{\delta}(q,x),a)\)，\(w=xa\)

如果语言 \(L\) 可以用 DFA 表示，那么我们说语言 \(L\) 是一个正则语言。

NFA

非确定型有穷自动机(NFA) 具有同时处在几个状态的能力。

NFA 是一个五元组 \(A=(Q,\sum , \delta ,q_0,F)\)

• \(Q\) 是有限状态的集合
• \(\sum\) 输入符号的集合（字母表）
• \(\delta\) 是 \(Q\) 和 \(\sum\) 的关系表，与 DFA 的主要区别就在于，NFA 的 \(\delta\) 返回值是一个集合
• \(q_o\in Q\) 是开始状态
• \(F\subseteq Q\) 是结束或者可接受的状态集合

NFA 的语言 \(L(A)=w|\hat{\delta}(q_0,w)\cap F\neq \varnothing \)

同样的可以定义 \(\hat{\delta}\) ：

• \(\hat{\delta}(q,\varepsilon)=\{q\}\)
• \(\hat{\delta}(q,w)=\bigcup _{p\in \hat{\delta}(q,w)} \delta(p,a)\)，\(w=xa\)

如果语言 \(L\) 可以用 DFA 表示，那么我们说语言 \(L\) 是一个正则语言。

DFA 与 NFA

• NFA 更容易设计
• DFA 与 NFA 是等价的（即能互相表示）
• NFA 可以通过子集构造得到等价的 DFA
  • 子集构造会造成状态个数呈指数级别增长
• lazy 策略，去掉从初始结点无法到达的结点

正则表达式

三种连接方式（假设 \(E\) 是一个正则表达式）：

• \(\cdot\)：\(L(E\cdot F)=L(E)\cdot L(F)\)
• \(+\)：\(L(E+F)=L(E)\cup L(F)\)
• \(*\)：\(L(E*)=(L(E))*\)

运算优先级\(* > \cdot > +\)