62 Одним из наиболее важных классификационных признаков, определяющим выразительные возможности ОП МГ и большинства других классов формальных грамматик и грамматических структур, является тип используемых правил подстановки (продукций) [19]. Аналогично общепринятой классификации формальных грамматик по Хомскому [41], будем выделять 4 типа ОП МГ, отличающихся ограничениями, накладываемыми на множество продукций: регулярные (тип 3), контекстносвободные (тип 2), контекстно-зависимые ОП МГ (ОП МГ непосредственносоставляющих) (тип 1) и неограниченные ОП МГ (тип 0). Для этих случаев входящие в ОП МГ атрибутные грамматики [ Грамматики типа 0нет ограничений на тип правил подстановки. 2. Грамматики типа 1-хотя бы одна грамматика содержит правила ociAoc2—>0CiPoc2, где Ае VNi, cxi, £, а2 е V*,, Р^е (е-пустая цепочка), V*; итерация множества V; = VN; uVTi, а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 2 и 3). 3. Грамматики типа 2-хотя бы одна грамматика содержит правила А—>р, где Ае VNi, Ре V\ V*r положительная итерация множества V, = VNi uVTi, а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 3). 4. Грамматики типа 3-грамматики содержат правила типа 3 А—>аВ, или А-»а, где A,Be Vnh ае VTi. Соответственно, ОП МГ подобных типов будем обозначать Grc(i), где i-тип ОПМГ, i=0(l)3. Применение ОП МГ различных типов определяется особенностями синтаксической структуры специфицируемых СиПО, требованиями к полноте, адекватности и структурной сложности создаваемых формальных |
16 Одним из наиболее важных классификационных признаков, . определяющим выразительные возможности ГС и большинства других • классов формальных грамматик и грамматических структур, является тип используемых правил подстановки (продукций) [119]. Аналогично общепринятой классификации формальных грамматик по Хомскому [125], будем выделять 4 типа ГС, отличающихся ограничениями, накладываемыми на множество продукций: регулярные (тип 3), контекстно-свободные (тип 2), контекстно-зависимые грамматические сети (ГС непосредственносоставляющих) (тип 1) и неограниченные ГС (тип 0). Для этих случаев входящие в ГС грамматики {<Уыь Уть Sj, Pj, Dj>, i=l(1 )N содержат в схемах Pj правила подстановки следующих типов: • 1. Грамматики типа 0нет ограничений на тип правил подстановки. 2. Грамматики типа 1-хотя бы одна грамматика содержит правила aiAoi2-»ctiPcc2, где Ае VNi, ab р, a2 е V*j, р^е (е-пустая цепочка), V*j итерация множества Vj = VNi uVTi, а остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 2 и 3). 3. Грамматики типа 2-хотя бы одна грамматика содержит правила А-»Р, где Ае VNi, ре V+j, V+jположительная итерация множества Vj = VNi uVTi, а ® остальные грамматики имеют схемы с более сильными ограничениями на тип правил подстановки (правила типа 3). 4. Грамматики типа 3-грамматики содержат правила типа 3 А-»аВ, или А->а, где A,Be VNi, ае VTi. Соответственно, грамматические сети подобных типов будем обозначать Grc(i), где i-тип ГС, 1=0(1 )3. Применение ГС различных типов определяется особенностями • синтаксической структуры специфицируемых сигнальных и протокольных л объектов, требованиями к полноте, точности и структурной сложности |