查看“︁上下文有关文法”︁的源代码

[[分类:形式语言]]
{{InfoBox
|name=上下文有关语言
|eng_name=context-sensitive language
}}
{{InfoBox
|name=上下文有关文法
|eng_name=context-sensitive grammar
|aliases=CSG
}}
{{InfoBox
|name=1型语言
|eng_name=type-1 language
}}
{{InfoBox
|name=1型文法
|eng_name=type-1 grammar
}}
'''上下文有关文法'''('''context-sentitive grammar''', '''CSG''')指一种[[形式语言]]中该语言字母表上全部可能单词中，每个字母是否可以出现可能取决于上下文的其他字母。是一种[[生成文法]]，与 [[Chomsky 生成语法理论]]中的'''1 型文法'''('''type-1 grammar''')相同。上下文有关字面意义上地意味着这个语言中任何非终结符被重写为其他符号串时可能受到上下文的其他符号影响。

== 定义 ==

若生成文法中，全部文法均有形式：

<math>\alpha A \beta \rightarrow \alpha \gamma \beta</math>

其中， <math>\alpha,\beta</math> 为任意终结符和非终结符构成的序列， <math>\gamma</math> 为任意终结符和非终结符构成的非空序列， <math>A</math> 为一个非终结符，

则称该文法为一种'''上下文有关文法'''('''context-sensitive grammar''', '''CSG''')，由这种文法生成的语言称为'''上下文有关语言'''('''context-sensitive language''')。

有些定义中也允许添加 <math>S\rightarrow \epsilon</math> 来允许概念范围中允许任意符号生成空串。

=== 说明 ===

以上为形式化定义。通俗地说，上下文有关文法的含义是，文法中每个非终结符一定可以被展开生成其他文法符号串，且这一展开规则可以依赖上下文中的其他序列。

与[[递归可枚举文法]]相比，上下文有关文法中的符号总是从一个符号生成更多的符号（这里不考虑生成到空或单个符号的情况），而不会将任意多符号一起替换为任意多符号，这意味着判定一个串是否属于语言时生成树总是有限高度的；
展开时可以依赖上下文，但也可以不依赖，也就是接受所依赖的序列可以是空序列，当完全不依赖上下文时，就得到了更加严格的[[上下文无关文法]]。

== 性质 ==

上下文有关语言的：

* [[Kleene 闭包]]
* [[连接]]
* [[并集]]
* [[交集]]
* [[代换、逆代换（语言）|代换、逆代换]]

都仍然是上下文有关的。