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

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

Рассмотрим нечеткий ограниченный автомат, у которого начальное состояние четкое, — четкое множество финальных состояний и — функция из в одноэлементное множество выходов если и иначе. Покажем [7], что нечеткий автомат А, определенный в § 7.5, эквивалентен нечеткому ограниченному автомату , т. е. распознаваемые ими языки совпадают:

Пусть тогда эквивалентный ему ограниченный автомат — следующий:

где новое начальное состояние, — новая функция переходов, определяемая следующим образом:

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

Если задана входная последовательность то функция выхода автомата А совпадает с выходом автомата А, так, как

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

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

и наоборот.

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

а) Пусть — нечеткая регулярная грамматика, тогда соответствующий нечеткий автомат

где — множество номеров правил подстановки из — любое одноэлементное множество, четкое начальное состояние, — множество конечных состояний.

Для любых если либо — номер правила подстановки и — номер правила подстановки или либо и -номер правила подстановки в противном случае Можно проверить, что любая последовательность переходов автомата из начального состояния в конечное состояние имеет ненулевое значение функции принадлежности тогда и только тогда, когда входное слово 0 порождается грамматикой

б) Пусть — нечеткий ограниченный автомат. Эквивалентная нечеткая грамматика определяется следующим образом: содержит правила подстановки вида тогда, когда и содержит правила подстановки вида тогда, когда может совпадать с начальным состоянием

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

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

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

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