Context-Free Grammar and Languages
Review about Chomsky Hierarchy
o We have known the Chomsky category
o Previous parts we have learned: FSM, Regular expression
o Chomsky classified the grammar into 4 classes, every class is corresponding to one language
❑Type 0 grammar
❑Type 2 grammar
❑Type 1 grammar
❑Type 3 grammar
o Sets of types of formal grammars with increasing expressive power
Chomsky Hierarchy
o Type 2 (context-free grammar CFG): rules in G as A →β, A∈Vn , β∈V+
o Language defined by type 2: L2 or context-free language
o Pumping Lemma: accept or recognize this type of language
这段内容介绍了 乔姆斯基层次结构（Chomsky Hierarchy） 中的 类型 2 文法，也就是 上下文无关文法（CFG, Context-Free Grammar），以及该文法所定义的语言的特性和泵引理的应用。
乔姆斯基层次结构（Chomsky Hierarchy）：
乔姆斯基层次结构是一个用于分类形式语言的体系，分为四种类型：类型 0（不受约束的文法）、类型 1（上下文相关文法）、类型 2（上下文无关文法）和类型 3（正则文法）。类型 2 对应于 上下文无关文法（CFG），也是这一段讨论的重点。
类型 2（上下文无关文法，CFG）：
- 文法规则的形式：
- $A \to \beta$，其中 $A \in V_n$ 是一个 非终结符，而 $\beta \in V^+$ 是一个由终结符和非终结符组成的字符串。
- 这里的 $V_n$ 代表 非终结符的集合，而 $\beta$ 必须是一个非空字符串（$V^+$ 表示至少包含一个符号的字符串）。
- 这意味着在上下文无关文法中，左侧只能是一个 非终结符，而右侧可以是由 终结符和非终结符 组成的任意字符串。
- 语言定义：
- 类型 2 文法 定义了 上下文无关语言（Context-Free Language，CFL），记作 $L_2$。
- 这些语言可以被 上下文无关文法 生成，通常用于描述具有递归结构的语言，比如平衡括号、简单的算术表达式等。
泵引理（Pumping Lemma）：
- 泵引理用于上下文无关语言：
- 泵引理（Pumping Lemma） 也适用于 上下文无关语言，用于证明一个语言是否是上下文无关的。
- 通过使用泵引理，可以验证某些语言是否具有上下文无关语言的特性，即是否可以“泵出”某些子串而不改变语言的结构性。
- 泵引理对于上下文无关语言和正则语言的形式有所不同，但目的相同，都是用于证明某个语言不是特定类型的语言。
总结：
- 类型 2 文法（上下文无关文法，CFG）：
- 规则形式为 $A \to \beta$，其中 $A$ 是一个非终结符，$\beta$ 是非空字符串，由终结符和非终结符组成。
- 类型 2 文法可以生成 上下文无关语言（CFL），这些语言具有递归结构，能够描述像平衡括号和嵌套结构这样的语言。
- 泵引理：
- 泵引理 可以用于上下文无关语言，帮助判断某个语言是否具有上下文无关的特性。
上下文无关文法和上下文无关语言在编程语言解析、自然语言处理等领域有广泛的应用，尤其擅长处理具有递归或嵌套结构的语言。
Chomsky Hierarchy
o Type 3 (regular grammar RG): rules in G as
⮚A →aB or A →a, A、B∈Vn , a∈Vt
⮚A →Ba or A →a, A、B∈Vn , a∈Vt