|
70 Рассмотрение представленной таблицы показывает, что при использовании однотипных правил согласования в регулярных ОП МГ практически все данные метаграмматики входят в один класс эквивалентности, соответствующий по «мощности» мощности семейства регулярных языков. В то же время использование оценочнопродукционных правил согласования позволяет повысить «выразительные» возможности ОП МГ, что соответствует, в частности, второму классу эквивалентности в множестве ОП МГ с оценочнопродукционными правилами согласования. В случае контекстносвободных ОП МГ использование даже однотипных правил согласования в ряде случаев выводит ОП МГ за пределы класса эквивалентности, соответствующего по мощности семейству контекстно-свободных языков. Для отдельных классов ОП МГ в табл. 2.2 представлены основные доказанные соотношения [20-28], характеризующие мощность порождаемых ими семейств языков. В частности, замкнутость отдельных классов ОП МГ относительно конкатенации позволяет специфицировать различного рода «сцепления» цепочек СиПО, не выходя за рамки выбранных классов метаграмматик; замкнутость относительно положительной итерации позволяет с использованием простых грамматических спецификаций описывать сложные системы объединяемых СиПО, в том числе и в условиях их модификации и т.п. В целом рассмотрение формальных свойств базовых классов ОП МГ, являющихся основой для построения более сложных (комбинированных и т.п.) структурно-лингвистических описаний для моделирования СиПО, показало, что данный формальный аппарат, сохраняя большинство положительных свойств обычных грамматик по сравнению с ними, позволяет специфицировать более сложные синтаксические и семантические структуры СиПО. |
87 соответствуют интерпретациям правил управления и погружения. Для конкретных подклассов ГС форма задания семейств порождаемых V > (специфицируемых) языков может быть конкретизирована аналогично [96]. ф Рассмотрение порождающих возможностей отдельных классов грамматических сетей показало, что отдельные подклассы ГС, отличающиеся типом правил управления и погружения, эквивалентны друг другу, что позволяет использовать любой из рассматриваемых подклассов ГС, руководствуясь соображениями удобства применения, наглядности, компактности представления моделируемых объектов. В табл. 2.1 представлен ряд классов эквивалентности для ГС, имеющих в своем составе только обычные грамматики (грамматики без дополнительных правил и модификаций, грамматики Хомского [119]), а ф также при использовании только однозначных отображений в схеме грамматических сетей. Доказательства данных свойств представлены в работах [50-96]. Рассмотрение представленной таблицы показывает, что при Ф использовании однотипных правил управления и погружения в регулярных ГС практически все грамматические сети входят в один класс эквивалентности, соответствующий по «мощности» мощности семейства регулярных языков. В то же время использование комбинированных правил • управления и погружения позволяет повысить «выразительные» возможности грамматических сетей, что соответствует, в частности, второму классу эквивалентности в множестве ГС с комбинированными правилами управления и погружения. В случае КСГС использование даже однотипных правил управления и погружения в ряде случаев выводит ГС за пределы класса эквивалентности, соответствующего по мощности семейству контекстно-свободных языков. Ф Для отдельных классов грамматических сетей в табл. 2.2 представлены основные доказанные соотношения [96], характеризующие мощность порождаемых ими семейств языков. 88 В частности, замкнутость отдельных классов ГС относительно конкатенации позволяет специфицировать различного рода «сцепления» цепочек РСДЗ, не выходя за рамки выбранных классов грамматических • сетей; замкнутость относительно положительной итерации позволяет с использованием простых грамматических спецификаций описывать сложные системы объединяемых РСДЗ, в том числе и в условиях их искажений и т.п. В целом рассмотрение формальных свойств базовых классов ГС, являющихся основой для построения более сложных (комбинированных и т.п.) грамматических сетей для моделирования РСДЗ, показало, что данный формальный аппарат, сохраняя большинство положительных свойств к обычных грамматик по сравнению с ними, позволяет специфицировать более сложные синтаксические и семантические объекты. Таблица 2.1 Однотипность правил управления и погружения Классы эквивалентности регулярные ГС контекстно-свободные ГС Однотипные {QbS, QeS ,QbP, QeP }, (CbK ,CeK, Сьм> Сем } {QbS, QeS, QbP, QeP }, {Ськ, Сек, CbM, CeM } Комбинированные {(QbS+Qes)> (QbS+Qbp), (QbS+QeP), (QeS +Qbp), (QeS +Qbp),---} {(QbS+Qes), (QbS+Qbp), (QbS+QeP), (QeS +Qbp), (QeS +Qbp),--} Таблица 2.2 Регулярные ГС Контекстно-свободные ГС LoCQbs) 5= Lper, LG(QbS+Qes)cLper, Lg(Qcs +Qbp)sLper, LG((QbS+Qep)) <=LhC Lc(Qbs) £ LHC, Lg(Qcs)) c L,icj LG(QbS+Qes) £ LKC, LG(QbS"^Qep) c Liic5 Lg(QcS +Qbp)<=LHC 89 Выводы 1. Предложенный класс формальных грамматических ч‘структур-грамматические сети-включает в свой состав большинство * известных грамматических структур и позволяет синтезировать широкий набор новых грамматических структур для решения задач распознавания и обработки РСДЗ в существующих и перспективных РСУ. Предложенная формализация основных понятий теории ГС создает необходимый базис для классификации и исследования основных свойств ГС применительно к решаемым прикладным задачам управления. 2. Рассмотрение особенностей предложенных классов ГС показало, f.r; что грамматические сети, по сравнению с существующими грамматическими структурами, позволяют снизить объем синтаксических описаний, повысить ф их наглядность и уменьшить сложность при сохранении мощности порождаемых семейств языков формального описания. 3. Для основных классов грамматических сетей доказаны основные соотношения, характеризующие мощность порождаемых ими семейств Ф языков. В частности, показано, что при использовании однотипных правил управления и погружения в регулярных ГС практически все грамматические сети входят в один класс эквивалентности, соответствующий по мощности семейству регулярных языков. В то же время использование • комбинированных правил управления и погружения позволяет повысить выразительные возможности грамматических сетей, что соответствует, в частности, второму классу эквивалентности в множестве ГС с комбинированными правилами управления и погружения. 4. Доказана замкнутость отдельных классов ГС относительно основных алгебраических операций, что позволяет синтезировать и модифицировать эталонные грамматические сетевые описания ф распознаваемых и обрабатываемых РСДЗ, не выходя за рамки выбранных классов грамматических сетей. 5. В целом рассмотрение формальных свойств базовых классов ГС, |