“计算理论基础”学习笔记
三月 18, 2020
有穷自动机
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\)