有穷自动机

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 > +\)

正则表达式的化简

• \(R+RS*=RS*\)
• \(R+S*R=S*R\)

正则表达式构造 \(varepsilon-\) DFA ，详见编译原理部分。

正则文法

• \(G=(V,T,P,S)\)
  • 如果只有 \(A\rightarrow xB,A\rightarrow x\) ，其中 \(A,B\in V,x\in T\) ，则称为右线性文法
  • 如果只有 \(A\rightarrow Bx,A\rightarrow x\) ，其中 \(A,B\in V,x\in T\) ，则称为左线性文法
  • 左线性文法与右线性文法的总和就是正则文法

Pumping Lemma

泵引理：如果 \(L\) 是一个正则语言，有一个整数 \(n\in \mathbb{N} \) ，对于任意的 \(w\in L (|w| \ge n)\) ，可以将 \(|w|\) 分成三部分，令 \(w=xyz\) 满足：

• \(|y| > 0\)
• \(|xy|\le n\)
• \(\forall k\ge 0 ,x y^kz\in L\)