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

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


[Касьянов-Поттосин]
[Касьянов-Поттосин]
[[Категория: Теория формальных языков]].

Версия от 13:31, 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],

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