Грамматика бесконтекстная

грамматика контекстно-свободная, КС-грамматика,- грамматика составляющих, все правила к-рой имеют вид [img: http://localhost:8080/file/010426-179.jpg] где А - вспомогательный символ и [img: http://localhost:8080/file/010426-180.jpg] - непустая цепочка (так наз. бесконтекстные правила). Языки, порождаемые такими грамматиками, наз. бесконтекстными языками. Напр., язык [img: http://localhost:8080/file/010426-181.jpg] порождается Г. б. с правилами [img: http://localhost:8080/file/010426-182.jpg] ([img: http://localhost:8080/file/010426-183.jpg] - начальный символ). В определении Г. б. условие непустоты [img: http://localhost:8080/file/010426-184.jpg] можно отбросить без существенного изменения класса языков (добавляются лишь языки, получаемые из бесконтекстных присоединением пустой цепочки). Г. б.- наиболее употребительный в приложениях класс формальных грамматик;они широко используются для построения математич. моделей естественных языков (см. Математическая лингвистика).и для описания языков программирования. Класс бесконтекстных языков является собственным подклассом класса НС-языков (см. Грамматика составляющих;напр., НС-язык [img: http://localhost:8080/file/010426-185.jpg] [img: http://localhost:8080/file/010426-186.jpg] не бесконтекстный) и совпадает с классом языков, допускаемых так наз. автоматами с магазинной памятью (МП -автоматами). Каждая Г. б. может быть эквивалентным образом приведена к стандартной бинарной форме - Г. б., все правила к-рой имеют вид [img: http://localhost:8080/file/010426-187.jpg] и [img: http://localhost:8080/file/010426-188.jpg], а также кнормальной форме Грейбах - Г. б., все правила к-рой имеют вид [img: http://localhost:8080/file/010426-189.jpg], [img: http://localhost:8080/file/010426-190.jpg] и [img: http://localhost:8080/file/010426-191.jpg] (в обоих случаях А, В, С - вспомогательные символы, а - основной символ). Бесконтекстные языки определяются также грамматиками категориальными, грамматиками доминационными, грамматиками зависимостей. Иногда для определения бесконтекстных языков используются так наз. нормальные системы уравнений в языках, представляющие собой другую форму записи Г. б. Класс бесконтекстных языков замкнут относительно объединения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью и относительно итерации) и не замкнут относительно пересечения и дополнения. Г. б. Г наз. однозначной, если для каждой цепочки языка L(Г)имеется единственное дерево вывода в Г. Бесконтекстный язык наз. однозначным, если он порождается нек-рой однозначной Г. б.; в противном случае он наз. неоднозначным (или существенно неоднозначным, существенно неопределенным). Пример неоднозначного бесконтекстного языка - [img: http://localhost:8080/file/010426-192.jpg] Если для любой Г. б., порождающей бесконтекстный язык L, и любого натурального [img: http://localhost:8080/file/010426-193.jpg] найдется цепочка, имеющая более пдеревьев вывода в данной грамматике, говорят, что Lимеет бесконечную степень неоднозначности; пример - язык [img: http://localhost:8080/file/010426-194.jpg] [img: http://localhost:8080/file/010426-195.jpg] где [img: http://localhost:8080/file/010426-196.jpg] означает обращение (т. е. если [img: http://localhost:8080/file/010426-197.jpg]). Бесконтекстный язык наз. детерминированным, если он допускается нек-рым детерминированным МП-автоматом. Всякий детерминированный язык однозначен, обратное неверно: напр., однозначный язык [img: http://localhost:8080/file/010426-198.jpg] не является детерминированным. Сложность вывода. Для любой Г. б. временная сложность н емкость вывода (см. Грамматика порождающая).ограничены сверху и снизу линейными функциями. Поэтому для классификации Г. б. по сложности вывода вводятся нек-рые специфич. характеристики сложности. Эти характеристики разделяются на два типа: одни из них ("древесные") строятся на основе представления вывода в виде дерева (см. Грамматика составляющих), другие ("цепочечные") основаны на учете числа или расположения вхождений вспомогательных символов в промежуточные цепочки вывода; в ряде важных случаев с "древесными" характеристиками можно связать "цепочечные", имеющие тот же порядок роста. Из "древесных" характеристик наиболее тонкую классификацию дает густота, определяемая следующим образом. 1) Каждой вершине [img: http://localhost:8080/file/010426-199.jpg] конечного дерева с корнем сопоставляется густота [img: http://localhost:8080/file/010426-200.jpg] - число [img: http://localhost:8080/file/010426-201.jpg] такое, что: если [img: http://localhost:8080/file/010426-202.jpg] - концевой узел, то [img: http://localhost:8080/file/010426-203.jpg]; если [img: http://localhost:8080/file/010426-204.jpg] - все узлы, в к-рые из [img: http://localhost:8080/file/010426-205.jpg] идут дуги, [img: http://localhost:8080/file/010426-206.jpg] и [img: http://localhost:8080/file/010426-207.jpg], то: а) если [img: http://localhost:8080/file/010426-208.jpg] только для одного [img: http://localhost:8080/file/010426-209.jpg] б) в противном случае [img: http://localhost:8080/file/010426-210.jpg]. 2) Густота корня дерева наз. густотой дерева. 3) Если Г есть Г. б., ее густота [img: http://localhost:8080/file/010426-211.jpg] определяется аналогично временной сложности с заменой длины вывода густотой дерева вывода. Одинаковый с густотой порядок роста имеет (для Г. б.) активная емкость [img: http://localhost:8080/file/010426-212.jpg], определяемая аналогично емкости с заменой длины цепочки [img: http://localhost:8080/file/010426-213.jpg] числом вхождений в wi вспомогательных символов. Густота всякой Г. б. ограничена сверху логарнфмич. функцией. Существуют бесконтекстные языки, для к-рых густоты любых порождающих их Г. б. имеют логарифмич. порядок роста, напр, множество всевозможных "правильных скобочных последовательностей" (т. е. последовательностей левых и правых круглых скобок, расставленных так, как это делается, напр., в арифметич. выражениях). В то же время языки, порождаемые Г. б., густоты к-рых ограничены константами, составляют обширный класс, совпадающий с замыканием класса линейных языков (см. Грамматика линейная).относительно подстановки. Имеются бесконечные последовательности функций, промежуточных по порядку роста между константой и логарифмом, такие, что для любых двух соседних членов последовательности найдется бесконтекстный язык, для к-рого наименьшая по порядку густота порождающей его Г. б. заключена между этими функциями. Употребляются и другие характеристики сложности вывода в Г. б. Предметом интенсивных исследований является и управление выводом в Г. б. Предложено много различных концепций управления выводом в Г. б. (из к-рых значительная часть переносится и на более широкие классы грамматик). Так, матричная грамматика получается, если задано нек-рое множество конечных последовательностей правил грамматики - "матриц" и допустимыми выводами считаются те, для к-рых последовательности применяемых правил могут быть разбиты на матрицы (т. е. правила применяются только "группами"). В грамматике с порядком на множестве правил задается частичный порядок и на каждом шаге разрешается применять только такие правила, для к-рых никакие предшествующие в смысле этого порядка правила не применимы к полученной к данному моменту цепочке. В программированной грамматике каждому правилу сопоставляются два множества правил - "успешное" и "безуспешное"; применение каждого правила распадается на два этапа: на первом этапе проверяется, входит ли левая часть правила в полученную к данному моменту цепочку; если да, то второй этап состоит в замене левой части правила правой и выборе из "успешного" множества правила для применения на следующем шаге; если нет, то второй этап сводится к выбору из "безуспешного" множества правила для применения на следующем шаге. Класс языков, порождаемых программированными Г. б. без правил с пустой правой частью, является собственным подклассом класса НС-языков и содержит классы языков, порождаемых матричными Г. б. и Г. б. с порядком; в то же время оба эти класса шире класса бесконтекстных языков. При наличии правил с пустой правой частью программированные Г. б. порождают произвольные рекурсивно перечислимые языки. Алгоритмические проблемы. Существуют алгоритмы, позволяющие по любой Г. б. распознавать, является ли порождаемый ею язык пустым, соответственно конечным. В классе Г. б. нераспознаваемы, в частности, следующие свойства языков и отношения между языками: иметь пустое, соответственно конечное или бесконтекстное дополнение; быть однозначным, соответственно детерминированным, линейным или автоматным языком; [img: http://localhost:8080/file/010426-214.jpg] Существуют такие Г. б. [img: http://localhost:8080/file/010426-215.jpg], для к-рых нет алгоритмов, позволяющих по произвольным, цепочкам хи у в основном алфавите [img: http://localhost:8080/file/010426-216.jpg] грамматики [img: http://localhost:8080/file/010426-217.jpg] (соответственно в основном алфавите [img: http://localhost:8080/file/010426-218.jpg] грамматика [img: http://localhost:8080/file/010426-219.jpg]) распознавать, замещаема ли х на у относительно [img: http://localhost:8080/file/010426-220.jpg] и [img: http://localhost:8080/file/010426-221.jpg] (соответственно взаимозамещаемы ли хи уотносительно [img: http://localhost:8080/file/010426-222.jpg] и [img: http://localhost:8080/file/010426-223.jpg]; см. Аналитическая модель языка). Сложность распознавания. Принадлежность цепочки языку, порождаемому заданной Г. б., может быть распознана алгоритмом Кока, допускающим реализацию на машине Тьюринга с одной лентой и одной, головкой, время работы к-рой пропорционально четвертой степени длины цепочки; при увеличении числа лент или головок до трех четвертая степень может быть заменена третьей. См. также Грамматика автоматная, Грамматика линейная.