TOC 中的上下文敏感语言是什么？

一种上下文敏感的文法，其产生式为

αAβ→αγβ

其中α，β∈(N∪T)*，A∈N；γ ∈ (N ∪ T)+ 并且如果起始符号 S 没有出现在任何规则的右侧，则允许形式为 S → λ 的规则。

由这种文法生成的语言称为上下文敏感语言。

• 每个上下文无关文法也是上下文相关的 =⇒ 上下文无关语言是上下文相关语言的子集（请参阅乔姆斯基范式）。

• 但是，并非所有上下文敏感的语言都是上下文无关的。

示例

语言 {anbncn, n > 1} 是上下文敏感的，但不是上下文无关的。

A grammar for this language is given by:
S → aSBC | aBC,
CB → HB,
HB → HC,
HC → BC,
aB → ab,
bB → bb,
bC → bc,
cC → cc
A derivation e.g. aabbcc, using this grammar is:
S ⇒ aSBC
   ⇒ aaBCBC (using S → aBC)
   ⇒ aabCBC (using aB → ab)
   ⇒ aabHBC (using CB → HB)
   ⇒ aabHCC (using HB → HC)
   ⇒ aabBCC (using HC → BC)
   ⇒ aabbCC (using bB → bb)
   ⇒ aabbcC (using bC → bc)
   ⇒ aabbcc (using cC → cc)

上下文相关语言也可以由单调文法生成，任何产生式都是允许的，只要没有使字符串变短的规则（除了一个 S → ∧）！