|
57 позволяет дать однозначную трактовку ряду других понятий, известных из теории сетей [55], необходимых для решения прикладных задач и развития теории метаграмматик. В ряде практически важных задач моделирования СиПО возникает необходимость разбиения множества {Gi}, аналогично [42, 51], на ряд подмножеств (слоев), стратифицированных по какойлибо системе дополнительных признаков. Подобное разбиение может отражать как объективные структурные свойства моделируемых (специфицируемых) объектов, так и вводиться, исходя из определенных теоретических предпосылок при необходимости сокращения объема формальных описаний, их типизации, уменьшения сложности процедур синтаксического анализа. В дальнейшем подобные ОП МГ будем называть стратифицированными или многослойными и, если необходимо, явным образом отражать это свойство в записи ОП МГ аналогично [42]. В целом предложенный класс МГОП МГвключает в свой состав большинство известных подклассов МГ и позволяет синтезировать широкий набор новых подклассов метаграмматик для решения задач моделирования СиПО, используемых в существующих и перспективных АОС. Предложенная формализация основных понятий для предложенного класса ОП МГ создает необходимый базис для классификации и исследования основных свойств ОП МГ применительно к решаемым прикладным задачам управления. |
70 вершины Gi к вершине Gj будем называть последовательность пар (G*o,G*i) (G*,,G*2)... (G*k.i,G*k), где Gj=G*o, Gj=G*k и существует хотя бы один путь в схеме ГС длины к от элемента gi€Gi до элемента gjeGj (обозначения аналогичны обозначениям в определении 4.6). Определение 2.8. Путь в схеме (обобщенной схеме) ГС будем называть однородным по типу правил управления, если все входящие в него пары (x*0,xi) (х*ьх2) ... (х*к.ьхк) (аналогично (G*0,G*i)... (G*k.bG*k)) соответствуют правилам управления, имеющим одинаковый тип. Определение 2.9. Путь в схеме (обобщенной схеме) ГС, однородный по типу правил управления и погружения, будем называть однородным. Сведение понятия пути в схеме (обобщенной схеме) ГС позволяет дать однозначную трактовку ряду других понятий, известных из теории сетей [120], необходимых для решения прикладных задач и развития теории грамматических сетей. В ряде практически важных задач спецификации и моделирования РСДЗ возникает необходимость разбиения множества {Gj}, аналогично [25-31], на ряд подмножеств (слоев), стратифицированных по какойлибо системе дополнительных признаков. Подобное разбиение может отражать как объективные структурные свойства моделируемых (специфицируемых) объектов, так и вводиться, исходя из определенных теоретических предпосылок при необходимости сокращения объема формальных описаний, их типизации, уменьшения сложности процедур синтаксического анализа. В дальнейшем подобные ГС будем называть стратифицированными или многослойными и, если необходимо, явным образом отражать это свойство в записи ГС аналогично [96]. В целом предложенный класс формальных грамматических системграмматические сети-включает в свой состав большинство известных грамматических систем и позволяет синтезировать широкий набор новых грамматических структур для решения задач спецификации РСДЗ, 71 используемых в существующих и перспективных РСУ. Предложенная формализация основных понятий теории ГС создает необходимый базис для классификации и исследования основных свойств ГС применительно к решаемым прикладным задачам. 2.2. Классификация грамматических сетей, используемых для формального описания разнородных сложноструктурированных данных и знаний Рассмотрение представленных выше основных понятий и определений грамматических сетей как формальных грамматических систем, ориентированных на использование в качестве формальной основы спецификаций и моделирования РСДЗ [81-89, 94-96,100], позволило в рамках введенных определений провести классификацию ГС в соответствии со следующей системой основных признаков. 1. Признаки, характеризующие множество {Gi}: мощность множества {Gj}; тип правил подстановки в грамматиках {Gi}; однородность множества {Gi}; тип дополнительных (экстралингвистических) правил в грамматиках, входящих в ГС; особенности задания мер на множествах правил подстановки грамматик {G;}; тип применяемых специальных форм грамматик. 2. Признаки, характеризующие схему правил управления ГС: мощность множества правил управления; особенности общей схемы правил управления; однородность правил управления; тип правил управления; 89 Выводы 1. Предложенный класс формальных грамматических ч‘структур-грамматические сети-включает в свой состав большинство * известных грамматических структур и позволяет синтезировать широкий набор новых грамматических структур для решения задач распознавания и обработки РСДЗ в существующих и перспективных РСУ. Предложенная формализация основных понятий теории ГС создает необходимый базис для классификации и исследования основных свойств ГС применительно к решаемым прикладным задачам управления. 2. Рассмотрение особенностей предложенных классов ГС показало, f.r; что грамматические сети, по сравнению с существующими грамматическими структурами, позволяют снизить объем синтаксических описаний, повысить ф их наглядность и уменьшить сложность при сохранении мощности порождаемых семейств языков формального описания. 3. Для основных классов грамматических сетей доказаны основные соотношения, характеризующие мощность порождаемых ими семейств Ф языков. В частности, показано, что при использовании однотипных правил управления и погружения в регулярных ГС практически все грамматические сети входят в один класс эквивалентности, соответствующий по мощности семейству регулярных языков. В то же время использование • комбинированных правил управления и погружения позволяет повысить выразительные возможности грамматических сетей, что соответствует, в частности, второму классу эквивалентности в множестве ГС с комбинированными правилами управления и погружения. 4. Доказана замкнутость отдельных классов ГС относительно основных алгебраических операций, что позволяет синтезировать и модифицировать эталонные грамматические сетевые описания ф распознаваемых и обрабатываемых РСДЗ, не выходя за рамки выбранных классов грамматических сетей. 5. В целом рассмотрение формальных свойств базовых классов ГС, |