|
69 грамматики Gr, входящей в подмножество определенным образом выделенных «начальных» грамматик {Gr}c{Gj}; К—обозначение определенного рода композиции цепочек хт (объединение, конкатенация и т.п.), зависящей от типа и интерпретации правил согласования; =>* есть рефлексивное и транзитивное замыкание отображения => непосредственного вывода с учетом правил управления и погружения грамматик, входящих в ОПМГ [42]. Выделение подмножеств {Gm} и {Gr} определяется главным образом спецификой конкретной решаемой прикладной задачи; ограничение набора композиций К, помимо прочего, определяется структурными свойствами моделируемых СиПО, типом и интерпретацией используемых правил согласования, которым должна даваться определенная трактовка в рамках решаемых прикладных задач. В большинстве практически важных случаев в качестве базовых композиций К использованы операции объединения и конкатенации. Эти операции, в определенной степени, соответствуют интерпретациям правил согласования. Для конкретных подклассов ОП МГ форма задания семейств порождаемых (специфицируемых) языков может быть конкретизирована аналогично [42,51]. Рассмотрение порождающих возможностей отдельных классов предложенных метаграмматик показало, что отдельные подклассы ОП МГ, отличающиеся типом правил согласования, эквивалентны друг другу, что позволяет использовать любой из рассматриваемых подклассов ОП МГ, руководствуясь соображениями удобства применения, наглядности, компактности представления моделируемых СиПО. В табл. 2.1 представлен ряд классов эквивалентности для ОП МГ, имеющих в своем составе только обычные атрибутные грамматики (грамматики без дополнительных правил и модификаций, грамматики Хомского [41]), а также при использовании только однозначных отображений в схеме ОП МГ. Доказательства данных свойств представлены в работах [20-25]. |
86 формальных спецификаций. Определение мощности семейства формальных языков, порождаемого У* > ГС, необходимо при оценке возможности описания конкретного класса ф сигнальных и информационных объектов с использованием таких грамматических структур. Одним из наиболее важных свойств семейств формальных языков, порождаемых ГС, является замкнутость относительно основных алгебраических операций [119], которая определяет возможность дополнения и изменения элементов формальных грамматических моделей при формировании комбинированных описаний РСДЗ без выхода за пределы данного класса грамматик. В общем случае язык, порождаемый ГС, определяется как множество • цепочек L(G)=K{xm xme V*T(m); Sr=S>*xm}; m,re{l,...,N}, где У*Т(т)-итерация множества Vi(m), VT(m) -множество терминалов грамматики Gm, входящей в подмножество определенным образом выделенных «завершающих» грамматик {Gm}cz{Gj}; S-начальный нетерминал грамматики Gr, входящей в подмножество определенным образом выделенных «начальных» грамматик {Gr}c{Gj}; К-обозначение определенного рода композиции цепочек хт (объединение, конкатенация и т.п.), зависящей от типа и интерпретации правил управления и погружения; =>* есть рефлексивное и транзитивное • замыкание отображения => непосредственного вывода с учетом правил управления и погружения грамматик, входящих в ГС [96]. Выделение подмножеств {Gm} и (Gr] определяется главным образом спецификой конкретной решаемой прикладной задачи; ограничение набора композиций К, помимо прочего, определяется структурными свойствами специфицируемых объектов, типом и интерпретацией используемых правил управления и погружения, которым должна даваться определенная трактовка • в рамках решаемых прикладных задач. В большинстве практически важных .5' случаев в качестве базовых композиций К использованы операции объединения и конкатенации. Эти операции, в определенной степени, 87 соответствуют интерпретациям правил управления и погружения. Для конкретных подклассов ГС форма задания семейств порождаемых V > (специфицируемых) языков может быть конкретизирована аналогично [96]. ф Рассмотрение порождающих возможностей отдельных классов грамматических сетей показало, что отдельные подклассы ГС, отличающиеся типом правил управления и погружения, эквивалентны друг другу, что позволяет использовать любой из рассматриваемых подклассов ГС, руководствуясь соображениями удобства применения, наглядности, компактности представления моделируемых объектов. В табл. 2.1 представлен ряд классов эквивалентности для ГС, имеющих в своем составе только обычные грамматики (грамматики без дополнительных правил и модификаций, грамматики Хомского [119]), а ф также при использовании только однозначных отображений в схеме грамматических сетей. Доказательства данных свойств представлены в работах [50-96]. Рассмотрение представленной таблицы показывает, что при Ф использовании однотипных правил управления и погружения в регулярных ГС практически все грамматические сети входят в один класс эквивалентности, соответствующий по «мощности» мощности семейства регулярных языков. В то же время использование комбинированных правил • управления и погружения позволяет повысить «выразительные» возможности грамматических сетей, что соответствует, в частности, второму классу эквивалентности в множестве ГС с комбинированными правилами управления и погружения. В случае КСГС использование даже однотипных правил управления и погружения в ряде случаев выводит ГС за пределы класса эквивалентности, соответствующего по мощности семейству контекстно-свободных языков. Ф Для отдельных классов грамматических сетей в табл. 2.2 представлены основные доказанные соотношения [96], характеризующие мощность порождаемых ими семейств языков. |