【计算理论】【《计算理论导引（原书第3版）》笔记】第一章：正则语言

文章目录

• • @[toc]
  • • 1.1|有穷自动机
    • • 有穷自动机的状态图
      • 有穷自动机的形式化定义
      • 有穷自动机计算的形式化定义
      • 正则语言
      • 正则运算
      • • 并
        • 连接（并置）
        • 星号
        • 定理
        • • 证明
        • 定理
    • 1.2|非确定性
    • • 确定型有穷自动机$DFA$
      • 非确定型有穷自动机$NFA$
      • • 示例
      • 非确定型有穷自动机的形式化定义
      • $NFA$计算的形式化定义
      • $NFA$与$DFA$的等价性
      • • 定理
        • • 证明
        • 定理
      • 在正则运算下的封闭性
      • • 正则语言类在并运算下封闭
        • • 构造
          • 证明
        • 正则语言类在连接运算下封闭
        • • 构造
          • 证明
        • 正则语言类在星号运算下封闭
        • • 构造
          • 证明

1.1|有穷自动机

有穷自动机的状态图

• 起始状态用一个指向它的无出发点的箭头表示
• 接受状态带有双圈
• 从一个状态指向另一个状态的箭头称为转移

有穷自动机的形式化定义

• 有穷自动机是一个$5$元组$(Q,\Sigma ,\delta ,q_0,F)$，其中

  • $Q$是一个有穷集合，称为状态集
  • $\Sigma$是一个有穷集合，称为字母表
  • $\delta :Q\times \Sigma \to Q$是转移函数
  • $q_0\in Q$是起始状态
  • $F\subseteq Q$是接受状态集

• 若$A$是机器$M$接受的全部字符串集，则称$A$是机器$M$的语言，记作$L(M)=A$，又称$M$识别$A$

• 如果机器不接受任何字符串，它仍然识别一个语言，即空语言$\varnothing$

有穷自动机计算的形式化定义

• 设$M=(Q,\Sigma ,\delta ,q_0,F)$是一台有穷自动机，$w=w_1{w}_2\cdots w_n$是一个字符串并且其中任一$w_i$是字母表$\Sigma$的成员，如果存在$Q$中的状态序列$r_0$，$r_1$，$\cdots$，$r_n$满足下述条件

  • $r_0=q_0$

  • $\delta (r_i,{\omega }_{i+1})=r_{i+1},i=0,\cdots ,n-1$

  • $r_n\in F$

• 则$M$接受$w$

正则语言

• 如果一个语言被一台有穷自动机识别，则称它是正则语言

正则运算

并

A ∪ B = {   x ∣ x ∈ A 或 x ∈ B   } A \cup B = \set{x \mid x \in A 或 x \in B} A∪B={ x∣x∈A或x∈B}

连接（并置）

A ∘ B = {   x y ∣ x ∈ A 且 y ∈ B   } A \circ B = \set{xy \mid x \in A 且 y \in B} A∘B={ xy∣x∈A且y∈B}

星号

A ∗ = {   x 1 x 2 ⋯ x k ∣ k ≥ 0 且每一个 x i ∈ A   } A^{*} = \set{x_{1} x_{2} \cdots x_{k} \mid k \geq 0 且每一个 x_{i} \in A} A∗={ x1​x2​⋯xk​∣k≥0且每一个xi​∈A}

定理

• 正则语言类在并运算下封闭，换言之，如果$A_1$和$A_2$是正则语言，则$A_1\cup A_2$也是正则语言

证明

• 设$M_1$识别$A_1$，$M_2$识别$A_2$，其中$M_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$，$M_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)$，构造识别$A_1\cup A_2$的$M$，这里$M=(Q,\Sigma ,\delta ,q_0,F)$

• Q = {   ( r 1 , r 2 ) ∣ r 1 ∈ Q 1 且 r 2 ∈ Q 2   } Q = \set{(r_{1} , r_{2}) \mid r_{1} \in Q_{1} 且 r_{2} \in Q_{2}} Q={ (r1​,r2​)∣r1​∈Q1​且r2​∈Q2​}

• 转移函数$\delta$定义如下：对每一对$(r_1,r_2)\in Q$和每一个$a\in \Sigma$，令$\delta ((r_1,r_2),a)=({\delta }_1(r_1,a),{\delta }_2(r_2,a))$

• $q_0$是有序对$(q_1,q_2)$

• $F$等于有一个元素是$M_1$或$M_2$的接受状态的有序对组成的集合 F = {   ( r 1 , r 2 ) ∣ r 1 ∈ F 1 或 r 2 ∈ F 2   } F = \set{(r_{1} , r_{2}) \mid r_{1} \in F_{1} 或 r_{2} \in F_{2}} F={ (r1​,r2​)∣r1​∈F1​或r2​∈F2​}或写成$F=(F_1\times Q_2)\cup (Q_1\times F_2)$

定理

• 正则语言类在连接运算下封闭，换言之，如果$A_1$和$A_2$是正则语言，则$A_1\circ A_2$也是正则语言
  • 有穷自动机$M$当它的输入可以被分成两段，$M_1$接受第一段且$M_2$接受第二段时，$M$才接受输入

1.2|非确定性

确定型有穷自动机$DFA$

• 每一个状态对于字母表中的每一个符号总是恰好有一个转移箭头射出

非确定型有穷自动机$NFA$

• 每一个状态对于字母表中的每一个符号可能有$0$个、$1$个或多个射出的箭头
• 如果计算分支中至少有一个结束在接受状态，则机器接受

示例

• 接受所有形如$0^k$的字符串的$NFA$，其中$k$是$2$或$3$的倍数

非确定型有穷自动机的形式化定义

• 对任意的字母表$\Sigma$，把 Σ ∪ {   ε   } \Sigma \cup \set{\varepsilon} Σ∪{ ε}记作${\Sigma }_{\epsilon }$
• 非确定型有穷自动机是一个$5$元组$(Q,\Sigma ,\delta ,q_0,F)$，其中
  • $Q$是有穷的状态集
  • $\Sigma$是有穷的字母表
  • $\delta :Q\times {\Sigma }_{\epsilon }\to \mathcal{P}(Q)$是转移函数
  • $q_0\in Q$是起始状态
  • $F\subseteq Q$是接受状态集

$NFA$计算的形式化定义

• 设$N=(Q,\Sigma ,\delta ,q_0,F)$是一台$NFA$，$w$是字母表$\Sigma$上的一个字符串，如果能把$w$写成$w=y_1{y}_2\cdots y_m$，这里每一个$y_i$是${\Sigma }_{\epsilon }$的一个成员，并且存在$Q$中的状态序列$r_0$，$r_1$，$\cdots$，$r_m$满足下述$3$个条件

  • $r_0=q_0$

  • $r_{i+1}\in \delta (r_i,y_{i+1}),i=0,1,\cdots ,m-1$

  • $r_m\in F$

• 则称$N$接受$w$

$NFA$与$DFA$的等价性

• 如果两台机器识别相同的语言，则称它们是等价的

定理

• 每一台非确定型有穷自动机都等价于某一台确定型有穷自动机

证明

• 设$N=(Q,\Sigma ,\delta ,q_0,F)$是识别语言$A$的$NFA$，构造一台识别语言$A$的$DFAM=(Q^{{}^{\prime }},\Sigma ,{\delta }^{{}^{\prime }},q_0^{{}^{\prime }},F^{{}^{\prime }})$

• 假设$N$没有$\epsilon$箭头

  • $Q^{{}^{\prime }}=\mathcal{P}(Q)$

  • 对于$R\in Q^{{}^{\prime }}$和$a\in \Sigma$，令 δ ′ ( R , a ) = {   q ∈ Q ∣ 存在 r ∈ R , 使得 q ∈ δ ( r , a )   } \delta^{'} (R , a) = \set{q \in Q \mid 存在 r \in R , 使得 q \in \delta(r , a)} δ′(R,a)={ q∈Q∣存在r∈R,使得q∈δ(r,a)}或写成${\delta }^{{}^{\prime }}(R,a)=\bigcup _{r\in R}\delta (r,a)$

  • q 0 ′ = {   q 0   } q_{0}^{'} = \set{q_{0}} q0′​={ q0​}

  • F ′ = {   R ∈ Q ′ ∣ R 包含 N 的一个接受状态   } F^{'} = \set{R \in Q^{'} \mid R 包含 N 的一个接受状态} F′={ R∈Q′∣R包含N的一个接受状态}

• 假设$N$有$\epsilon$箭头

  • 对于$M$的任意一个状态$R$，定义$E(R)$为从$R$的成员出发只沿着$\epsilon$箭头可以达到的状态集合，包括$R$本身的所有成员在内，对于$R\subseteq Q$， E ( R ) = {   q ∣ 从 R 出发沿着 0 个或者多个 ε 箭头可以达到 q   } E(R) = \set{q \mid 从 R 出发沿着 0 个或者多个 \varepsilon 箭头可以达到 q} E(R)={ q∣从R出发沿着0个或者多个ε箭头可以达到q}

  • δ ′ ( R , a ) = {   q ∈ Q ∣ 存在 r ∈ R , 使得 q ∈ E ( δ ( r , a ) )   } \delta^{'} (R , a) = \set{q \in Q \mid 存在 r \in R , 使得 q \in E(\delta(r , a))} δ′(R,a)={ q∈Q∣存在r∈R,使得q∈E(δ(r,a))}

  • q 0 ′ = E ( {   q 0   } ) q_{0}^{'} = E(\set{q_{0}}) q0′​=E({ q0​})

定理

• 一个语言是正则的，当且仅当有一台$NFA$识别它

在正则运算下的封闭性

正则语言类在并运算下封闭

构造

证明

• 设$N_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$识别$A_1$，并且$N_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)$识别$A_2$，构造识别$A_1\cup A_2$的$N=(Q,\Sigma ,\delta ,q_0,F)$

• Q = {   q 0   } ∪ Q 1 ∪ Q 2 Q = \set{q_{0}} \cup Q_{1} \cup Q_{2} Q={ q0​}∪Q1​∪Q2​

• 状态$q_0$是$N$的起始状态

• 接受状态$F=F_1\cup F_2$

• 定义$\delta$如下：对每一个$q\in Q$和每一个$a\in {\Sigma }_{\epsilon }$

δ ( q , a ) = { δ 1 ( q , a ) , q ∈ Q 1 δ 2 ( q , a ) , q ∈ Q 2 {   q 1 , q 2   } , q = q 0 且 a = ε ∅ , q = q 0 且 a ≠ ε \delta(q , a) = \begin{cases} \delta_{1} (q , a) , & q \in Q_{1} \\ \delta_{2} (q , a) , & q \in Q_{2} \\ \set{q_{1} , q_{2}} , & q = q_{0} 且 a = \varepsilon \\ \emptyset , & q = q_{0} 且 a \neq \varepsilon \end{cases} δ(q,a)=⎩ ⎨ ⎧​δ1​(q,a),δ2​(q,a),{ q1​,q2​},∅,​q∈Q1​q∈Q2​q=q0​且a=εq=q0​且a=ε​

正则语言类在连接运算下封闭

• $N_1$的每一个接受状态增加一个$\epsilon$箭头，使得只要$N_1$在一个接受状态，就允许$N$非确定性地分支进入$N_2$

构造

证明

• 设$N_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$识别$A_1$，并且$N_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)$识别$A_2$，构造识别$A_1\circ A_2$的$N=(Q,\Sigma ,\delta ,q_1,F_2)$

• $Q=Q_1\cup Q_2$

• $N$的起始状态是$N_1$的起始状态$q_1$

• $N$的接受状态集是$N_2$的接受状态集

• 定义$\delta$如下：对每一个$q\in Q$和每一个$a\in {\Sigma }_{\epsilon }$

δ ( q , a ) = { δ 1 ( q , a ) , q ∈ Q 1 且 q ∉ F 1 δ 1 ( q , a ) , q ∈ F 1 且 a ≠ ε δ 1 ( q , a ) ∪ {   q 2   } , q ∈ F 1 且 a = ε δ 2 ( q , a ) , q ∈ Q 2 \delta(q , a) = \begin{cases} \delta_{1} (q , a) , & q \in Q_{1} 且 q \notin F_{1} \\ \delta_{1} (q , a) , & q \in F_{1} 且 a \neq \varepsilon \\ \delta_{1} (q , a) \cup \set{q_{2}} , & q \in F_{1} 且 a = \varepsilon \\ \delta_{2} (q , a) , & q \in Q_{2} \end{cases} δ(q,a)=⎩ ⎨ ⎧​δ1​(q,a),δ1​(q,a),δ1​(q,a)∪{ q2​},δ2​(q,a),​q∈Q1​且q∈/F1​q∈F1​且a=εq∈F1​且a=εq∈Q2​​

正则语言类在星号运算下封闭

构造

证明

• 设$N_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$识别$A_1$，构造识别$A_1^{\ast }$的$N=(Q,\Sigma ,\delta ,q_0,F)$

• Q = {   q 0   } ∪ Q 1 Q = \set{q_{0}} \cup Q_{1} Q={ q0​}∪Q1​

• $q_0$是新的起始状态

• F = {   q 0   } ∪ F 1 F = \set{q_{0}} \cup F_{1} F={ q0​}∪F1​

• 定义$\delta$如下，对每一个$q\in Q$和每一个$a\in {\Sigma }_{\epsilon }$

δ ( q , a ) = { δ 1 ( q , a ) , q ∈ Q 1 且 q ∉ F 1 δ 1 ( q , a ) , q ∈ F 1 且 a ≠ ε δ 1 ( q , a ) ∪ {   q 1   } , q ∈ F 1 且 a = ε {   q 1   } , q = q 0 且 a = ε ∅ , q = q 0 且 a ≠ ε \delta (q , a) = \begin{cases} \delta_{1} (q , a) , & q \in Q_{1} 且 q \notin F_{1} \\ \delta_{1} (q , a) , & q \in F_{1} 且 a \neq \varepsilon \\ \delta_{1} (q , a) \cup \set{q_{1}} , & q \in F_{1} 且 a = \varepsilon \\ \set{q_{1}} , & q = q_{0} 且 a = \varepsilon \\ \emptyset , & q = q_{0} 且 a \neq \varepsilon \end{cases} δ(q,a)=⎩ ⎨ ⎧​δ1​(q,a),δ1​(q,a),δ1​(q,a)∪{ q1​},{ q1​},∅,​q∈Q1​且q∈/F1​q∈F1​且a=εq∈F1​且a=εq=q0​且a=εq=q0​且a=ε​