О разложении и анализе обобщенных нечетких автоматов и языков

Сер. 10. 2009. Вып. 4

ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

УДК 519.71 В. А. Хохулина

О РАЗЛОЖЕНИИ И АНАЛИЗЕ ОБОБЩЕННЫХ НЕЧЕТКИХ АВТОМАТОВ И ЯЗЫКОВ*)

1. Введение. В теории нечетких множеств [1] показана возможность представления любого конечного нечеткого множества в виде дизъюнкции его уровневых четких множеств, умноженных на соответствующий уровень нечеткости. В теории вероятностных автоматов известен метод синтеза любого вероятностного автомата в виде детерминированного автомата со случайным входом, фактически представляющего собой объединение конечного числа детерминированных автоматов, каждому из которых сопоставлена некоторая вероятность его выбора [2]. Поэтому вполне очевидна целесообразность исследования подобной проблемы для случая нечетких автоматных моделей [3, 4].

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

Именно таким вопросам, применительно к так называемым обобщенным нечетким конечным автоматам, посвящена настоящая работа.

2. Основные определения. Будем рассматривать полную дистрибутивную решетку L =

a + b = max

условно называемыми «сложением» и «умножением», и обычным упорядочиванием. Условимся также обозначать £m,n множество всех (m х п)-матриц над L.

Если U = {z} есть некоторое универсальное множество элементов z G U, то обычное (четкое) подмножество Z С U можно задавать как множество упорядоченных пар Z = {(z, fj,z(z))}, z G U, где nz{z) = 1 при -г G Z и цг{%) = 0 при z G Z - характеристическая функция подмножества Z.

Хохулина Виктория Александровна — программист лаборатории математических проблем информатики математико-механического факультета Санкт-Петербургского государственного университета. Научный руководитель: действительный член РАЕН, доктор физико-математических наук, проф. М. К. Чирков. Количество опубликованных работ: 3. Научное направление: автоматное моделирование. E-mail: vakh08@mail.ru.

+ ) Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 07-01-00355).

© В. А. Хохулина, 2009

В отличие от четкого подмножества, нечеткое подмножество Z универсального множества и определяется как множество упорядоченных пар Z = {г,^z(г)}, где

степени принадлежности элемента г нечеткому подмножеству Z.

Нечетким языком Z в алфавите X называется любое нечеткое подмножество Z = {(w,^zV))}, V € X*, ^V) € [0,1], множества всех слов X* в этом алфавите. Иначе, нечеткий язык в алфавите X можно трактовать как однозначное отображение Z = |J>z : X* ^ [0,1]. Значение |J>z V) соответствует степени принадлежности слова V нечеткому подмножеству Z. «Пустой» язык Z условимся обозначать Z = 0.

Элементарными нечеткими языками в алфавите X = {х\, х2, ,хп} называют нечеткие языки Z = е («пустое» слово) и Z = х8, в = 1,п, определяемые соотношениями

Элементарные нечеткие языки обозначают (как и в обычной алгебре регулярных языков) символами е, Х1,Х2, , хп, однако в выражениях нечетких языков это нечеткие множества с функциями принадлежности (2).

Скалярным произведением элемента а € [0,1] и нечеткого языка Z называются нечеткие языки, обозначаемые соответственно а^ и Zа и определяемые следующими выражениями:

для всех V Є X* (далее в скалярном произведении будем символ пустого слова е опускать: ае = еа = а).

Дизъюнкцией нечетких языков Z\ и Z2 называется язык, обозначаемый Z = Z\ и Z2 и определяемый по формуле

для всех V € X*.

Произведением нечетких языков Zl и Z2 называется нечеткий язык, обозначаемый Z = ZlZ2 и определяемый выражением

для всех V € X*, где П - множество всевозможных пар слов (ш1,ш2) € X* таких, что Ш1Ш2 = V.

Итерация нечеткого языка Z обозначается Z* и определяется соотношением

для всех V Є X*, где П - множество всевозможных представлений V в виде последовательности конечного числа V, 1 ^ V ^ і, і = |и>|, непустых отрезков слова V = .

Всякий нечеткий язык, который может быть получен из элементарных нечетких языков с помощью конечного числа операций скалярного произведения, дизъюнкции,

цz (г) € [0,1] для всех г € и. Функция jлz(г) в этом случае называется функцией

при V = е, при V = е,

при V = х3, при V = х8.

МаяV) = тіп

МяV) = тах

НиV) = тах тіп

тах

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

Обобщенным нечетким конечным автоматом называют [4] систему

Af =

где X,A,Y есть алфавиты входов, состояний и выходов, \X\ = п, |А| = m, \Y\ = k; r € C1,m - начальный вектор-строка (степеней принадлежности состояний множеству начальных состояний); q € Cm>1 - финальный вектор-столбец (степеней принадлежности состояний множеству конечных состояний) и {F(x, y)}; F(x,y) € Cm’m, x € X, y € Y, есть совокупность матриц переходов (степеней принадлежности переходов состояний множеству различных переходов), задающая отображение X х Y ^ Cm’m.

Нечеткое отображение Фf : Xd х Yd ^ [0,1], d = 0,1, 2,..., индуцируемое нечетким автоматом Af, определяется функцией принадлежности

d

<^f

t=1

для всех (w, v) € Xd х Yd, d = 0,1, 2,..., и тем самым задает нечеткое подмножество пар слов одной, но сколь угодно большой длины, с функцией принадлежности (4).

В частном случае, когда дистрибутивная решетка C является булевой решеткой

C1 = ({0,1}, V, &, 1 > 0),

система (3) называется обобщенным недетерминированным автоматом [5]

And =

здесь вектор-строка начальных состояний d € Cl’m, вектор-столбец конечных состояний g € Cm’1 и {D(x, y)}, D(x,y) € Cm,m, x € X, y € Y, есть совокупность матриц переходов. Недетерминированный автомат A^ld индуцирует недетерминированное отображение $nd : Xd х Yd ^ {0,1}, d = 0,1, 2,..., определяемое выражением

d

$nd

t=i

где под «сложением» и «умножением» подразумеваются операции V и &.

Пусть задан обобщенный нечеткий конечный автомат Af (3) и выделено подмножество Y(к) С Y его выходных символов. Говорят, что нечеткий язык Z = j^z : X* ^ [0; 1] представлен в Af подмножеством Y(к), если для индуцируемого обобщенным нечетким автоматом Af нечеткого отображения (4) выполняется

У2 У2 ф

— — vEY* viE Y

vEY* ylEY(к) V^Y ’Vl^Y

для всех w € X*, где |w| = |vy^.

Соответственно недетерминированный автомат Лпй (5) подмножеством У(к) С У

выходных символов будет представлять четкий язык Z = |лz : X* ^ {0,1}, если для индуцируемого этим автоматом недетерминированного отображения (6) выполняется

Из теории автоматов известно [2, 4], что нечеткие автоматы представляют нечеткие регулярные языки, а недетерминированные автоматы - обычные (четкие) регулярные языки.

3. Разложение нечетких матриц. Рассмотрим конечное множество нечетких (тхт)-матриц¥(х,у] €Оп,т, х € X, у € У, ¥(х,у) = (Е^(х,у))т,т, Е^(х,у) € [0,1]. Учитывая конечность алфавитов Х,У и индексов г,], матрицы Е(х, у), х € X, у € У, содержат конечное число значений Е^(х,у). Обозначим множество таких различных значений, которые условимся называть уровнями нечеткости, как

В таком случае, согласно теории нечетких множеств [1], учитывая вид операций (1), каждую нечеткую матрицу Е(х, у) можно представить в виде «суммы» «произведений»

Выражение (11) будем называть разложением нечеткой матрицы Е(х,у) по различ-

Пусть теперь (и>,-у) есть любая пара слов длины ! > 0 в алфавитах Х,У, т. е. V = х31 х32 .. ,хВЛ, V = у^у12 .. ,у1Л, и рассмотрим «произведение» матриц вида

При каждом £ = 1, й для матрицы Е

уЕУ* у1еУ

матриц О*-1') (ж, у) на соответствующие уровни нечеткости V = 1, </:

9

О) 1—

ным уровням нечеткости , V = 1,д.

4

г=1

9

Для «произведения» матриц (12) справедливо следующее утверждение.

Лемма 1. Пусть Е(х84 ,у3ь), х8ь € X, у8± € У, есть нечеткие (т х т)-матрицы, каждой из которых соответствует ее разложение вида (13) по различным уровням нечеткости (9), тогда для любой пары слов (ад, V), ад = х31 х32 ... х3л, V = у;1 у\2 У1Л,

й =1, 2,.., «произведение» этих нечетких матриц (12) может быть представлено

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

ч

Е

и=1

где

d

Бм

г=1

Доказательство. Будем доказывать справедливость выражений (14), (15) индукцией по длине слов ад и V. При й =1 справедливость утверждения теоремы вытекает из выражения (13) при Ь =1. Предположим, что утверждение теоремы справедливо для слов длины Ь = й, т. е. при Ь = й выполняются соотношения (14), (15), и покажем,

что из этого следует справедливость разложения вида (14), (15) для слов адх, vy длины

Ь = й +1.

В соответствии с выражением (12) справедливо равенство

Е

и, следовательно, Е(адх, vy) есть нечеткая (т х т)-матрица, у которой, учитывая операции (1), все элементы принадлежат множеству уровней нечеткости (9), а в этом случае для нее должно существовать разложение типа (14) по различным уровням нечеткости

ч

Е

^=1

В таком случае остается необходимым доказать, что для матриц Б(^ (адх, vy) в выражении (17) выполняется соотношение типа (15), т. е. что

Бм

Согласно выражениям (11), (14), (16), должно выполняться

Е(адх^у)= (]Г Б(ш) (ад^)^) ПТ Б(а)(х, у)^) =

= 1 / \а = 1

ч ч

'Б(ш)^„ „,т(^)/„

]Т]ТБ

ш = 1а = 1

Из соотношений (17), (19), принимая во внимание принятую упорядоченность зна-

V

чений м/ , получаем, что м/ М/ = шт(^^ ,М/ ) = М/ тогда и только тогда, когда

а ^ ш = V или ш ^ а = V, а тогда

Б

Из выражения (20), учитывая, что элементы матриц Б(а)(х, у), Б(ш)(ю,у) удовлетворяют условию (10), следует, что

^Б

Б(^ (юх^у) = Б(и)(т,у)Б(и) (х,у)+Б(и) (т,у)Б(и) (х,у) = Б(и)(т, у)Б(и) (х,у),

т. е. оказывается справедливым выражение (18). Тем самым показано, что утверждения (14), (15) леммы 1 выполняются при любых ! = 1, 2,... .

4. Разложение нечетких автоматов. На основе леммы 1 очевидна справедливость утверждений, касающихся разложения нечетких отображений и нечетких автоматов. Поскольку для обобщенного нечеткого автомата (3) г € С1’™, q € С™’1, то, если считать, что множество уровней нечеткости (9) учитывает и элементы векторов г и q, эти векторы можно представить в виде разложений

гМ ,,м

v=1 v=1

где с!^ - это т-мерный вектор-строка, а g('гУ-) - т-мерный вектор-столбец, V = 1,д, с элементами

,( V) I 1 при гг > №, (V) \ 1 при Чг > /Г)Г),

' = 1 п ^ [*) дг ) = 1 п ^

^ 0 при гг < / , [0 при чг < / .

В таком случае, с учетом выражения (4) и леммы 1, оказываются справедливыми следующие утверждения.

Лемма 2. Нечеткое отображение Ф/, индуцируемое обобщенным нечетким автоматом (3), может быть записано как разложение

Ф/ = ЁфПМ" ),

= 1

в котором Ф^1, V = 1, </, есть недетерминированные отображения Ф^1 : Ха х —> [0,1], ! = 0,1,..., такие, что

жМ, ч Г а( 1,)Б( 1,) (w,v)g( 1,) при !> 0,

<<(».»> = { а("^(;-) при ! = <>,

где а( ,'), б(1/) ( ю,у), g( 1/) определяются выражениями (15), (22).

Теорема 1. Обобщенный нечеткий автомат А/ (3) может быть представлен в виде разложения

а, = £ а

V=1

АV = 1,ч, есть обобщенные недетерминированные автоматы

А£ = X, а, у, аЧ {б(^(х,у)}, g(v)),

и

а суммирование в (24) означает, что векторы г, q и матрицы ¥(х,у) автомата Af определяются по формулам (21), (22), (10), (11).

5. Метод абстрактного анализа автомата. Задача абстрактного анализа заданного автомата Af (And) с заданным подмножеством выходных символов У<к) состоит в нахождении регулярного выражения языка, представленного в этом автомате подмножеством У<к). Один из вариантов процедуры решения данной задачи для обобщенного нечеткого автомата Af состоит в следующем [4, 6]:

1) построить матрицу прямых переходов автомата

п / к \

й =и !>

8=1 \ 1=1 /

где

пп

(хв)хв ( ПШХ (х8,У1)\ хв ;

в = 1 в = 1 ' '

2) найти финальные векторы для в = 1,пс помощью выражения

q

У1 еУ

3) составить и решить систему

^ и ГЬ 3 = !> т>

и определить Zj для всех ], для которых найдется хотя бы одно значение в, такое,

что ъ (в) = 0;

4) получить регулярное выражение нечеткого языка 2 по формуле

п т

2 = и UZj ^

Я=1j=1

Процедура абстрактного анализа автомата А^ (5) аналогична процедуре анализа

автомата Af с учетом изменения обозначений элементов автомата и операций.

6. Разложение нечетких регулярных языков. На основе леммы 2, теоремы 1 и выражений (7), (8) оказывается справедливым следующее утверждение.

Теорема 2. Пусть обобщенный нечеткий конечный автомат Af (3), приведенный в виде разложения (24), представляет подмножеством У<к) С У нечеткий регулярный язык Zf, а недетерминированные автоматы АV = 1,</, представляют подмножеством У<к) регулярные языки V = 1, тогда справедливо разложение

~ 4 ~

Zf = и 2<")М<1')

^=1

Доказательство. Пусть т = х81   х8ь, ъу\ = У\1  У1ь-1 Уи тогда, воспользовавшись выражением (23), получим

(Ю,УУ1 ) = ф<пс1(ш,уУ1 )м{f),

и=1

откуда, после «суммирования» левой и правой частей этого равенства по V € У * У1 € У<к), имеем

^ ^ (™^У1 )= ^ ^ ф<П](ш,Щ1)] М^^

уЕУ* у1еУ(к) ^=1 ^ уЕУ* у1еУ(к) '

Далее, учитывая выражения (7), (8), следует, что для языков ^ и V = 1, </,

9

М2}

V=1

Полученное выражение (30) непосредственно подтверждает справедливость разложения (29). Теорема доказана.

Рассмотрим Л € [0,1] такое, что для некоторого п €{!,,?}

м/п) ^ Л > м/ 1),

и будем рассматривать регулярный язык 2^\, соответствующий языку уровня Л в нечетком регулярном языке Zf. С учетом того, что для языков V = 1, </, согласно принятой упорядоченности уровней нечеткости (9), выполняется

2<9) с 2<9-1) с  с 2<1),

вытекает справедливость следующих двух утверждений.

Следствие 1. Регулярное выражение языка может быть получено из регу-

Z <1) <п-1)

лярного выражения нечеткого языка 2/ путем замены в нем скаляров м/ ,, М/

на пустой язык 0, а скаляров м/1^,    , М/9) на 1.

Следствие 2. Регулярное выражение языка может быть получено путем абстрактного анализа недетерминированного автомата .

7. Специальный абстрактный анализ нечеткого автомата. Задача специального анализа обобщенного нечеткого автомата Af (3) с заданными подмножеством выходных символов У<к) и уровнем нечеткости Л (31) состоит в нахождении регулярного выражения языка 2\, представленным в автомате Af подмножеством У< к) с уровнем нечеткости не менее чем Л. В соответствии со следствиями 1 и 2 могут быть предложены два метода решения этой задачи.

Первый метод состоит в абстрактном анализе нечеткого автомата Af, построении нечеткого регулярного выражения языка Zf и использовании следствия 1.

Второй метод состоит в соответствии со следствием 2 в абстрактном анализе недетерминированного автомата Anl,l), построенного с учетом условия (31), согласно выражениям (9), (10), (21), (22).

8. Пример. Рассмотрим нечеткий автомат Af (3), где X = {х1, х2}, А = {а,1, а,2, аз},

F(xl,Уl) =

F

0), Т q1 = ю

/0.2 0 0 \

0 0.3 0

0 0 0.4/

/0.4 0 0\

0 0.6 0 ,

0 0.7 0

0.6 0 0

0.5 0 0

0 0 0.2.

0.3 0 0\

0 0.5 0

0.3 0.2 0

Требуется найти регулярное выражение языка ^0.5, включающего в себя все слова V € X*, уровень принадлежности которых нечеткому языку 2, представленному в автомате А/ подмножеством У<к) = {У2}, удовлетворяет условию М2<ш) ^ 0^5.

Используя первый метод, выполняем абстрактный анализ нечеткого автомата А/ . Согласно процедуре, изложенной в п. 5, последовательно получаем

1. Матрицу прямых переходов

/ 0.6*1 и 0.4х2 0 0 \

8 = I 0.5ж1 0.3ж1 и 0.6х2 0 I

\ 0.3х2 0.7х2 0.4ж1 )

2. Финальные векторы

q(1) = (0^5; 0^5; 0^2)Т, q(2) = (0^3; 0^5; 0^2)Т

3. Систему уравнений

21 = 21(0.6x1 и 0^4x2) и 220^5x1 и 2з0.3х2 и 0^4,

22 = 22(0^3x1 и 0^6x2) и 2з0 7x2 и 0^7, = 2з0^4х1

и ее решения

23 = 0, 22 = 0  7(0  3х1 и 0  6х2)*, 21 = (0  5(0  3х1 и 0  6х2)*х1 и 0  4)(0  6х1 и 0  4х2)*^

4. Регулярное выражение нечеткого языка 22

22 =

5. Искомое регулярное выражение языка 2о.5

2^0.5 = х2

Теперь для сравнения воспользуемся вторым методом, использующим разложение автомата А/ по уровням нечеткости. Для этого найдем недетерминированный автомат Ап,а = (X, А, У, а, {В(х8,У;)}, g}, заменив в автомате А/ в г, F(s,/) и q все числа, меньшие 0.5, на 0, а все числа, большие или равные 0.5, на 1, и удалив недостижимое состояние аз, таким образом, получим а = (0; 1), gT = (1; 1),

В(х1 ,У1)= (° , Б(х1 ,У2)= ^ 0

х0 оу ^ 0

0(х2,уі)= (0 ^ , Б(х2,у2)= 1

Далее производим абстрактный анализ недетерминированного автомата Лай • В результате последовательно находим

8=(х «), (1)=(!), *(2)=(1,

Zi = Z\x\ U Z2X1, Z2 = Z2X2 U e, Z2 = x2, Zi = X2xix*,

Z0.5 = x2xix1 xi U x2(xi U X2) = x2(xixl U X2).

Таким образом, второй метод решения задачи поиска языка, представленного в автомате Af с заданным уровнем нечеткости, оказывается в этом случае существенно менее трудоемким, чем общий метод.

9. Заключение. В работе доказано, что любой обобщенный нечеткий конечный автомат Af может быть представлен в виде дизъюнкции («суммы») обобщенных недетерминированных конечных автоматов *4^, v = l,q, соответствующих различным уровням нечеткости MfV), а любой нечеткий регулярный язык - как объединение регулярных языков, соответствующих разным степеням принадлежности исходному языку. Установлена связь такого разложения нечеткого регулярного языка с соответствующим разложением обобщенного нечеткого автомата, представляющего этот язык, на основе чего сформулирован специальный метод абстрактного анализа обобщенного нечеткого автомата для заданного уровня нечеткости.

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

Литература

1. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982. 432 с.

2. Чирков М. К., Пономарёва А. Ю. Стационарные детерминированные и вероятностные автоматы: Теория автоматных моделей. СПб.: Изд-во С.-Петерб. ун-та, 2008. 248 с.

3. Kandel A., Lee S. C. Fuzzy Switching and Automata: Theory and Applications. New York: Crane Russak & Comp. Inc., 1979. 303 p.

4. Скорикова Я. И., Чирков М. К. Абстрактный анализ обобщенных нечетких автоматов // Математические модели. Теория и приложения. Вып. 6. СПб.: ВВМ, 2005. С. 110—122.

5. Пономарёва А. Ю., Сандрыкина Н. В., Чирков М. К. Оптимизация абстрактной структуры недетерминированных автоматов // Математические модели. Теория и приложения. Вып. 3. СПб.: Научн.-исслед. ин-т химии С.-Петерб. ун-та, 2003. С. 94—102.

6. Чирков М. К., Кабаве М. Абстрактный анализ обобщенных конечных автоматов // Теория и приложения дискретных систем / под ред. М. К. Чиркова, С. П. Маслова. СПб.: Изд-во С.-Петерб. ун-та, 1995. С. 3—36.

Статья рекомендована к печати член-кор. РАН, проф. Г. А. Леоновым.

Статья принята к печати 28 мая 2009 г.