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

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

где Vn — множество нетерминальных символов; Ѵт — множество терминальных символов; S—начальный символ 5 е Fj?; Р — конечное множество правил подстановки вида и~^ѵ, и, s(FjfUFi.)*, р^Р', L — множество весов (например, дистрибутивная решетка с О и 1); ф: Р ^ L, ці{р) — степень принадлежности выводу правила р^Р.

Далее множество всех терминальных и нетерминальных сим< волов будем обозначать F = Ft U Fw.

Нусть задана грамматика G; и, V*. Говорят, что и непосредственно порождает ѵ со степенью ф,, если найдутся такие

 

Фх

что и = utxui, V = uiyut, х-^у. Это обозначаем как и~^ ѵ или

ф(р) и—^ V. р

Пусть и, V, Zo, ..Zm е V*. Последовательность z», ..z„ называется выводом {цепочкой вывода) и ѵіз ѵ, а ѵ выводимой из и в грамматике G, если существует последовательность подстановок из Р:

Выводимость г; из U в грамматике О обозначаем и^ ѵ, В общем случае может существовать более одной цепочки вывода. Если и = S, V — X, X е Ѵт, то говорят, что S порождает терминальную цепочку V посредством подстановок р„ ..., р™.

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

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

Множество правил вывода Р и функция ф определяют нечеткое бинарное отношение R-. V* XV* L.

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

и операции М, * обладают свойством дистрибутивности на L, то степень выводимости а; из 5 вычисляется по следующей формуле:

где у* = {у,, ..., уп) — множество цепочек вывода.

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

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

где а + р = 1; Gi, — пессимистическая и оптимистическая НГ.

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

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

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

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

Дробные НГ использовались при грамматическом разборе в процедуре распознавания образов. В [33] и.эучаются древовидные

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

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

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

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

Две НГ G, и Gj называются эквивалентными тогда и только тогда, коща для любого х еѴ*

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

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

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

ф(р)

эквивалентной G, у которой нет правил вида А —>- В; А, В ^

S Vn- Во-вторых, построение грамматики G2, эквивалентной G,, у которой нет правил подстановки вида:

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

Пример 7.1. Рассмотрим нечеткую пессимистическую КС- грамматику с алфавитами Fj. = {а, Ь), Vf, = ^A, В, S} и правилами подстановки, приведенными в табл. 7.3. Этапы построения канонической формы Хомского проиллюстрированы в табл. 7.3. При построении Gc добавлены нетерминальные символы С,, Сг, D.

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

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

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

Во-вторых, все правила подстановки приводятся к виду: Аі -V Ajj, 'Y ^ V*, i ^ i. Это выполняется следующим образом. Пусть для к нетерминальных символов {к ^ і) правила подстановки имеют вид: Аі А,а, j > і, тогда правило подстановки AjCi,

в котором ]<к+1, используя правило с левой частью Aj, приводится к виду Ak+i^Aia, 1>к + і. Если l = k+l, то вводится новый нетерминальный символ Zk+i и правила подстановки приобретают вид;

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

Если G — нечеткая пессимистическая КС-грамматика и Л Аа,і,    i = l, ..г; у = 1, ..s —множества правил под

становки такие, что А е Ѵ^; а., е F*, то грамматика, полученная заменой правил    правилами

для которых

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

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

Пример 7.2. Пусть дана нечеткая пессимистическая КС- грамматика G в канонической форме Хомского с алфавитами Ѵт — {а, Ь, с}, Vn = {S, а, в. С). Этапы построения канонической формы Грейбаха проиллюстрированы в табл. 7.4.

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

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

где Fjf, Fj, Р, S, L обозначают то же, что и в определении 7.2, а

Фі = Ф Ри • • •; Рі) = ф(Р1 Ри ■ ■ ■, Рі) — степень использования правила р при условии, что перед р были использованы правила Рі, ..., Рі.

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

и

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

Если к> п и к = п + ]', тогда степень принадлежности вычисляется по формуле

Пример 7.3. Приведем 1-кратную НГ G^, предложенную в [17]. Пусть Ѵп = {А, В, С, S}, Ѵт = {а, Ь, с}, фо —    ЛSC) =

= 0,9. Правила подстановки грамматики и значения фі(РіІРі) приведены в табл. 7.5. В пустых клетках таблицы предполагаются: значения из интервала [О, 0,65].

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

В грамматике G, возможны и другие выводы этого слова. Степень принадлежности выводу последовательности подстановок а) равен 0,7, а последовательности подстановок б) 0,8. Можно» проверить, что степень вывода    0,8.

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

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

нечеткой регулярной га-кратной (п>1) грамматики всегда возможно построить (га + 1)-кратную и (га — 1)-кратную нечеткие регулярные грамматики, которые эквивалентны исходной НГ, в частности, 1-кратную нечеткую регулярную грамматику можно трансформировать в 0-кратную нечеткую регулярную грамматику и наоборот.

Поясним алгоритм построения для га-кратной нечеткой регулярной грамматики G„ = <Fw, Ft, Р, S, L, {ф», ..., ф„}>, га ^2, эквивалентной ей (га — 1)-кратной чечеткой регулярной грамматики Gn-i = <F^, Ft, Р', S',. L, {h^, ..., Л„-]}> [17]. Множество нетерминальных символов; F„ = {і ] pj е Р} U S', где S' — новый начальный символ.

Множество правил подстановки Р' формируется следующим образом. Для всех правил рі^ Р с начальным символом S в левой части; рі\ S аА или pt: S ^ а, новое правило имеет вид; Рой S' аі или Рой S' -*■ а. Для каждой пары правил из Р: рі^. Ai^-^aAj^^ рі^. а'Л, у которых нетерминальный сим

вол в правой части одного правила совпадает с нетерминальным символом в левой части другого правила, новое правило имеет вид и соответственно для правил из Р\ Рі^. Л-ѵ

А' -^а^, новое правило;

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

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

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

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

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

МРоі) = фо(Рі)= 1,

ht (pl2\po,) = Фі (РгІРі) = 0,8,

hi (р2ъ I pa) = ф2 [рь I Рфг) = 0,7,

ht (p23\pi2) = УіІРзІРіРі) = 0,6, hi (p3i I p23) — ф2 (pjpips) = 0,6, hi (pi21 Pu) = фг {рг I РзРі) = 0,6, hi (p2b I Рьг) = фг (рь I РіРг) = 0,6,

МР23ІР42) = ф2(рз1р4р2)= 0,6.