“计算理论基础”学习笔记


有穷自动机

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

 

 

You may also like

LEAVE A COMMENT

Statistics

  • 1
  • 53,564

Categories

Archive

Comments