形式语言复习二

形式语言复习二

# 形式定义

• 文法
  • $G=(V,T,P,S)$
    • V—— 为变量的非空有穷集。$\forall A\in V,A$ 叫做一个语法变量，简称为变量，也可以叫做非终极符号
    • T—— 为终极符的非空有穷集。$\forall a\in T,a$ 叫做终极符。$V\cap T=\phi$
    • P—— 为产生式的非空有穷集合。P 中的元素均具有形式$\alpha\rightarrow\beta$，被称为产生式，读作：$\alpha$ 定义$\beta$。其中$\alpha\in(V\cup T)^+$，且$\alpha$ 中至少有$V$ 中一个元素的出现，$\beta\in(V\cup T)^*$
    • S——$S\in V$，为文法$G$ 的开始符号

对一组有相同左部的产生式

$\alpha\rightarrow\beta_1,\alpha\rightarrow\beta_2,...,\alpha\rightarrow\beta_n$

可以简单记为：

$\alpha\rightarrow\beta_1\vert\beta_2\vert...\vert\beta_n$

读作：$\alpha$ 定义为$\beta_1,$ 或者$\beta_2,...$，或者$\beta_n$。并且称它们为$\alpha$ 产生式。$\beta_1,\beta_2,...,\beta_n$ 称为候选式

• 推导：
  • 设$G=(V,T,P,S)$ 是一个文法，如果$\alpha\rightarrow\beta\in P,\gamma,\delta\in(V\cup T)^*$，则称$\gamma\alpha\delta$ 在$G$ 中直接推导出$\gamma\beta\delta$。
  • $\gamma\alpha\delta\Rightarrow_G\gamma\beta\delta$
  • 读作：$\gamma\alpha\delta$ 在文法$G$ 中直接推导出$\gamma\beta\delta$。
  • 直接推导可以简称推导，也称推导为派生
• 归约：
  • $\gamma\alpha\delta\Rightarrow_G\gamma\beta\delta$
  • 称$\gamma\beta\delta$ 在文法$G$ 中直接规约称$\gamma\alpha\delta$。在不特别强调归约的直接性时，“直接归约” 可以简称为归约
• $\Rightarrow_G,\Rightarrow_G^+,\Rightarrow_G^*$ 当成$(V\cup T)^*$ 上的二元关系
  • $\alpha\Rightarrow_G^n\beta$: 表示$\alpha$ 在$G$ 中经过 n 步推导出$\beta$；$\beta$ 在$G$ 中经过 n 步归约成$\alpha$。
  • 当 n=0 时，有$\alpha=\beta$。即$\alpha\Rightarrow_G^0\alpha$。
  • $\alpha\Rightarrow_G^+\beta$：表示$\alpha$ 在$G$ 中经过至少一步推导出$\beta$；$\beta$ 在$G$ 中经过至少 1 步归约成$\alpha$。
  • $\alpha\Rightarrow_G^*\beta$：表示$\alpha$ 在$G$ 中经过若干步推导出$\beta$；$\beta$ 在$G$ 中经过若干步归约成$\alpha$
  • 分别用$\Rightarrow,\Rightarrow^+,\Rightarrow^*,\Rightarrow^n$ 代替$\Rightarrow_G,\Rightarrow_G^+,\Rightarrow_G^*,\Rightarrow_G^n$
• 语言
  • $L(G)={\{}w\vert w\in T^*,S\Rightarrow^* w{\}}$
• 句子
  • $\forall x\in L(G),w$ 称为$G$ 的一个句子
  • 句子$w$ 是从$S$ 开始，在$G$ 中可以推导出来的终极符号行，它不含语法变量
• 句型
  • $G=(V,T,P,S)$，对于$\forall \alpha\in(V\cup T)^*$，如果$S\Rightarrow^*\alpha$，则称$\alpha$ 是$G$ 产生的一个句型
  • 句型$\alpha$ 是从$S$ 开始，在$G$ 中可以推导出来的符号行，它可能含语法变量

# 文法的构造

• 等价
  • 设有两个文法$G_1$ 和$G_2$，如果$L(G_1)=L(G_2)$，则称$G_1$ 和$G_2$ 等价
• 文法$G=(V,T,P,S)$ 约定
  • 一个文法的所有产生式中包含的符号，就是文法中所有可能有用的终极符号和非终极符号
  • 所列的第一个产生式的左部就是该文法的开始符号

# 文法的乔姆斯基体系

• 文法$G=(V,T,P,S)$

  • 短语结构文法（PSG）：

    • $G$ 叫做 0 型文法，也叫做短语结构文法

    • $L(G)$ 叫做 0 型语言。也可以叫做短语结构语言（PSL）、递归可枚举集

  • 上下文相关文法（CSG）：

    • $G$ 是 0 型文法

    • 如果对于$\forall \alpha\rightarrow\beta\in P$，均有$\vert\beta\vert\ge\vert\alpha\vert$ 成立，则称$G$ 为 1 型文法，或上下文相关文法

    • $L(G)$ 叫做 1 型语言或上下文相关语言（CSL）

  • 上下文无关文法（CFG）：

    • $G$ 是 1 型文法
    • 如果对于$\forall\alpha\rightarrow\beta\in P$，均有$\vert\beta\vert\ge\vert\alpha\vert$，并且$\alpha\in V$ 成立，则称$G$ 为 2 型文法，或上下文无关文法
    • $L(G)$ 称为 2 型语言或上下文无关语言（CFL）

  • 正则文法（RG）：

    • $G$ 是 2 型文法
    • 如果对于$\forall\alpha\rightarrow\beta\in P,\alpha\rightarrow\beta$ 均具有形式$A\rightarrow w,A\rightarrow wB$，其中$A,B\in V,w\in T^+$，则称$G$ 为 3 型文法，也可称正则文法或正规文法
    • $L(G)$ 叫做 3 型语言，也可称为正则语言或者正规语言（RL）

• 文法分类

  • $G$ 是短语结构文法
  • 如果所有产生式都有右边部分长度大于左边部分，那么$G$ 是上下文有关文法
  • 如果所有产生式的左边部分都是单个非终极符号，那么$G$ 是上下文无关文法
  • 如果所有产生式的右边部分都是以终极符号开始，且含有至多一个非终极符号（如果有非终极符号则出现在最右边），那么$G$ 是正则文法
  • 如果一个文法$G$ 是$RG$，则它也是$CFG,CSG$ 和短语结构文法，反之不一定成立
  • 如果一个文法$G$ 是$CFG$，则它也是$CSG$ 和短语结构文法，反之不一定成立
  • 如果一个文法$G$ 是$CSG$，则它也是短语结构文法，反之不一定成立
  • $RL$ 也是$CFL,CSL$ 和短语结构语言。反之不一定成立
  • $CFL$ 也是$CSL$ 和短语结构语言。反之不一定成立
  • $CSL$ 是短语结构语言。反之不一定成立
  • 当文法$G$ 是$CFG$ 时，$L(G)$ 却可以是$RL$
  • 当文法$G$ 是$CSG$ 时，$L(G)$ 可以是$RL,CFL$
  • 当文法$G$ 是短语结构文法时，$L(G)$ 可以是$RL,CFL,CSL$

• 定理：$L$ 是$RL$ 的充要条件是存在一个文法，该文法产生语言$L$，并且它的产生形式要么是形如：$A\rightarrow a$ 的产生式，要么是形如$A\rightarrow aB$ 的产生式。其中$A,B$ 为语法变量，$a$ 为终极符号

  • 证明：

    • 充分性：设有$G^\prime,L(G^\prime)=L$，且$G^\prime$ 的产生式的形式满足定理要求。这种文法就是$RG$。所以，$G^\prime$ 产生的语言就是$RL$, 故$L$ 就是$RL$

    • 必要性：

      • 构造：用产生式组：$A\rightarrow a_1A_1,A_1\rightarrow a_2A_2,...,A_{n-1}\rightarrow a_n$ 代替产生式$A\rightarrow a_1a_2...a_n$

      • 用产生式组$A\rightarrow a_1A_1,A_1\rightarrow a_2A_2,...,A_{n-1}\rightarrow a_nB$ 代替产生式$A\rightarrow a_1a_2...a_nB$

      • 证明$L(G^\prime)=L(G)$

        对于$\forall A\in V,A\Rightarrow_G^+ x\Leftrightarrow A\Rightarrow_{G^\prime}^+x$，因为$S\in V$，所以结论自然对$S$ 成立

• 线性文法：

  • 设$G=(V,T,P,S)$，如果对于$\forall\alpha\rightarrow\beta\in P,\alpha\rightarrow\beta$ 均具有如下形式：$A\rightarrow w,A\rightarrow wBx$，其中$A,B\in V,w,x\in T^*$，则称$G$ 为线性文法
  • 线性语言
    • $L(G)$ 叫做线性语言

• 右线性文法：

  • 设$G=(V,T,P,S)$，如果对于$\forall\alpha\rightarrow\beta\in P,\alpha\rightarrow\beta$ 均具有如下形式：$A\rightarrow w,A\rightarrow wB$，其中$A,B\in V,w,x\in T^*$，则称$G$ 为线性文法
  • 右线性语言
    • $L(G)$ 叫做右线性语言

• 左线性文法

  • 设$G=(V,T,P,S)$，如果对于$\forall\alpha\rightarrow\beta\in P,\alpha\rightarrow\beta$ 均具有如下形式：$A\rightarrow w,A\rightarrow Bw$，其中$A,B\in V,w,x\in T^*$，则称$G$ 为线性文法
  • 左线性语言
    • $L(G)$ 叫做左线性语言

• 定理：$L$ 是一个左线性语言的充要条件是存在文法$G$，$G$ 中的产生式要么是形如：$A\rightarrow a$ 的产生式，要么是形如$A\rightarrow Ba$ 的产生式，使得$L(G)=L$。其中$A,B$ 为语法变量，$a$ 为终级符号

• 定理：左线性文法和右线性文法等价

  • 对任意右线性文法$G$，我们能构造出对应的左线性文法$G^\prime$，使得$L(G^\prime)=L(G)$；
  • 对任意左线性文法$G$，我们能构造出对应的右线性文法$G^\prime$，使得$L(G^\prime)=L(G)$

• 定理：左线性文法的产生式与右线性文法的产生式混合所得到的文法不是$RG$

  • 证明：设有文法$G_{15}:S\rightarrow0A,A\rightarrow S1\vert1$
  • 不难看出，$L(G_{15})={\{}0^n1^n\vert n\ge1{\}}$。我们构造不出$RG\ G$，使得$L(G)=L(G_{15})={\{}0^n1^n\vert n\ge1{\}}$
  • 因为$L(G_{15})$ 不是$RL$。所以$G_{15}$ 不是$RG$。

# 空语句

• 形如$A\rightarrow\epsilon$ 的产生式叫做空产生式，也可以叫做$\epsilon$ 产生式

• 规定空语句不影响文法的类型

• 定理：

  • 加入空语句不影响语言的类型
  • 去掉空语句不影响语言的类型