§ 7.5. Определение нечеткого автомата

Рассмотрим один из типов нечетких автоматов (НА), играющий важную роль в изучении НЯ. Будем считать, что автомат допускает слово некоторого НЯ, если при подаче на вход автомата последовательности сигналов, соответствующей анализируемому слову, НА генерирует выходной сигнал, указывающий на степень принадлежности данного слова нечеткому языку. Таким образом автомат может распознавать НЯ.

Определение 7.6 [7, 19]. Нечетким конечным автоматом называется упорядоченная шестерка

где и ~ {а,, ..., am) — конечное множество входов, X = {ж,, ... ..., Хп) — конечное множество состояний, У = (г/,, ..., ур) — конечное множество выходов, б: XXUXX-^L — функция перехо-

дов, о: XXY L — функция выходов, So — нечеткое начальное состояние So е ^2 (X) (so: Z L).

В определении 7.6 функция б порождает множество нечетких матриц переходов (Г„)„=[/= (и)j, 1 ^ ц j^n, функция о порождает нечеткую матрицу выхода

Из определения НА следует ряд классических определений. Например, если б: XX С/XX-*-(О, 1} и из некоторых состояний Хо^ X возможен переход в несколько состояний Xt, ..., Хг^Х, то это автомат недетерминированный. Если для любого гѳ{1, ..п} существует единственное /г^(1, ..., ге) такое, что

то это детерминированный автомат.

Пусть и* — множество всевозможных входных последовательностей, тогда функция переходов б: XXU*XX-^ L вычисляется следующим образом:

где Q = Ui, uz... Uk^ и'‘, Q Ф X.

Аналогично определяется матрица переходов:

Если на вход нечеткого автомата А подается последовательность Ѳ, то выход автомата вычисляется следующим образом:

Рассмотрим специальный вид НА, у которого единственный выход ¥ = {уо). В этом случае нечеткий выход определяется вектором Оі=((іі, ..., (Aft), где (Хі указывает на степень получения в состоянии Хі выхода г/о.

Можно ввести еще более специальный тип НА, определяя множество финальных (заключительных) состояний   и функцию выходов

Если еще предположить, что начальное состояние четкое Хо ^ X, т. е.

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

Различные типы автоматов могут быть определены в зависимости от множества оценок L и операций, используемых в формуле вычисления функции переходов (см. табл. 7.6).

Если в качестве множества входов U рассматривать множество терминальных символов Ft, то функция отклика нечеткого автомата задает нечеткий язык S{Vt) в алфавите Ѵт- В этом случае говорят, что автомат А распознает язык S' = S{A). Следующий пример иллюстрирует возможность построения НА, распознающего язык, порожденный регулярной грамматикой.

Пример 7.7. Рассмотрим регулярную НГ с алфавитами Ѵт = = (а, Ъ), Fn = {5, а. В) и правилами подстановки

Грамматика G порождает НЯ 2’аь = {(а6, 0,8), ((аЬ)”, 0,6), п = = 2, 3, ...}.

Нечеткий автомат А, распознающий язык 2’оь, строится следующим образом:

Диаграмма переходов синтезируемого автомата, приведена на рис. 7.2. Если на вход автомата подать слово аЬ, то выход вычисляется следующим образом:

Если на вход автомата подается слово abab, то

Аналогично вход вычисляется для любого слова (аЬ)", п = 3, 4, ...

Следовательно, построенный автомат распознает язык З’аь-

Покажем, что слово аЪа, не принадлежащее языку З’аь, автоматом не распознается:

Приведем некоторые свойства распознавания нечетких языков нечеткими автоматами [10, 14, 19—21, 27—29].

Замкнутость относительно операции объединения. Пусть Аі, А2 — нечеткие автоматы, тогда существует автомат А = A,U А2 такой, что

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

Замкнутость относительно операции пересечения. Пусть Аі и Аг — нечеткие автоматы, тогда существует НА А ~ Аі® Аі такой, что

Автомат А определяется следуюпщм образом:

Существование автомата А. Для любого НА А существует автомат А такой, что S{A) — S'{A). Автомат Л является минимаксным автоматом:

где“— min max — композиция вместо композиции max min.

Распознавание конкатенации языков. Если А, и Аі нечеткие автоматы, то существует автомат Л    рас

познающий конкатенацию языков:

Распознавание замыкания Клини. Для любого НА А существует автомат А, распознающий замыкание Клини:

В [19] определены достаточные условия для распознавания нечетким автоматом нечеткого языка, который является своим собственным замыканием Клини:

а) если для любого а е [7 и любого Хі^Х

тогда S’(Л) —замкнутый язык, т. е. 5’(Л) = 5’(Л). Из-за краткости доказательства приведем его полностью:

Так как ба рефлексивна и Гѳ также рефлексивна для каждого Ѳ е и*, то Геѳ' == Гѳ ° Гѳ' Э Гѳ и, следовательно.

Распознавание пороговых языков. Пусть S{А, а) — пороговый язык нечеткого языка S {А), распознаваемого нечетким автоматом А:

тогда для любого ао ^ [О, 1) существует НА А^ такой, что