什麼是上下文相關文法？

上下文相關文法 (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+ 瀏覽

開啟您的 事業

完成課程後獲得認證

開始