# 上下文无关文法

# 定义

上下文无关文法 (context-free grammar, CFG) 是一个 4 元组$(V,\varSigma,R,S)$ 且：

1. $V$ 是一个有穷集合，称为变元集 (variables)
2. $\varSigma$ 是一个与$V$ 不相交的有穷集合，称为终结符集 (terminals)
3. $R$ 是一个有穷规则集 (rules)，每条规则由一个变元和一个由变元和终结符组成的字符串构成
4. $S \in V$ 是起始变元

# 下推自动机