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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 6: Строка 6:
<math>\alpha,\beta\in (N\cup\Sigma)^*</math>.
<math>\alpha,\beta\in (N\cup\Sigma)^*</math>.


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


==Литература==
==Литература==

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

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