上下文无关语言

定义

Definition

$G=(V,T,P,S)$ 是一个 CFG，则 $G$ 的语言 $L(G)$ 指能从初始符号推导出所有终结符串的集合。 如果一个语言 $L$ 是某个上下文无关文法的语言，则称 $L$ 为上下文无关语言。

上下文无关语言的证明

证明某个语言是某个文法的语言

• $w\in L\Rightarrow w\in L(G)$：归纳于 $|w|$
• $w\in L(G)\Rightarrow w\in L$：归纳于推导的步数

Example

$$P\to 0P0|1P1|0|1|ϵ$$

证明 $L(G)$ 是 $\left\{0,1\right\}$ 上的回文串的集合

---

• $\forall w\in {\left\{0,1\right\}}^{\ast },w\in L(G)\Rightarrow w^R=w$：
  • 基础：$0,1,ϵ\in L(G)$，且显然为回文
  • 归纳：若所有 $n$ 步内推导出的串 $x$ 均为回文串，考虑任意能通过 $n+1$ 步推导出的串 $w$，有两种情况。若第一步推导使用了规则 $P\to 0P0$，有 $P\Rightarrow 0P0\Rightarrow 0x0\Rightarrow w$，故 $w$ 为回文串，同理，若第一步推导使用了规则 $P\to 1P1$，$w$ 为回文串
• $\forall w\in {\left\{0,1\right\}}^{\ast },w^R=w\Rightarrow w\in L(G)$：
  • 基础：$|w|$ 为 0 或 1 时，$w$ 可能为 $0$, $1$, $ϵ$，显然有 $w\in L(G)$
  • 归纳：若 $\forall |x|\le n,x\in L(G)$，考虑 $|w|=n+1$ 的情况。若 $w$ 首尾都为 0，可以写成 $0x0$，则必然存在一个推导 $P\Rightarrow 0P0\stackrel{\ast }{\Rightarrow }0x0=w$，同理，若 $w$ 首尾都为 1，……

Example

$$S\to aS|aSb|ϵ$$

证明 $L(G)=\left\{a^m{b}^n|0\le n\le m\right\}$

---

• 先证明当 $w$ 具有该形式时一定有 $w\in L(G)$
  • 基础：$|w|=0$ 时，成立
  • 归纳：$|w|=k$ 时成立，考虑 $|w|=k+1$ 的情况。可以将 $w$ 写作 $ax$，由归纳假设，$S\stackrel{\ast }{\Rightarrow }x$，由 $S\to aS$，有 $S\Rightarrow aS\stackrel{\ast }{\Rightarrow }ax=w$
• 再证明 $w\in L(G)$ 时有 $w\in L$
  • 基础：$ϵ\in L$
  • 归纳：若所有 $n$ 步内推导出的串 $x$ 均有 $x\in L$，对于任意能通过 $n+1$ 步推导出的串 $w$，若第一步使用了 $S\to aS$，则 $w=ax$，有 $w\in L$，若第一步使用了 $S\to aSb$，则 $w=axb$，也有 $w\in L$