上下文敏感语法（CSG）和语言（CSL）

上下文敏感语法- 上下文敏感语法是一种不受限制的语法，其中所有的结果都是形式的—— 其中α和β是非端子和端子串。

上下文敏感语法是 更强大 因为有些语言可以用CSG描述，但不能用上下文无关语法描述，而且CSL的功能不如无限制语法。这就是为什么上下文敏感语法在乔姆斯基层次结构中位于上下文无关语法和非限制语法之间。

上下文敏感语法有4个元组。 G={N，∑，P，S} 哪里 N=非终端符号集 ∑=终端符号集 S=生产的开始符号 P=有限生产集 P中的所有规则都是α形式 _1. Aα _2. –> α _1. β α _2.

上下文敏感语言： 可由上下文相关语法定义的语言称为CSL。CSL的特性包括：

• 两种上下文敏感语言的并集、交集和连接是上下文敏感的。
• 上下文敏感语言的补语是上下文敏感的。

例如——

考虑下面的CSG。 s→ abc/aAbc Ab→ 文学士 交流电→ Bbcc bB→ Bb aB→ aa/aaA 这个语法生成了什么语言？

解决方案 : s→ aAbc → abAc → abbcc → abbcc → aaAbbcc → aabAbcc → aabbAcc → AABBCCC → AABBCCC → AABBCCC → AABBBCCC 该语法生成的语言是{ A. ^N B ^N C ^N |n≥1}.

盖特CS角问题

练习下列问题将有助于测试你的知识。所有问题都是在前几年的GATE或GATE模拟测试中提出的。强烈建议你练习。

1. 2005年CS门，问题55
2. CS门2004，问题87

参考资料- CSG–维基百科 CSG–csa。iisc。欧内斯特。在里面