§ 7.7. Нечеткие регулярные грамматики и автоматы

Приведем основные ре.эультаты о соотношении нечетких регулярных языков, нечетких автоматов и нечетких регулярных грамматик.

Рассмотрим нечеткий ограниченный автомат, у которого начальное состояние So четкое, F — четкое множество финальных состояний и о — функция из F в одноэлементное множество выходов {у}: a{Xj, г/)=1, если Xj^F и а{х^, у) = 0 иначе. Покажем [7]|, что нечеткий автомат А, определенный в § 7.5, эквивалентен нечеткому ограниченному автомату Ао, т. е. распознаваемые ими языки совпадают: S' (А) = S’ {Аа).

Пусть А = iU, X, Y, So, б, о>; тогда эквивалентный ему ограниченный автомат — следующий:

где и' = и\ Z' = X и jso, г/), s'„— новое начальное состояние, б' — новая функция переходов, определяемая следующим образом:

У = {г/'} — специально определенный выход.

Конечным состоянием автомата Ао определяем у.

Если задана входная последовательность Ѳ = UiUz ...щ, U; ѳ U, то функция выхода автомата А совпадает с выходом автомата А, так, как

В преобразованиях учитывалось то, что sj — четкое состояние и При к = 1 использовалось выражение для

6(so, а* у).

Утверждение 7.2 [15]. Для заданной нечеткой регулярной грамматики G существует НА А такой, что

и наоборот.

Приведем доказательство из [7].

а)   Пусть G = <Fr, Vn, S, Р, L, ф> — нечеткая регулярная грамматика, тогда соответствующий нечеткий автомат

где и = Ѵт, X = / и {5}, / — множество номеров правил подстановки из Р, Y = {г/} — любое одноэлементное множество, So — S —

четкое начальное состояние,—

множество конечных состояний.

Для любых Хі, Xj^X, a^U б (ж,-, а, Xj) = ср(р,), если либо Х{ —

номер правила подстановки А-^ЪВ и Xj — номер правила под-

Ѵ\

становки В-^а или В-^аС, либо Жі = 5 и номер правила

подстановки s^aA\ в противном случае ^{хі, а, Х)) — 0. Можно проверить, что любая последовательность переходов автомата из начального состояния в конечное состояние имеет ненулевое значение функции принадлежности (Хд(Ѳ) = So ° Гѳ ° тогда и только тогда, когда входное слово Ѳ порождается грамматикой G.

б)   Пусть Ao — W, X, У, So, б, F> — нечеткий ограниченный автомат. Эквивалентная нечеткая грамматика определяется следующим образом: Vt^U, Vn = X\F, S = So, P содержит правила подстановки вида xi~^axj тогда, когда б (ж,, а, а;з) = б(>0, и содержит правила подстановки вида х<-^а тогда, когда б (Ж;, а, х,) = = б;>0 и    (Хі может совпадать с начальным состоянием So)-

Так как в работе [27] доказано, что каждый регулярный язык, построенный на основе регулярных выражений, распознается не-

которым НА и любой НА распознает только такой НЯ, который порождается некоторым регулярным выражением, то справедливо фундаментальное соотношение

утверждающее, что множества языков, порождаемых нечеткими регулярными грамматиками, нечеткими регулярными L-выраже- ниями и распознаваемых нечеткими автоматами, совпадают.

В [29] получены аналогичные результаты для нечетких регулярных грамматик и нечетких автоматов с операциями «сумма» и «произведение».