84 возможно, по конечному множеству цепочек из дополнения к L (G). Восстановленная грамматика — это совокупность правил, описывающая данное конечное множество цепочек из L (G), по которой можно вывести другие цепочки той же природы, что и цепочки заданного множества. Известные в настоящее время методы и алгоритмы восстановления грамматик и метаграмматик можно разделить на два основных класса: 1) алгоритмы восстановления грамматики перечислением; 2) алгоритмы восстановления индукцией. Основные результаты анализа существующих методов восстановления представлены в [3]. В частности, работах [19, 107, 93-108] приведены основные теоретические положения и намечены подходы к решению задачи восстановления обычных грамматик, а в работах [3, 92] описана совокупность эвристических правил автоматического восстановления грамматик для моделирования сложноструктурированных данных. Формулировка задачи восстановления обычных грамматик содержит три основных пункта [3]: 1) выделение множества непроизводных элементов, из которых составляются рассматриваемые структуры; 2) выделение множества предикатов, описывающих структурные отношения между непроизводными элементами, которые являются аргументами предикатов; 3) синтез множества правил подстановки, каждое из которых должно состоять из трех частей: а) наименования определяемого объекта; б) списка перемен-’ных для составных частей объекта (вспомогательных символов); в) условий, которым должны удовлетворять составные части, чтобы воспроизвести определяемый объект. Таким образом, для заданного множества объектов XI, Х2, ..., Хп, имеющих общую синтаксическую структуру, задача восстановления |
92 которые порождают неправильные цепочки, что приводит в большинстве случаев к ошибкам распознавания и обработки, иногда очень существенным [149,157]. • Обычно, в известной литературе задачи создания формальных грамматик по слабоформализованным описаниям (описания форматов хранения и кодирования, протоколов и процедур обмена РСДЗ на языках типа SDL и т.п.) относят к задачам синтеза грамматик, а задачи создания ФГ по образцам цепочек распознаваемых и обрабатываемых РСДЗ (реальные данные и знания)к задачам восстановления. Анализ известных подходов к синтезу ФГ [16, 96, 129] показывает, что развитые в них подходы относятся к классу эвристических и основаны на явном учете структуры и правил построения моделируемых объектов и ф систем в рамках своеобразного структурноагрегативнодекомпозиционного подхода, принципов структурного программирования, при явной привязке создаваемого структурнолингвистического описания к структуре моделируемых объектов и при незначительном использовании процедур минимизации грамматического описания, проверки на наличие тупиковых выводов, проверки согласованности грамматики (для стохастических грамматик). Предложенные методы, за исключением [101,104, 106], не позволяют синтезировать сложные многоуровневые и сетевые • грамматические структуры, что существенно ограничивает их применение при решении задач реального уровня сложности. Задача восстановления грамматики состоит главным образом в построении процедур восстановления синтаксических правил неизвестной грамматики по конечному множеству предложений или цепочек языка L (G), порождаемого грамматикой G, и, возможно, по конечному множеству цепочек из дополнения к L (G). Восстановленная грамматика — это • совокупность правил, описывающая данное конечное множество цепочек из . L (G), по которой можно вывести другие цепочки той же природы, что и цепочки заданного множества. 93 Известные в настоящее время методы и алгоритмы восстановления грамматики можно разделить на два основных класса: f' п‘ 1)алгоритмы восстановления грамматикиперечислением; ф 2)алгоритмы восстановления индукцией. Основные результаты проведенного анализа существующих методов восстановления представлены в [96]. В частности, работах [119, 129, 133-140] приведены основные теоретические положения и намечены подходы к решению задачи восстановления обычных грамматик, а в работах [119, 135, 140] описана совокупность эвристических правил автоматического восстановления грамматик для описания и распознавания сложноструктурированных образов. ф Формулировка задачи восстановления обычных грамматик содержит три основных пункта [119]: 1) выделение множества непроизводных элементов, из которых составляются рассматриваемые структуры; 2) выделение множества предикатов, описывающих структурные отношения между непроизводными элементами, которые являются аргументами предикатов; 3) синтез множества правил подстановки, каждое из которых должно ф состоять из трех частей: а) наименования определяемого объекта; б) списка переменных для составных частей объекта (вспомогательных символов); в) условий, которым должны удовлетворять составные части, чтобы воспроизвести определяемый объект. Таким образом, для заданного множества объектов XI, Х2, ..., Хп, имеющих общую синтаксическую структуру, задача восстановления состоит в том, чтобы при данных непроизводных элементах и предикатах построить Ф грамматику, которая является некоторым приближением заданного множества структур. Проведенный анализ существующих подходов и методов позволил |