§ 7.3. Порождение языков нечеткими грамматиками

Говорят, что нечеткий язык

2* = [(и, \ig(u)y. ueFj, ц^(и)>0),

является языком, порождаемым грамматикой, если существует нечеткая грамматика G = <FW, FT, Р, 5, L, ф> такая, что

и, це(м) =

Грамматика G называется грамматикой, порождающей нечеткий язык S. Тип языка определяется типом порождающей грамматики. В [23] исследован ряд вопросов соотношения нечетких языков и максимально-взвешенных грамматик, в частности, условия представления в канонических формах Хомского и Грейбаха.

Пусть — совокупность всех конечных неотрицательных действительных чисел такая, что — &+ U {°°}.

Тогда финитарным нечетким языком S назовем нечеткое подмножество Vт с функцией принадлежности

Hg,: Fr->^+.

Утверждение 7.1. Если 2 — нечеткий КС-язык на Ѵт, тогда S(VT) = S(GT) для некоторой максимально-взвешенной КС-грамматики Gr = <FA., Ѵт, Р, S, 5?+, ф>, удовлетворяющей следующим условиям:

а)   начальный символ S не появляется в правой части правил

ф(р)

подстановки А —► иеР; р

Фі   Ф2

б)   для каждых А е= VN, а е Ѵ*,А -^аеР, /(-’■аеР предполагается фі = фг, > 0;

в)   для каждого А е VN существуют [i,veFj и последовательность правил подстановки

со: S =>- цЛѵ, (1 (S' =>- > 0;

СО   \ (О )

9? = 9? (G) = |(и, (и)): S =>-

г) для каждого существует а е и последователь

ность правил подстановки

Грамматика Gr называется приведенной максимально-взвешенной грамматикой.

Приведенная максимально-взвешенная (MB) КС-грамматика называется финитарной МБ КС-грамматикой, если для каждого е Fjv и последовательности правил йодстановки со   1.

Каноническая форма Хомского. S является финитарным нечетким КС-языком тогда и только тогда, когда

= И'й Д-^ія некоторой приведенной MB КС-грамматики G, правила вывода которой имеют вид:

где Л, В, С е Vn, а е Ѵт.

Каноническая форма Грейбаха. S' является финитарным нечетким КС-языком тогда и только тогда, когда

= fig для некоторой приведенной максимально-взвешенной КС-грамматики G, правила вывода которой имеют вид:

где A^Vn, длина слова y не более двух сим

волов.

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

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

Определение 7.4. Пороговый язык S{Si, %, >) для нечеткого языка Si на Ѵт и для  определяется следующим образом:

Аналогично определяются языки:

Каждой нечеткой порождающей грамматике аналогичво ставятся в соответствие пороговые языки.

Пример 7.5. Для 1-кратной нечеткой КС-грамматики, приведенной в табл. 7.5, пороговыми языками являются:

где N — множество натуральных чисел. Отметим, что язык S{G, 0,65, >) является КЗ-языком.

Для пессимистических грамматик число пороговых языков каждого из перечисленных типов конечно и зависит от числа различных оценок правил подстановки.

Для любой нечеткой пессимистической грамматики G, номер типа которой і приведен в табл. 7.2, в [15] доказано следующее:

а)   если G типа і {і = 0, 1, 2, 3), тр для любых X S{G, Я,, >) типа і;

б)   если G типа і (г = 0, 3), то S'{G, X, типа і;

в)   если G типа і (і — 3), то S(G, Xt, Х^) и S{G, X, =) типа i\

г)   если G типа i {i = 0, 2), то S(G, Xt, Xz) и S{G, X, =) могут не быть типа i.

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

В [24] были исследованы максимально-взвешенные регулярные грамматики. Установлено, что они являются более общими, чем пессимистические грамматики в том смысле, что порождают нерегулярные языки.