下巴斯-科德范式（Chomsky-Schützenberger范式）是形式语言理论中描述上下文无关文法的一种特殊形式。其核心特征是：所有产生式规则的右侧要么是单个终结符，要么恰好包含一个非终结符和一个终结符。这种形式由语言学家Chomsky和Schützenberger共同提出。
形式化定义
设文法$G = (V, \Sigma, P, S)$，其中：
- $V$是非终结符集合
- $\Sigma$是终结符集合
- $P$是产生式规则集合
- $S$是起始符号
在标准形式中，所有产生式满足以下形式之一： $$ A \to a $$ $$ A \to aB $$ 其中$A, B \in V$，$a \in \Sigma$。
示例
合法产生式： $$ S \to aT \ T \to b \ T \to cU $$ 非法产生式： $$ S \to ab \quad (\text{含两个终结符}) \ S \to TT \quad (\text{含两个非终结符}) $$
理论意义
这种范式具有以下重要特性：
- 表达能力等价于正则文法
- 可直接转换为有限状态自动机
- 在语法分析中具有线性时间复杂度
通过引入该范式，可以更清晰地揭示上下文无关文法与正则语言的内在联系。
