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

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

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

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

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

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

Утверждение 7.1. Если 2 — нечеткий КС-язык на тогда для некоторой максимально-взвешенной КС-грамматики удовлетворяющей следующим условиям:

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

б) для каждых предполагается

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

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

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

Приведенная максимально-взвешенная КС-грамматика называется финитарной КС-грамматикой, если для каждого и последовательности правил йодстановки со

Каноническая форма Хомского. является финитарным нечетким КС-языком тогда и только тогда, когда — Для некоторой приведенной КС-грамматики правила вывода которой имеют вид:

где .

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

где длина слова не более двух символов.

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

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

Определение 7.4. Пороговый язык для нечеткого языка на и для определяется следующим образом:

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

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

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

где — множество натуральных чисел. Отметим, что язык является КЗ-языком.

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

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

а) если типа то для любых типа ;

г) если типа то могут не быть типа .

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

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