Грамматика Составляющих

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

Множество всех отрезков последней цепочки вывода, получающихся "развертыванием" вхождений вспомогательных символов - иначе говоря, "происходящих" от (неконцевых) вершин дерева вывода - при добавлении всех одноточечных отрезков образует систему составляющих указанной цепочки (см. Синтаксическая структура);отсюда и название "Г. С.". Если все одноточечные отрезки также получаются заменой вхождений вспомогательных символов, то можно получить размеченную систему составляющих, приписывая каждой составляющей в качестве меток те вспомогательные символы, от вхождений к-рых она "происходит". Так, в приведенном выше примере для цепочки получается размеченная система составляющих (здесь границы составляющих указаны скобками, после правых скобок записаны метки).

Приписывание цепочкам размеченных систем составляющих лежит в основе лингвистич. Приложений Г. С. Так, грамматика, имеющая (в числе прочих) правила где ПРЕДЛ, - вспомогательные символы, означающие, соответственно, "предложение", "существительное рода хв числе уи падеже г", "группа глагола в 3-м лице", "переходный глагол в 3-м лице", а символ ПРЕДЛ - начальный, приписывает предложению "Эллипс пересекает параболу" размеченную систему составляющих Математич. Значение Г. С. Определяется прежде всего тем, что порождаемые ими языки (так наз. НС-языки) представляют собой простой подкласс класса примитивно рекурсивных множеств. Класс НС-языков совпадает с классом языков, допускаемых недетерминированными линейно ограниченными Тьюринга машинами с одной лентой п одной головкой.

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

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

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