Контекстно-зависимая грамматика

Контекстно-зависимая грамматика (Context-sensitive grammar) - грамматика [math]\displaystyle{ G = (N, \Sigma, }[/math] [math]\displaystyle{ P, S) }[/math], в которой каждое правило имеет вид

[math]\displaystyle{ \alpha A\beta\longrightarrow\alpha\omega\beta, }[/math] где [math]\displaystyle{ A\in N,\omega\in(N\cup\Sigma)^+ }[/math] и [math]\displaystyle{ \alpha,\beta\in (N\cup\Sigma)^* }[/math].

Другие названия - Грамматика типа 1, КЗ-грамматика, Неукорачивающаяся грамматика.

Литература

[Ахо-Ульман],

[Касьянов/95],

[Касьянов-Поттосин]