首页 形式语言

形式语言复习五

# RL 的泵引理

# 泵引理

  • 设 L 为 RL，则存在仅依赖与 L 的正整数 N，对于∀z∈L\forall z\in L，如果∣z∣≥N\vert z\vert\ge N，则存在u,v,wu,v,w 满足
    • z=uvw;z=uvw;
    • ∣uv∣≤N\vert uv\vert\le N
    • ∣v∣≥1;\vert v\vert\ge1;
    • 对于任意的整数i≥0,uviw∈L;i\ge 0,uv^iw\in L;
    • N 不大于接受 L 的最小 DFA M 的状态数

RL 的泵引理

  • 用来证明一个语言不是 RL，不能用泵引理证明一个语言是 RL
    • 由于泵引理给出的是 RL 的必要条件，所以，在用它证明一个语言不是 RL 时，使用反证法
    • 泵引理中提到的仅依赖与 L 的正整数不用给出具体的数值，只需用符号 N 来表示即可
    • z 的选择是关键，在保证∣z∣≥N\vert z\vert\ge N 的前提上，使得根据∣uv∣≤N,u,v,w\vert uv\vert\le N,u,v,w 的取值很容易得出
    • 当一个特意被选来用作 "发现矛盾" 的 z 确定后，就必须依照∣uv∣≤N,∣v∣≥1\vert uv\vert\le N,\vert v\vert\ge1 的要求，说明 v 不存在
    • 与选 z 时类似，在寻找 i 时，我们也仅需要找到一个表明矛盾的具体的值

例：证明{0n1n∣n≥1}{\{}0^n1^n\vert n\ge 1{\}} 不是 RL

证明：假设 L={0n1n∣n≥1}{\{}0^n1^n\vert n\ge 1{\}} 是 RL，z=0n1nz=0^n1^n

按照泵引理所述，v=0k,k≥1v=0^k,k\ge1，此时有u=0N−k−j,w=0j1Nu=0^{N-k-j},w=0^j1^N

从而有uviw=0N−k−j(0k)i0j1N=0N+(i−1)k1Nuv^iw=0^{N-k-j}(0^k)^i0^j1^N=0^{N+(i-1)k}1^N

当i=2i=2 时，有uv2w=0N+(2−1)k1N=0N+k1Nuv^2w=0^{N+(2-1)k}1^N=0^{N+k}1^N

注意到k≥1k\ge1，所以N+k>NN+k>N

即0N+K1N∉L0^{N+K}1^N\notin L，与泵引理矛盾，所以 L 不是 RL

# RL 的封闭性

  • 封闭性

    如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的

  • 有效封闭性

    给定一个语言的若干个语言的描述，如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称语言类对相应的运算是有效封闭的

定理：RL 在并，乘积，闭包运算下是封闭的

定理：RL 在补运算下式封闭的

定理：RL 在交运算下封闭

正则代换：

  • 设Σ,Δ\Sigma,\Delta 是两个字母表，映射f:Σ→2Δf:\Sigma\rightarrow2^\Delta 被称为是从Σ\Sigma 到Δ\Delta 的代换，如果对于∀a∈Σ,f(a)\forall a\in\Sigma,f(a) 是Δ\Delta 上的 RL，则称ff 为正则代换

  • ff 是正则代换，则：

    • f(ϕ)=ϕf(\phi)=\phi
    • f(ϵ)=ϵf(\epsilon)=\epsilon
    • 对于∀a∈Σ,f(a)\forall a\in\Sigma,f(a) 是Δ\Delta 上的 RE
    • 如果 r,s 是Σ\Sigma 上的 RE，则f(r+s)=f(r)+f(s),f(rs)=f(r)f(s),f(r∗)=f(r)∗f(r+s)=f(r)+f(s),f(rs)=f(r)f(s),f(r^*)=f(r)^* 是Δ\Delta 上的 RE

定理：设 L 是Σ\Sigma 上的一个 RL f:Σ→2Δf:\Sigma\rightarrow2^\Delta 是正则代换，则f(L)f(L) 也是 RL

同态映射：

  • 设Σ,Δ\Sigma,\Delta 是两个字母表f:Σ→Δ∗f:\Sigma\rightarrow\Delta^*，ff 为映射，如果对于∀x,y∈Σ∗,f(xy)=f(x)f(y)\forall x,y\in\Sigma^*,f(xy)=f(x)f(y) 则称 f 为Σ\Sigma 到Δ∗\Delta^* 的同态映射

  • 对于∀L⊆Σ∗,L\forall L\subseteq\Sigma^*,L 的同态像f(L)=⋃x∈Lf(x)f(L)=\bigcup\limits_{x\in L}f(x)

  • 对于∀w⊆Δ∗,w\forall w\subseteq\Delta^*,w 的同态原像是一个集合f−1(w)={x∣f(x)=w,x∈Σ∗}f^{-1}(w)={\{}x\vert f(x)=w,x\in\Sigma^*{\}}

  • 对于∀L⊆Δ∗,L\forall L\subseteq\Delta^*,L 的同态原像是一个集合f−1(L)=f^{-1}(L)={x∣f(x)∈Lx\vert f(x)\in L}

推论：RL 的同态像是 RL

定理：RL 的同态原像是 RL

商：

  • 设L1,L2⊆Σ∗,L2L_1,L_2\subseteq\Sigma^*,L_2 除以L1L_1 的商定义为：L1/L2=L_1/L_2={x∣∃y∈L2,xy∈L1x\vert\exists y\in L_2,xy\in L_1}。
  • 计算语言的商主要是考虑句子的后缀。只有当L1L_1 句子的后缀在L2L_2 中时，其相应的前缀才属于L1/L2L_1/L_2。所以，当ϵ∈L2\epsilon\in L_2 时，L1⊆L1/L2L_1\subseteq L_1/L_2

定理：L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^*，如果L1L_1 是 RL，则L1/L2L_1/L_2 也是 RL

# Myhill-Nerode 定理与 DFA 的极小化

# Myhill-Nerode 定理

  • DFA M 确定的等价关系RMR_M:

    • 对于M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)，∀x,y∈Σ∗,xRMy⇔δ(q0,x)=δ(q0,y)\forall x,y\in\Sigma^*,xR_My\Leftrightarrow\delta(q_0,x)=\delta(q_0,y)
    • xRMy⇔∃q∈Q,x,y∈set(q)xR_My\Leftrightarrow\exists q\in Q,x,y\in set(q)

  • L 确定的Σ∗\Sigma^* 上的关系RLR_L:

    对于∀x,y∈Σ∗,xRLy⇔\forall x,y\in\Sigma^*,xR_Ly\Leftrightarrow (对∀z∈Σ∗,xz∈L⇔zy∈L\forall z\in\Sigma^*,xz\in L\Leftrightarrow zy\in L)

    对于∀x,y∈Σ∗\forall x,y\in\Sigma^*，如果xRLyxR_Ly，则 x 和 y 无论接Σ∗\Sigma^* 中的任何串 z，xz 和 yz 要么都是 L 中的句子，要么都不是 L 的句子

  • 关系RMR_M:

    设DFAM=(Q,Σ,δ,q0,F)DFA\ M=(Q,\Sigma,\delta,q_0,F)，M 所确定的Σ∗\Sigma^* 上的关系RMR_M 定义为：对于∀x,y∈Σ∗\forall x,y\in\Sigma^*

    • xRMy⇔δ(q0,x)=δ(q0,y)xR_My\Leftrightarrow\delta(q_0,x)=\delta(q_0,y)
    • 即xRMy⇔∃q∈Q,x,y∈set(q)xR_My\Leftrightarrow\exists q\in Q,x,y\in set(q)
    • 或者：M 从q0q_0 开始读入 x 和 y 以后进入同一个状态

  • 关系RLR_L:

    设L⊆Σ∗,LL\subseteq\Sigma^*,L 确定的Σ∗\Sigma^* 上的关系RLR_L 定义为：对于∀x,y∈Σ∗\forall x,y\in\Sigma^*

    • xRLy⇔xR_Ly\Leftrightarrow (对∀z∈Σ∗,xz∈L⇔yz∈L\forall z\in\Sigma^*,xz\in L\Leftrightarrow yz\in L)

  • 对于RLR_L:

    • 如果xRMyxR_My，则必有xRL(M)yxR_{L(M)}y，可以证明
    • 如果xRL(M)yxR_{L(M)}y，则不一定有xRMyxR_My

  • 右不变的等价关系

    设 R 是Σ∗\Sigma^* 上的等价关系，对于∀x,y∈Σ∗\forall x,y\in\Sigma^*，如果xRyxRy，对于∀z∈Σ∗,\forall z\in\Sigma^*, 则必有xzRyzxzRyz 成立，则称 R 是右不变的等价关系

命题：对于任意DFAM=(Q,Σ,δ,q0,F)DFA\ M=(Q,\Sigma,\delta,q_0,F)，M 所确定的Σ∗\Sigma^* 上的关系RMR_M 为右不变的等价关系

命题：对于任意L⊆Σ∗,LL\subseteq\Sigma^*,L 所确定的Σ∗\Sigma^* 上的关系RLR_L 为右不变的等价关系

  • 指数：

    • 设 R 是Σ∗\Sigma^* 上的等价关系，则称∣Σ∗/R∣\vert\Sigma^*/R\vert 是 R 关于Σ∗\Sigma^* 的指数。简称 R 的指数
    • 简称Σ∗\Sigma^* 的关于 R 的一个等价类，也就是Σ∗/R\Sigma^*/R 的任意一个元素，为 R 的一个等价类

  • RMR_M 是RL(M)R_{L(M)} 的加细

    • ∀x,y∈Σ∗\forall x,y\in\Sigma^*，如果xRMyxR_My，必有xRL(M)yxR_{L(M)}y 成立，即对于任意DFAM=(Q,Σ,δ,q0,F)DFA\ M=(Q,\Sigma,\delta,q_0,F),∣Σ∗/RL(M)∣≤∣Σ∗/RM∣≤∣Q∣\vert\Sigma^*/R_{L(M)}\vert\le\vert\Sigma^*/R_M\vert\le\vert Q\vert
    • 按照RMR_M 中被分在同一等价类的串，在按照RL(M)R_{L(M)} 分类时，一定会被分在同一个等价类
    • RMR_M 对Σ∗\Sigma^* 的划分比RL(M)R_{L(M)} 对Σ∗\Sigma^* 的划分更细，成RMR_M 是RL(M)R_{L(M)} 的加细

# DFA 的极小化

  • 判断哪些状态不能合并

    • 终止状态和非终止状态不能合并
    • 如果两个状态读入同一个字符所进入的状态不能合并，那么这两个状态不能合并

  • 可区分：设DFAM=(Q,Σ,δ,q0,F)DFA\ M=(Q,\Sigma,\delta,q_0,F)，如果∃x∈Σ∗\exists x\in\Sigma^*，使得 Q 中的两个状态 q 和 p,δ(q,x)∈F\delta(q,x)\in F 和δ(p,x)∈F\delta(p,x)\in F 中有且仅有一个成立，则称 q 和 p 是可以区分的；否则称 q 和 p 等价，记作q≡pq\equiv p

  • 算法：DFA 极小化算法

    • 算法思想：扫描所有的状态对，找出所有的可区分的状态时，不可区分的状态一定是等价的

    • 输入：给定的 DFA

    • 输出：可区分状态表

    • 主要数据结构：状态对关联表；可区分状态链

    • 主要步骤：

      • for∀(q,p)∈F×(Q−F)dofor\ \forall(q,p)\in F\times(Q-F)\ do

        标记可区分状态表中的表项 (q,p)；

      • for∀(q,p)∈F×F∪(Q−F)×(Q−F),q≠pdofor\ \forall(q,p)\in F\times F\cup(Q-F)\times(Q-F),q\neq p\ do

      • ​ if∃a∈Σif\ \exists a\in\Sigma，可区分状态表中的表项 (δ(q,a),δ(p,a)\delta(q,a),\delta(p,a)) 已经被标记 thenthen

      • ​ beginbegin

      • ​ 标记可区分状态表中表中的表项 (q,p);

      • ​ 递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项

      • ​ endend

      • ​ elsefor∀a∈Σ,doelse\ for\forall a\in\Sigma,do

      • ​ ifδ(q,a)≠δ(q,a)if\ \delta(q,a)\neq\delta(q,a),(q,p)(q,p) 与(δ(q,a),δ(p,a))(\delta(q,a),\delta(p,a)) 不是同一个状态对 thenthen

      • ​ 将 (q,p) 放在(δ(q,a),δ(p,a))(\delta(q,a),\delta(p,a)) 的关联链表上