什么是上下文相关文法？

上下文相关文法 (CSG) 定义为 G=(V,Σ,P,S)

其中，

• V: 非终结符或变量。
• Σ: 输入符号。
• P: 生成规则。
• P:{αAβ → αγβ, A ϵ V,α ϵ (V∪Σ)*, β ϵ (V∪Σ)*
• S: 起始符号。

示例

• aS→SAa|aA
• aA→abc

在上下文相关文法中，变量中要么存在左上下文环境，要么存在右上下文环境 (αAβ，即 α 是左上下文环境，β 是右上下文环境)。

但在上下文无关文法 (CFG) 中不存在上下文环境。

例如在生成规则中

S →0 B S 2 ，

B 0 → 0 B

在我们获得 B0 之前，无法替换 B。

因此，CSG 比 CFG 更难理解。

CFG、CSG 和无限制文法如下所示 −

Bhanu Priya

更新于：15-Jun-2021

8K+ 浏览

开启您的 事业

完成课程后获得认证

开始