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 → ∧）！
以上是 TOC 中的上下文敏感语言是什么？ 的全部内容， 来源链接： utcz.com/z/355096.html
