§ 7.2. Нечеткие грамматики и их свойства

Определение 7.2 [16, 19]. Нечеткая грамматика — это шестерка

где — множество нетерминальных символов; — множество терминальных символов; — начальный символ — конечное множество правил подстановки вида — множество весов (например, дистрибутивная решетка с 0 и 1); — степень принадлежности выводу правила

Далее множество всех терминальных и нетерминальных волов будем обозначать

Пусть задана грамматика . Говорят, что и непосредственно порождает со степенью если найдутся такие

что Это обозначаем как и или

Пусть . Последовательность называется выводом (цепочкой вывода) и из выводимой из и в грамматике если существует последовательность подстановок из Р:

Выводимость из и в грамматике обозначаем и . В общем случае может существовать более одной цепочки вывода. Если то говорят, что порождает терминальную цепочку посредством подстановок .

Наличие степени принадлежности выводу правил из Р требует введения определенных способов вычисления степени принадлежности выводу цепочки правил подстановки и степени выводимости некоторой терминальной цепочки из в грамматике

Учитывая это, нечеткие грамматики (НГ) могут быть классифицированы как по способу вычисления степени выводимости, так и по виду правил подстановки.

Множество правил вывода Р и функция определяют нечеткое бинарное отношение

Следовательно, определение операции композиции отношений дает способ вычисления степени выводимости. Если

и операции обладают свойством дистрибутивности на то степень выводимости х из вычисляется по следующей формуле:

где — множество цепочек вывода.

В [16] приведены различные способы определения операций Соответствующие операции и типы грамматик приведены в табл. 7.1.

В [16] определяется также смешанная НГ

где пессимистическая и оптимистическая НГ.

Далее, на протяжении всей главы, если не оговорено особо, под НГ будут подразумеваться пессимистические НГ.

Наряду с грамматиками, приведенными в табл. 7.1, известны другие типы грамматик. В [8] исследована дробная которой

степень выводимости вычисляется по формуле:

где k — индекс цепочки подстановок, порождающей слово — количество подстановок в цепочке вывода;

Дробные НГ использовались при грамматическом разборе в процедуре распознавания образов. В [33] изучаются древовидные грамматики, в которых дополнительно используется отображение где — множество натуральных чисел. Отображение позволяет упорядочивать (нумеровать) символы из и . В этом случае левые и правые части подстановок и получаемые в результате вывода слова интерпретируются как деревья. В табл. 7.2 приводится классификация НГ по виду правил подстановки [12].

Таблица 7.1 (см. скан)

При анализе грамматик существенную роль играют свойства рекурсивности и эквивалентности.

НГ называется рекурсивной тогда и только тогда, когда существует алгоритм вычисления . В [12] доказана рекурсивность нечетких пессимистических КЗ-грамматик. В четком случае аналогичное свойство доказано для грамматик непосредственна

Таблица 7.2 (см. скан)

составляющих, т. е. таких грамматик, у которых правила подстановки и обладают свойством: . Под рекурсивностью здесь, естественно, понимается возможность построения алгоритма, позволяющего определить: выводима ли рассматриваемая цепочка в данной грамматике. Заметим, что нечеткие и Р-грамматики тоже рекурсивны, так как они являются частными случаями нечеткой КЗ-грамматики.

Две и называются эквивалентными тогда и только тогда, ковда для любого

Для нечетких КС-грамматик, как и для четкого случая, возможно построение канонических форм Грейбаха и Хомского.

Каноническая форма Хомского. Нечеткая пессимистическая КС-грамматика эквивалентна некоторой с правилами подстановки вида:

Каноническую форму грамматики в [12] предлагается конструировать в три этапа. Во-первых, построение грамматики эквивалентной которой нет правил вида Во-вторых, построение грамматики эквивалентной которой нет правил подстановки вида:

В-третьих, построение грамматики эквивалентной , у которой все правила подстановки имеют канонический вид.

Пример 7.1. Рассмотрим нечеткую пессимистическую КС-грамматику с алфавитами и правилами подстановки, приведенными в табл. 7.3. Этапы построения канонической формы Хомского проиллюстрированы в табл. 7.3. При построении добавлены нетерминальные символы Си

Каноническая форма Грейбаха [12]. Нечеткая пессимистическая КС-грамматика эквивалентна некоторой с правилами подстановки вида:

Конструирование канонической формы осуществляется следующим образом.

Во-первых, строится каноническая форма Хомского. Все нетерминальные символы в канонической форме Хомского перенумеровываются: .

Таблица 7.3 (см. скан)

Во-вторых, все правила подстановки приводятся к виду: Это выполняется следующим образом. Пусть для к нетерминальных символов правила подстановки имеют вид: тогда правило подстановки в котором используя правило с левой частью приводится к виду Если то вводится новый нетерминальный символ и правила подстановки приобретают вид:

При преобразовании используется следующая лемма:

Если — нечеткая пессимистическая КС-грамматика и множества правил подстановки такие, что то грамматика, полученная заменой правил правилами

для которых

эквивалентна грамматике

В-третьих, правила подстановки преобразуются к такому виду, чтобы их левые части начинались с терминальных символов.

Пример 7.2. Пусть дана нечеткая пессимистическая КС-грамматика в канонической форме Хомского с алфавитами . Этапы построения канонической формы Грейбаха проиллюстрированы в табл. 7.4.

Часто бывает естественным конструирование грамматик, в которых степень правильности использования правила подстановки зависит от ранее использованных в цепочке вывода правил подстановки. Такой тип грамматик, названный -кратными, рассматривается в [17].

Определение 7.3. Нечеткая -кратная грамматика — это шестерка

где обозначают то же, что и в определении 7.2, а

— степень использования правила при условии, что перед были использованы правила

Если имеется цепочка вывода

и

(кликните для просмотра скана)

то цепочка вывода примет вид:

Если тогда степень принадлежности вычисляется по формуле

Пример 7.3. Приведем -кратную предложенную в [17]. Пусть Правила подстановки грамматики и значения приведены в табл. 7.5. В пустых клетках таблицы предполагаются значения из интервала [0, 0,65].

Таблица 7.5 (см. скан)

Приведем примеры вывода слова

В грамматике возможны и другие выводы этого слова. Степень принадлежности выводу последовательности подстановок

а) равен 0,7, а последовательности подстановок б) 0,8. Можно» проверить, что степень вывода

Из определений 7.2 и 7.3 следует, что -кратная НГ является обычно НГ.

В [17] доказаны следующие свойства -кратных грамматик: для любой нечеткой -кратной КС-грамматики существует эквивалентная ей нечеткая -кратная КЗ-грамматика; для заданной

нечеткой регулярной грамматики всегда возможно построить и -кратную нечеткие регулярные грамматики, которые эквивалентны исходной в частности, -кратную нечеткую регулярную грамматику можно трансформировать в -кратную нечеткую регулярную грамматику и наоборот.

Поясним алгоритм построения для -кратной нечеткой регулярной грамматики эквивалентной ей -кратной чечеткой регулярной грамматики Множество нетерминальных символов: где — новый начальный символ.

Множество правил подстановки Р формируется следующим образом. Для всех правил с начальным символом в левой части: или , новое правило имеет вид: или . Для каждой пары правил из которых нетерминальный символ в правой части одного правила совпадает с нетерминальным символом в левой части другого правила, новое правило имеет вид соответственно для правил из новое правило:

Функция степени принадлежности выводу определяется следующим образом:

Пример 7.4. Для -кратной нечеткой регулярной грамматики с правилами подстановки

и функцией степени принадлежности :

Эквивалентная ей 1-кратная нечеткая регулярная грамматика имеет правила подстановки Р:

и функцию степени принадлежности