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

Материал из WEGA
Версия от 10:59, 26 июня 2009; KEV (обсуждение | вклад) (Создана новая страница размером '''Контекстно-зависимая грамматика''' (''Context-sensitive grammar'') - [[гр...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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