Context-Sensitive Language

Theorem: All Context-Sensitive Languages are accpetable by Linear Bounded Automata.
Theorem: The language class accepted by Linear Bounded Automata can be generated by Context-Sensitive Grammar.

Context-Sensitive Grammars

A Context-Sensitive Grammar is an unrestricted grammar in which every product has the form:

α \to β

, with

| β | \geq | α |

α

contains at least one variable.

這邊的定義是一種弱版本，也就說 Context-Sensitive Grammar 是 Unrestricted Grammar 的變體，前提就是變換過後的長度會大於原本的長度。

Another Definition of CSG

Definition: a context-sensitive grammar is a quadruple:

G = (V, Σ, R, S)

$V$ is an alphabet. (Variables + Terminals)
$Σ$ is a subset of
$V$ , the set of terminals
$R$ is the set of grammar rules:
$V^{⋆} (V - Σ) V^{⋆} \to V^{⋆} (V)^{+} V^{⋆}$
$S$ is a start variable.

A

是變數，

α

和

β

是字串，有限制上下文才能轉換。

α A β \to α γ β

A \in (V - Σ), α, β \in V^{⋆}, γ \in V^{+}

Context-Sensitive Grammar 是比 Context-Free Grammar 強大，Context-Free Grammar 會是 Context-Sensitive Grammar 的一種！