上下文无关文法能够描述某些具有递归结构的特征。

上下文无关文法的应用：

• 研究人类语言。在名词、动词、介词以及他们的短语之间的关系中存在自然的递归。

• 程序设计语言的规范说明和编译。

3.1 上下文无关文法

例子,:

一个文法由一组替换规则产生，替换规则又叫做产生式。

格式：符号 箭头 字符串

符号：变元

字符串：变元+终结符组成

起始变元：通常第一条规则的左边

3.1.1 上下文无关文法的形式定义

定义3.1 上下文无关文法是一个4元组, 这里

1）v是一个有穷集合，称作变元集。

2. 是一个与V不相交的有穷集合，称作终结符集。

3. R是一个有穷的规则集，每一条规则是一个变元和一个有变元和终结符组成的字符串。

4. 是起始变元。

3.1.2上下文无关文法举例

考虑文法，其中规则集R为：

如果把a看作左括弧"("、b看作右括弧")"，可以看出是所有正常嵌套的括弧字符串构成的语言。

考虑文法，其中，，规则为：

$<FACTOR> \rightarrow (<EXPR>) | a$$

3.1.3 设计上下文无关文法

1 许多CFG是由几个比较简单的CFG合并成的。分成几部分，并且分别构造每一部分的文法。

部分：

加入新规则：

2 如果这个语言碰巧是正则的，可以先构造它的DFA，然后在构造它的CFG。转化方法：

对于DFA的每一个状态，设一个变元，如果是DFA中的一个转移函数，则把规则加入CFG；

如果是DFA的接受状态，则把规则加入CFG；

设是DFA的起始状态，则取作为CFG的起始变元。

3.1.4 歧义性

最左派生

当已知一个歧义文法，有时能找到一个产生相同语言的非歧义文法，但某些上下文无关语言只能用歧义文法产生，这样的语言称为固有歧义的。

3.1.5 乔姆斯基范式

定义3.5 一个上下文无关文法为乔姆斯基范式，如果他的每一个规则具有如下形式：

定理3.6 任何一个上下文无关语言都能用乔姆斯基范式的上下文无关文法产生。

3.2 下推自动机

3.2.1 下推自动机的形式定义

定义3.8 下推自动机是一个6元组，这里和F都是有穷集合，并且

1. Q是状态集。

2. 是输入字母表。

3. 是栈字母表。

4. (Q \times \Gamma_{\epsilon})$是转移函数。

5. 是起始状态。

6. 是接受状态集。

下推自动机在能力上与上下文无关文法等价.

非形式地描述这个语言的PDA如何工作：

读输入中的符号。每读一个0把0输入栈。一旦看见1之后，就每读一个1就把一个0弹出栈。如果栈中0被排空的时候恰好读完输入串，则接受这个输入。如果还有1没有读的时候栈变成空的；或者栈中还有0的时候1已经读完了；或者0出现在1的后面，则拒绝这个输入。

3.2.2 下推自动机机举例

3.2.3 与上下文无语言的等价性

定理3.12* 一个语言是上下文无关的，当且仅当存在一台下推自动机识别他。

正向：证明主要关注PDA的非确定性

反向：数学归纳法

3.3 非上下文无关语言

关于上下文无关语言的泵引理*

定理3.19 如果A是上下文无关语言，则存在数p（泵长度），使得A中任何一个长度不小于p的字符串s能够分成5段，s=uvxyz，满足下述条件

1. 对于每一个i，

2. 

3.