Контекстно-зависимая грамматика: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Контекстно-зависимая грамматика''' (''Context-sensitive grammar'') - [[гр...)
(нет различий)

Версия от 10:59, 26 июня 2009

Контекстно-зависимая грамматика (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],

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