Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 7.2. Нечеткие грамматики и их свойстваОпределение 7.2 [16, 19]. Нечеткая грамматика — это шестерка
где Далее множество всех терминальных и нетерминальных Пусть задана грамматика
что Пусть
Выводимость Наличие степени принадлежности выводу правил из Р требует введения определенных способов вычисления степени принадлежности выводу цепочки правил подстановки и степени выводимости некоторой терминальной цепочки из Учитывая это, нечеткие грамматики (НГ) могут быть классифицированы как по способу вычисления степени выводимости, так и по виду правил подстановки. Множество правил вывода Р и функция Следовательно, определение операции композиции отношений
и операции
где В [16] приведены различные способы определения операций В [16] определяется также смешанная НГ
где Далее, на протяжении всей главы, если не оговорено особо, под НГ будут подразумеваться пессимистические НГ. Наряду с грамматиками, приведенными в табл. 7.1, известны другие типы грамматик. В [8] исследована дробная степень выводимости вычисляется по формуле:
где k — индекс цепочки подстановок, порождающей слово
Дробные НГ использовались при грамматическом разборе в процедуре распознавания образов. В [33] изучаются древовидные грамматики, в которых дополнительно используется отображение Таблица 7.1 (см. скан) При анализе грамматик существенную роль играют свойства рекурсивности и эквивалентности. НГ называется рекурсивной тогда и только тогда, когда существует алгоритм вычисления Таблица 7.2 (см. скан) составляющих, т. е. таких грамматик, у которых правила подстановки и Две Для нечетких КС-грамматик, как и для четкого случая, возможно построение канонических форм Грейбаха и Хомского. Каноническая форма Хомского. Нечеткая пессимистическая КС-грамматика эквивалентна некоторой
Каноническую форму грамматики в [12] предлагается конструировать в три этапа. Во-первых, построение грамматики
В-третьих, построение грамматики Пример 7.1. Рассмотрим нечеткую пессимистическую КС-грамматику с алфавитами Каноническая форма Грейбаха [12]. Нечеткая пессимистическая КС-грамматика эквивалентна некоторой
Конструирование канонической формы осуществляется следующим образом. Во-первых, строится каноническая форма Хомского. Все нетерминальные символы в канонической форме Хомского перенумеровываются: Таблица 7.3 (см. скан) Во-вторых, все правила подстановки приводятся к виду:
При преобразовании используется следующая лемма: Если
для которых
эквивалентна грамматике В-третьих, правила подстановки преобразуются к такому виду, чтобы их левые части начинались с терминальных символов. Пример 7.2. Пусть дана нечеткая пессимистическая КС-грамматика Часто бывает естественным конструирование грамматик, в которых степень правильности использования правила подстановки зависит от ранее использованных в цепочке вывода правил подстановки. Такой тип грамматик, названный Определение 7.3. Нечеткая
где
Если имеется цепочка вывода
и
(кликните для просмотра скана) то цепочка вывода примет вид:
Если
Пример 7.3. Приведем Таблица 7.5 (см. скан) Приведем примеры вывода слова
В грамматике а) равен 0,7, а последовательности подстановок б) 0,8. Можно» проверить, что степень вывода Из определений 7.2 и 7.3 следует, что В [17] доказаны следующие свойства нечеткой регулярной Поясним алгоритм построения для Множество правил подстановки Р формируется следующим образом. Для всех правил Функция степени принадлежности выводу определяется следующим образом:
Пример 7.4. Для
и функцией степени принадлежности
Эквивалентная ей 1-кратная нечеткая регулярная грамматика имеет правила подстановки Р:
и функцию степени принадлежности
|
1 |
Оглавление
|