上下文无关文法

组成

可以看作一个四元组

1. $T$是终结符号(Terminal)集合，对应于词法分析器产生的词法单元；
2. $N$ 是非终结符号 (Non-terminal) 集合；
   • 非终结符号可以再次展开，而终结符号不行
3. $P$ 是产生式 (Production) 集合；
   • $A\in N\to \alpha \in (T\cup N{)}^{\ast }$
   • 头部/左部 (Head) $A$: 单个非终结符
   • 体部/右部 (Body) $\alpha$: 终结符与非终结符构成的串，也可以是空串 $ϵ$
4. $S$为开始(Start)符号。要求$S\in N$ 且唯一。

三个图灵奖得主，BNF范式（左边两位），右边那位扩展了BNF,变成了[E]BNF

语义

一个上下文无关文法$G$定义了一个语言$L(G)$

推导

将某个产生式的左边替换为它的右边，每一步推导需要选择替换哪一个非终结符号，以及使用哪一个产生式

一般只考虑两种情况：即每次选择最左边的和最右边的

句型

如果$S\to \alpha$且$alpha\in (T\cup N{)}^{\ast }$，那么称$\text{slpha}$是文法$G$的一个句型

句子

如果$S\to w$且$w\in T^{\ast }$，那么$w$是$G$的一个句子，句子是一种特殊的句型

文法生成的语言

文法$G$的语言$L(G)$就是它能推导的所有句子的集合

$$w\in L(G)⟺S\stackrel{\ast }{\Rightarrow }w$$

文法基本问题

Membership问题

Membership问题：给定字符串$x\in T^{\ast }$，$x\in L(G)$吗？

todo

$L(G)$究竟是什么

设计语言是，设计者需要很清楚的知道自己设计的是啥

给定文法，找出语言是什么

给定语言，那么文法是什么

回文串语言

Question

字母表$\Sigma =\{a,b\}$上的所有回文串构成的语言

带数量关系的语言

Question

带任意的语言

Question

ab组成的串中ab个数相同

Question

ab组成的串中ab个数不相同

表达能力

Chomsky Hierarchy：一种分类语言文法的层次结构

正则表达式的表达能力严格弱于上下文无关文法

证明

需要证明两点：

• 有上下文无关文法能表达的语言，但是正则表达式无法表达
• 任意正则都能用上下文无关表达

证明正则都能用上下文无关表达

用上下文无关文法来模拟NFA

证明有上下文无关无法用正则表达

如何证明这个不能用正则表达？反证法

如果能用正则表达式描述，那么就能用DFA描述。

设有一个有限状态自动机$D(r)$：$L(D(r))=L$，状态数为$k$

考虑输入$m>k$时，有k个状态但是却有m步，自动机一定会出现相同的状态。 那么如果$a^i{b}^i$能被接受，就存在一个错误的$a^j{b}^j$也能被接受，因此是错误的。

这个定理叫做Pumping Lemma，中文叫汞定理

此外，这个定理还能证明某个语言无法被上下文无关文法表达，不如说下面这个