由有限语法规则集组成的上下文无关文法 (CFG) 是四元组(V, T, P, S)
在哪里，
V 是一个变量（非终结符）。
T 是一组终端。
P是一组规则，P：V→(V∪T)*，即产生式规则的左边。P 确实有任何右上下文或左上下文。
S 是起始符号。
通过使用任何语言的规则，我们可以导出该语言中的任何字符串。
对于语言 a* CFG 如下 -
S -> aS
S -> ɛ
这里，
S 是变量。
a 和 ɛ 终端。
S 是起始符号。
通过使用这些规则，我们可以推导出任意数量的 a。
例如，将字符串 aaaaa 视为 CFG，如下所示 -
S aS rule 1 aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaɛ rule 2 aaaaa
上下文无关语言是由上下文无关语法创建的，它包括常规语言。
多个上下文无关文法可以生成相同的上下文无关语言。
示例 1
不规则但上下文无关的语言示例是{ anbn | n >= 0 }
上面的例子是所有具有相同数量 a 和 b 的字符串，并且符号 a3b3 可以扩展为 aaabbb，其中有三个 a 和三个 b。
抽引引理提供了执行否定测试的能力。如果语言不满足泵引理，那么可以说它不是上下文无关的。Pumping lemma 是数学证明，需要时间将其应用于上下文无关语言。
示例 2
考虑另一个不规则的上下文无关示例。
S -> aSb | ɛ
这个例子不是正则的，因为我们不能用有限状态机或正则表达式来表达它。我们应该能够计算 A 的数量并检查 B 的匹配数量。此外，它不能用有限状态来完成，因为 n 可以是任何东西。