Размещено на http://www.allbest.ru/

Саратовский государственный социально-экономический университет

ОБ ИДЕНТИФИКАЦИИ АВТОМАТОВ КОНЕЧНЫМИ СЛЕДАМИ

С. А. Богомолов

Саратов, Россия

Одним из основных принципов в теории систем является принцип единственности на основе понятия изоморфизма. Этот принцип был введен в работе Р. Е. Калмана [1], в которой отмечается, что в задаче реализации (моделирования) для достаточно полных данных существует единственная модель в том смысле, что все модели, объясняющие данные, изоморфны друг другу. Там же приведены примеры, в которых единственность модели трактуется в смысле изоморфизма всех минимальных моделей, но минимальность подразумевает конкретное значение параметра. Под реализацией в [1] понимается система (модель), воспроизводящая данные и рассматривается как точное описание механизма, порождающего данные. Одним из важнейших понятий, относящихся к принципу единственности, является понятие «минимальности» системы и, несмотря на то, что проверяемые условия минимальности системы приведены, но самого определения в работе нет. Исходя из понятия системы, определенной на входном и выходном объектах, можно прийти к различным ее динамическим реализациям и различным пространством состояний. Поэтому практический интерес представляет задача отыскания «наименьшего» (в определенном смысле) пространства состояний и построение процедуры, позволяющей конструировать такое пространство на основе первоначальной информации о системе. Среди всех динамических реализаций необходимо выделить те, которые обладают некоторыми особыми свойствами и особенно те, которые, в определенном смысле, являются «простейшими» или «наименьшими». Поскольку динамика поведения системы описывается в терминах изменения ее состояний, минимальность реализации системы должна подразумевать минимальность самого пространства состояний; в теории автоматов реализация автомата считается минимальной, если минимальна мощность его пространства состояний (множества состояний автомата). Кроме того, в работе [1] приведен принцип неопределенности, согласно которому неточным (недостоверным) данным соответствует неединственная (недостоверная) система. Таким образом, для единственности представления системы необходимы полные и точные данные. В общеметодологических работах этот принцип связывается с тем, что каждая используемая модель системы должна доопределяться внешним образом с целью достижения ее единственности.

Решение задачи построения математических моделей динамических дискретных систем на основании данных наблюдений их поведения составляют предмет теории идентификации систем, которая является одним из основных элементов научной методологии. Под структурной идентификацией понимают процедуру построения оптимальной в определенном смысле математической модели системы по реализациям ее входных воздействий и выходных компонент. В настоящей заметке термин «идентификация» используется только применительно к уровню математических моделей, то есть в узком смысле, а именно в качестве моделей рассматривается важный класс дискретных систем - конечные автоматы, поведение которых определяется конечной совокупностью попарно различных ограниченно - детерминированных функций (о. - д. функций), реализуемых в автомате [2]. Задачи идентификации непосредственно связаны с проблемой синтеза (восстановления диаграммы переходов [2]) автомата, заданного некоторым описанием его поведения или условиями функционирования, обладающего заранее определенными свойствами. Целью работы является изучения отношения «автомат - информация о поведении автомата», позволяющего описать внутреннюю структуру автомата (например, диаграмму переходов [2]) с заданной степенью точности.

Так как проблема структурной идентификации автомата непосредственно связана с единственностью представления автомата посредством информации о поведения, то следует более подробно рассмотреть возможность и условия единственности восстановления автомата, заданного (конечной) информацией о его поведении. Проблема единственности решения в теории дискретных систем, как одна из важных проблем рассматривалась в работе [3]. Анализируя процессы постановки и решения основных задач теории дискретных систем, обнаруживается одна общая и весьма важная черта для всех этих задач: подавляющее большинство задач теории дискретных систем изначально или путем последовательных уточнений постановок доопределяется таким образом, что каждая из них имеет единственное решение. Почти всегда наличие нескольких альтернативных решений воспринимается как неокончательный результат. Формально это означает, что вся совокупность сформулированных условий представляет собой условие единственности решения соответствующей задачи. Понятие идентификации автомата непосредственно связано с вопросом о единственности представления данного системного описания в рамках модельной структуры. Таким образом, в рамках теории автоматов задача идентификации внутренней структуры автомата формулируется следующим образом: по заданному автомату и имеющийся информации о его поведении, определить условия, налагаемые как на автомат, так и на заданное поведение, позволяющие идентифицировать автомат на основании предложенного поведения.

В сообщении под автоматом понимается конечный детерминированный автомат Мили A = (S, X, Y, д, л), где Х={x,…,x}, Y ={y,…,y} - входной и выходной фиксированный алфавиты (m?2, p?2); S = {s1,…, sn} - конечное множество состояний, д: S Ч Х > S и л: S Ч Х > Y - функции переходов и выходов автомата соответственно. Области определения функций переходов и выходов совпадают. Через X* и Y* обозначим множества всех конечных слов в алфавитах X и Y соответственно. Функции д и л обычным образом [2] распространяются на область определения SЧХ* со значениями соответственно в S и Y*. Множество всех автоматов с входным X и выходным Y алфавитами обозначим через K(U), где U = XЧY. В качестве поведения автомата, рассматривается конечное множество попарно различных ограниченно - детерминированных функций (о. - д. функций) [2] в нем реализуемых. Пару слов одинаковой длины (б,в) = (х,…, х,y,…,y), бX*, вY* назовем вход - выходным словом, допустимым автоматом A в состоянии sS, если выполняется л(s,x,…, x) = y,…,y. Множество всех вход - выходных слов, допустимых автоматом A в состоянии s, обозначим

Через Щ(U) обозначим множество всех о.-д. функций, отображающих X* в Y*. Пусть - F={f1,…fn} - конечное множество о.-д. функций из Щ(U). Будем говорить, что автомат AK(U) реализует множество F , если для любого i{1,…n} существует состояние sSA такое, что fi = цs. Через K(F) обозначим класс автоматов из K(U), реализующих множество F. Автомат AK(F) строго (в точности) реализует множество F, если A реализует F и не реализует никакие о. - д. функции из Щ(U), не принадлежащие множеству F. Через KC(F) обозначим класс автоматов из K(F), строго реализующих множество о. - д. функций F. Автомат AKC(F) назовем «не избыточным» неприводимым (относительно строгой реализации F) автоматом класса KC(F), если любой его гомоморфный образ [2]не принадлежит KC(F).

Утверждение 1. Класс KC(F) содержит единственный (с точностью до изоморфизма) неприводимый автомат из K(U).

Очевидно, что множество автоматов из K(F) строго реализующих множество о.-д. функций F, образует класс эквивалентности автоматов [2], среди которых существует единственный приведенный автомат с минимальным числом состояний [2], который и является неприводимым в классе KC(F). Это множество автоматов является собственным подмножеством класса K(F). Рассмотрим строение класса K(F) для произвольного конечного множества о.-д. функций F Щ(U). Класс K(F) бесконечен и содержит, в общем случае, автоматы с «избыточной» информацией относительно реализуемости в них множества F. Это обусловлено следующим: во-первых, вместе с каждым автоматом AK(F) класс K(F) содержит бесконечное множество автоматов, эквивалентных A; во-вторых, для любого автомата AK(F) и всякого автомата B K(U) автомат A + B также принадлежит K(F); в-третьих, для всякого автомата AK(F) класс K(F) содержит бесконечное множество автоматов, содержащих автомат A в качестве собственного подавтомата. Таким образом, большинство автоматов бесконечного класса K(F), заданных информацией о поведении в виде множества о.-д. функций F, заведомо «избыточны» относительно реализации множества F и таких автоматов в K(F) бесконечное множество. В этой связи вводится понятие «не избыточности» автомата относительно реализации заданного поведения следующим образом. Автомат A является неприводимым автоматом в классе K(F), если любой собственный подавтомат и любой гомоморфный образ автомата A не принадлежит классу K(F) .

Утверждение 2. Класс K(F) содержит единственный, с точностью до изоморфизма, неприводимый автомат из K(U).

Следствие 1. Заданная система о. - д. функций F идентифицирует, реализующий множество F, автомат A из K(U) тогда и только тогда, когда автомат A является неприводимым (относительно реализации F) автоматом в K(F). идентификация автомат задача дискретный

Однако в практических ситуациях информация о поведении автомата, полученная в результате проведения с ним экспериментов [2] или же априорно заданная в качестве условий на синтез, чаще всего конечна. Поэтому в качестве такой информации, на основании которой будет осуществляться идентификация внутренней структуры автомата (диаграммы переходов) предлагается рассматривать конечные фрагменты вход - выходного поведения автомата, определяемые как следы о. - д. функций, реализуемых автоматом, которые являются в определенном смысле «сужениями» отображений, осуществляемых о. - д. функциями на конечное множество слов. Рассмотрим вопрос идентификации автомата конечным фрагментом его поведения. Под следом о.- д. функции f, реализуемой автоматом A в состоянии s понимается конечное множество вход - выходных слов {(б,в)} таких, что f(б) = в. Под следом автомата понимается конечная совокупность следов о. - д. функций, реализуемых данным автоматом. След автомата простой, если все его элементы содержат единственное вход - выходное слово и структурированный в противном случае. Процесс структуризации следа заключается в уточнении информации о поведении путем перехода от множества простых экспериментов, составляющих элементы следа к множеству кратных экспериментов [2].

Рассмотрим случай, когда в качестве информации для идентификации автомата используется конечный след автомата. Пусть W= {R1,…Rk} - конечный след некоторого автомата A из K(U), диаграмма переходов которого содержит хотя бы один цикл. Приведем пример, показывающий, что для конечного следа W некоторого автомата A K(U) существует бесконечное множество автоматов из K(U), реализующих указанный след, у которых любой гомоморфный образ и любой собственный подавтомат не реализует заданный конечный след. С этой целью рассмотрим полезную конструкцию. Зафиксируем простой цикл автомата. Пусть {s1,…,sk} - простой цикл в автомате A дA(si, хi) = si+1 для i =1,… ,k-1 дA(sk, хk) = s1, , лA(si, хi) = уi i = 1, , k. Построим автомат Br, путем растягивания цикла автомата A' r раз. Полагаем, что в автомате B каждое состояние si расщепляется на r состояний sij 1 j r, а остальные состояния - такие же, как в автомате A'. Кроме того, предполагаем, что в автомате B существует цикл, образованный состояниями {s11,.., s1к ,…s21,s22,.., s2к,…,srk}, причем полагаем, что дB(sij, хi) = sij+1, 1 i < r , дB(sik, хk) = sj+1,j , 1 j < r , а также дB(srk, хk) = s1,1. Пусть также лB(sij, хi) = уi . Если дA(si, х) = si для некоторого хX, отличного от xi,, то полагаем, что дB(sij, х) = si1, и лB(sij, х) = лA(si, х). Если s {s1,…,sk} и дA(s, х) = si,, 1 j r то полагаем лB(sij, х) = лA(si, х). Если дA(s, х) {s1,…,sk}, то полагаем дB(sij, х) = дA(si, х) и лB(sij, х) = лA(si, х).Если дA(s, х) =t и s,t не принадлежат выбранному циклу в A, то полагаем дB(s, х) = t, лB(s, х) = лA(s, х).По построению автомат B детерминирован. Автоматы, диаграммы которых построены согласно операции растяжения цикла, содержат заведомо избыточную информацию (сколь угодно большое число состояний) относительно реализации конечного следа и не существует конечного следа, идентифицирующего любой такой автомат как неприводимый относительно реализации. В этой связи в [4] вводится понятие м - операции, с помощью которой определяется неприводимость (не избыточность) автомата относительно реализации конечного следа. Операция м является многозначной и определена схемой операции, в результате применения данной операции к диаграмме переходов получаем (в общем случае) множество автоматов. Если провести уточнение данной операции путем внешнего указания направления переходов, ведущих в удаляемое состояние, в оставшиеся состояния, в которые вели переходы из удаляемого состояния, то определим тем самым операцию обобщенной редукции и редуцированного подавтомата (результата применения операции обобщенной редукции). Автомат назовем неприводимым, относительно реализации конечного следа, если любой его редуцированный подавтомат не реализует заданного следа. Из теоремы 3. [4] следует, что для любого приведенного автомата не существует простых следов автомата, идентифицирующих данный автомат как неприводимый относительно их реализации. Из теоремы 2 [5] следует, что для любого приведенного автомата существует бесконечное множество структурированных следов, идентифицирующих данный автомат как неприводимый относительно реализации. В теореме 3 [5] приведены необходимые и достаточные условия для произвольного конечного следа некоторого автомата из K(U), при выполнении которых данный след идентифицирует автомат, его реализующий как неприводимый относительно реализации.

Выводы

Один из путей решения проблемы единственности при идентификации автомата конечным фрагментом поведения является уточнение свойств автомата (неприводимость относительно реализации фрагмента поведения) и уточнение с дополнением информации, относительно фрагмента поведения (структуризация следов и введение определенных числовых параметров), которые позволят согласно принципу единственности [1] идентифицировать автомат конечным фрагментом его поведения.

Список литературы

Калман Р. Е. Идентификация систем с шумами // Успехи математических наук - 1985. - т. 40. - Вып. 4 (244). - с.27 - 33.

Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. - М.: Наука, 1985. - 320с.

Буков В.Н., Кулабухов В.С., Максименко И.М., Рябченко В.Н. Проблема единственности решения задач теории систем // Автоматика и телемеханика, №12, 1997, стр.4 - 11.

Богомолов С.А. О синтезе автоматов по конечному множеству экспериментов // ДАН СССР, 1985, т. 281, №1, с. 20 - 22.

Богомолов С.А. О восстановлении автомата по экспериментам //Дискретная математика,т.1, вып.1,1989, С.135 - 146.

Размещено на Allbest.ru