Грамматика Линейная

один и" видов формальной грамматики, служащий для порождения цепочек вместе с деревьями подчинения (см. Синтаксическая структура). Формально Г. Д. Может быть определена как грамматика бесконтекстная, у к-рой. В каждом правиле, за исключением правил вида , где - начальный и а - основной символы, одно из вхождений символов в правую часть снабжено специальной мет кой. При этом правая часть каждого такого правила должна содержать не менее двух вхождений символов. Система составляющих, отвечающа..

один из видов формальной грамматики. Т. К. Может быть определена как упорядоченная четверка где - конечные множества, элементы к-рых наз. Основными символами и элементарными категориями соответственно. Ф 0 - элемент W, называемый главной категорией. - приписывающая функция, сопоставляющая каждому основному символу конечное множество категорий - выражений, образованных из элементарных категорий и синтаксич. Символов по следующему правилу. 1) всякая элементарная категория есть категория. 2..

..

грамматика непосредственно составляющих, НС-грамматика, грамматика контекстная,- частный случай грамматики порождающей, когда каждое ее правило имеет вид , где - цепочки в алфавите и 0 непуста. Каждый шаг вывода в Г. С. Состоит в замене одного вхождения символа Авхождением цепочки q, причем возможность замены обусловлена наличием "контекста" Вхождения символов в q потом также могут заменяться и т. Д. Таким образом, вхождение символа "развертывается" в нек-рый отрезок возникающей в резу..