Содержание к диссертации
Введение
1 Исследование специфики функционирования автоматов Медведева с обобщенными временными характеристиками 14
1.1 Основные понятия и определения 14
1.2 Автоматы с обобщенными временными характеристиками и их функционирование 22
1.3 Применение представляющих автоматов для решения задачи ФВП систем, моделируемых автоматами с обобщенными временными характеристиками 38
1.4 Основные результаты раздела 46
2 Восстановление поведения системы, моделируемой КДА Медведева произвольного временного типа, на основе анализа универсального автомата с обобщенными временными характеристиками 47
2.1 Анализ универсального автомата с обобщенными временными характеристиками 47
2.2 ФВП системы, моделируемой КДА Медведева типа <0,t2>, при изменении начального порядка расположения состояний автомата 70
2.3 Основные результаты раздела 80
3 Восстановление поведения системы, моделируемой семейством автоматов произвольных временных типов, на основе синтеза универсального автомата 82
3.1 Синтез универсального автомата с обобщенными временными характеристиками для семейства автоматов произвольных временных типов 82
3.2 Восстановление поведения системы, моделируемой семейством {АІ}ІЄІ автоматов Медведева типа (0,1) 94
3.3 Основные результаты раздела 105
Заключение 107
Список использованных источников 109
- Автоматы с обобщенными временными характеристиками и их функционирование
- Применение представляющих автоматов для решения задачи ФВП систем, моделируемых автоматами с обобщенными временными характеристиками
- ФВП системы, моделируемой КДА Медведева типа <0,t2>, при изменении начального порядка расположения состояний автомата
- Синтез универсального автомата с обобщенными временными характеристиками для семейства автоматов произвольных временных типов
Введение к работе
Теория автоматов находит широкое применение при решении задач проектирования, технического диагностирования и восстановления поведения сложных систем [43, 44, 45, 50]. Это обусловлено способностью автоматов выступать в качестве адекватных математических моделей законов функционирования дискретных систем [29, 37]. В свою очередь, исследование проблематики автоматов позволяет в определенной мере предсказать типологию и постановку задач технической диагностики и восстановления поведения [25-27, 32, 38].
Исследования в области теории конечных детерминированных автоматов (КДА) проводятся достаточно давно, начиная с работ Э. Мура, А. Гилла, В.М. Глушкова и других авторов [1, 28, 29, 2, 3, 13, 18, 35, 36, 39, 42, 48, 61, 62].
Одно из направлений этой теории, связанное с задачами исследования математических методов технической диагностики, получило развитие в работах A.M. Богомолова, П.П. Пархоменко, М.Ф. Каравая, Д.В. Сперанского, В.А. Твердохлебова [7, 9, 12, 33, 34, 59, 43-45, 47]. А.А. Сытник использовал теоретические основы технической диагностики в качестве инструментария при построении теории восстановления поведения дискретных систем [10, 11, 16, 49, 50, 51, 55], для которых способность к восстановлению поведения означает возможность продолжения заданного закона функционирования после возникновения и обнаружения неисправности.
Одним из возможных подходов при решении задачи восстановления является использование свойств текущего закона функционирования системы, полученного после возникновения неисправности, для формирования на выходах требуемой совокупности реакций, то есть решение задачи функционального восстановления поведения (ФВП) [50, 51, 56].
В упомянутых работах ФВП системы состоит в переходе от преобразовательного способа описания закона функционирования к перечислительному на основе использования теории универсальных автоматов.
В теории универсальных автоматов есть несколько вариантов определения универсальности. Так в определении, предложенным М. Минским [1], элемент называется универсальным, если достаточно большое множество объектов «обладает некоторыми подобными свойствами этого элемента, или отличающимися лишь в количественном отношении». Исследования данного подхода на множестве ограниченно - детерминированных функций проведено В.Б. Кудрявцевым и В.А. Буевичем [14].
В.М. Глушков [29] называет автомат универсальным, если «любой алгоритм может быть представлен в виде конечного набора выполняемых этим автоматом команд программы работы и фактически реализован им при условии игнорирования ограничений, накладываемых конечностью объема памяти автомата».
Концепция К. Шеннона [1] универсальности алгоритмов предполагает построение универсальной машины Тьюринга, в том смысле, что на ней путем подходящего кодирования можно выполнять любое вычисление и тем самым воспроизводить работу любой заданной машины Тьюринга. Обобщение универсальной вычисляющей машины с целью построения универсальной конструирующей машины рассматривалось Дж. фон Нейманом [42]. При этом универсальность машины заключалась в способности самовоспроизведения: «...процесс начинается с одного экземпляра универсального конструктора и его описания, а заканчивается двумя экземплярами этого комплекса. Это и есть самовоспроизведение...... Фон Нейман так же впервые предсказал, что
«благодаря тесной связи задач самовоспроизведения и саморемонта результаты по самовоспроизведению помогут решить проблему надежности» [42].
Дальнейшие исследования универсальности были ограничены классом булевых функций и конечных детерминированных автоматов. К их числу следует отнести работы Э.В. Евреинова, И.В. Прангишвили [31], В.И. Варшавского [18], В.М. Глушкова [29], В.А. Мищенко [40], Я.М. Барздиня [5], А.А. Сытника [50].
Понятие универсального КДА, основанное на концепции универсальности К. Шеннона, было исследовано А.А. Сытником [50].
Определенный в [10, 50] универсальный КДА А{ для класса автоматов
{Aj}.! позволяет моделировать поведение любого автомата из этого класса с
точки зрения выходных реакций. Осуществляется этот процесс путем подбора в универсальном автомате инициального состояния и входного сигнала (в общем случае последовательности входных сигналов), вызывающих ту же выходную реакцию, что и зафиксированный входной сигнал в рассматриваемом автомате семейства. Соответственно, эквивалентность в поведении универсального Aj и
моделируемого А(, ієі автоматов понимается в смысле перечислимости одинакового множества выходных сигналов. Данный подход является редукцией концепции К. Шеннона на множестве КДА.
В [50] показано, что реализация процесса восстановления поведения в случае отличия поведения исследуемой системы от заданного, предполагает последовательное решение следующих задач:
определение возможности восстановления заданного поведения системы;
поиск совокупности преобразований системы посредством трансформации ее составляющих, взаимосвязей между ними, изменения режимов функционирования, наблюдения и снятия результатов с выходных каналов, позволяющих восстановить заданное поведение;
выбор допустимого оптимального преобразования среди возможных преобразований системы по восстановлению заданного поведения, исходя из указанных ограничений на время и принцип восстановления.
Решение этих задач в каждом конкретном случае требует их формализации [41], например, с использованием математического аппарата конечно-автоматных преобразований симметрической полугруппы [17, 50, 51] или на основе построения числовой модели системы, допускающей моделирование многочленами [55, 56].
В качестве автоматных моделей поведения систем, как правило,
рассматриваются автоматы типов Мили и Мура, для которых закон
функционирования задается на уровне отдельных тактов работы автомата, при
этом абстракция мгновенного изменения состояния и мгновенной переработки
входного сигнала в выходной сигнал оказывается препятствием на пути
описания временных характеристик функционирующих систем с помощью
автоматов таких типов [59]. В данном случае возможно моделирование
поведения дискретных систем с помощью автоматов с обобщенными
временными характеристиками типа (t\>t2>h>U) > введенных
В.А. Твердохлебовым [58, 59, 60].
В работах А.А. Сытника [49, 50] по ФВП систем автоматы типов (t\,t2,t3,t4) использовались для определения временного режима наблюдения
выходных реакций при восстановлении поведения в перечислительной форме. При этом не рассматривался класс нарушений функционирования, который составляют изменения временных характеристик процесса формирования реакций системы. Моделирование поведения систем для данного класса неисправностей может быть адекватно реализовано с использованием автоматов с обобщенными временными характеристиками типа (ti,t2it3,t4).
Сказанное выше определило цель диссертационной работы, которая состоит в исследовании возможности функционального восстановления поведения дискретных систем, моделируемых автоматами с обобщенными временными характеристиками.
Объектами исследований в работе являются математические модели дискретных систем, представляющие собой инициальные КДА A = (S,X,Y,S,A,s0) [28, 29]. Их поведение р представляется в виде
объединения автоматных преобразований, индуцируемых всем множеством сигналов подаваемых на вход:
p= U {(м*(5о >/>))}>
реХ*
где Я* - расширенная функция выходов автомата А.
Предметом диссертационного исследования являются траектории изменения состояний КДА, что позволяет рассматривать вместо автоматов A = (S,X,Y,S,A,s0) автоматы Медведева [48]:
A = (S,X,S,s0) S:SxX^S Вся информация о поведении автомата Медведева заложена в индуцируемых входными сигналами преобразованиях, действующих на множестве внутренних состояний. Такое предположение существенно упрощает процесс исследования поведения и, не приводит к принципиальному ограничению общности рассуждений [50].
В соответствии с поставленной целью диссертационной работы решались следующие основные задачи:
Автоматы с обобщенными временными характеристиками и их функционирование
В [50] доказан критерий универсальности автомата Af, согласно которому для того, чтобы КДА Aj был универсальным для семейства конечных детерминированных автоматов {At }/є/ необходимо и достаточно, чтобы автомат Aj был универсальным перечислителем для автоматов семейства /.
Следующее определение позволяет дать математическую формулировку задачи ФВП, которая будет решаться в работе. Определение 1.16. Процесс построения для заданного класса неисправностей множества восстанавливающих последовательностей с последующим их приложением и организацией работы в перечислительном режиме назовем функциональным восстановлением поведения системы. Задача ФВП системы относительно заданного класса неисправностей в терминах теории универсальных автоматов может быть сформулирована следующим образом [50]. Пусть поведение «исправной» технической системы описывается конечным детерминированным автоматом А. Каждой учитываемой неисправности к є К сопоставляется автомат Ак, моделирующий поведение автомата А при неисправности к. Соответственно, предполагается заданным семейство КДА {Ак }кеК (класс учитываемых неисправностей) и КДА А. Как показано в [50] задача ФВП системы относительно заданного класса неисправностей, представленного семейством {Ak }кеК, разрешима тогда и только тогда, когда каждый автомат Ак семейства {Ак }кеК является универсальным для автомата А, моделирующего исходное поведение системы. Таким образом, для решения задачи ФВП системы, поведение которой описывается КДА А, необходимо проверить справедливость утверждения {Ak}keK ciUnA, и построить множество отображений { , „, каждое из которых удовлетворяет условию: (у к є К) (pkJ(Ak)= А. Затем для каждого множества отображений pkJ} выбрать допустимое решение ср (желательно оптимальное), исходя из заданных ограничений на реализацию процесса восстановления поведения. В [50] показано, что задача построения универсального КДА относительно конечного семейства КДА алгоритмически разрешима, но для решения задачи ФВП требуется проведение исследования процесса функционирования универсального автомата, а так же анализ принципов реализации семейства отображений \рщ\к К и уточнение, как самого процесса восстановления, так и конкретизация средств его проведения. При моделировании средств восстановления (СВ), требуемых для решения задачи ФВП, в [50] предложен и другой подход. Суть его заключается в описании всех автоматов А{, і е I, для которых заданный автомат А является универсальным. Пусть фиксирован тип неисправности, относительно которого для текущего поведения системы, представленного автоматом А, возможно восстановление, тогда автомат А(, /є/, задающий «исправное» поведение при возникновении неисправности данного типа, будет моделироваться автоматом А, универсальным для семейства автоматов {At }/є/. Задачу ФВП системы в этом случае можно решать двумя способами [50]: - найти семейство /, для которого А является универсальным автоматом (задача анализа); - найти для семейства / универсальный автомат А (задача синтеза). Далее в работе предлагается решать задачи синтеза и анализа универсальных автоматов Медведева с обобщенными временными характеристиками, то есть решать задачу ФВП систем, поведение которых описывается автоматами произвольного временного типа. Для этого необходимо провести исследование специфики функционирования автоматов Медведева с обобщенными временными характеристиками, выявить особенности их поведения. 1.2 Автоматы с обобщенными временными характеристиками и их функционирование Понятие конечного детерминированного автомата типа ( ,/2, з 4)» в котором традиционное определение конечного автомата обобщалось при помощи временных соотношений (1.8, 1.9) для функций переходов и выходов введено, как указано в параграфе 1.1, в [59] В.А. Твердохлебовым. Для того чтобы сохранить причинно-следственный характер связей между состояниями и воздействиями, с одной стороны, и новыми состояниями и внешними реакциями — с другой, предполагается выполнение неравенств (1.7) для параметров tx, t2, t3, t4. Согласно введенному определению 1.6, автоматы Мили являются автоматами типа (0,1,0,0). С каждым КДА A = {S,X,Y,5,X) типа автомата Мили связано семейство автоматных отображений {hs}seS вида hs:X Y . Обобщение понятия конечного детерминированного автомата не приводит к изменению свойств отображений вида hs:X -» Y , представимых в автоматах с произвольными временными характеристиками. Тип автомата и временные соотношения вида (1.8, 1.9) взаимнооднозначно определяют друг друга. В связи с этим будем употреблять выражение «автомат типа ti,t2,t3,t4» без указания временных соотношений. В автомате произвольного типа для каждого такта его работы должны быть представлены некоторые входные сигналы и состояния, относящиеся к моментам времени, не превосходящим /. При t4 \ и t43 l в автомате должны содержаться выходные сигналы, относящиеся к моменту t и некоторым последующим моментам [59]. Выполнение данных условий обеспечивает для автоматов произвольного типа свойство автоматического преобразования информации и свойство автономного восстановления автоматом после каждого такта работы средств для реализации следующего такта работы. Для того чтобы иметь возможность определять состояния, входные и выходные сигналы для автоматов типа {tx,t2,t3,tA) в различные моменты времени, зададим системы равенств на соответствующих множествах. Введем несколько обозначений. Определение 1.17 Пусть С— конечное непустое множество. Словом р длины к, к 1 в алфавите С назовем упорядоченную последовательность букв, полученную в результате отображения (р вида #?:{l,2,...,A:}-»C. Множество всех слов длины к, где к 1, в алфавите С будем обозначать через FQ , то есть F ={p\peFc&\p\ = k}.
Применение представляющих автоматов для решения задачи ФВП систем, моделируемых автоматами с обобщенными временными характеристиками
Полученный выше результат доказывает справедливость следующей теоремы. Теорема 1.5. Поведение автомата Медведева A = (S,X,S) и время его функционирования в классах автоматов типов (0,t2), t2 1 и (tx,t2), где tx 0, t2 1, t2 tx совпадает. Для класса автоматов типа (— 2), где tl 0, t2 \ процесс функционирования сдвигается в сторону увеличения во времени на величину параметра tx при том же поведении. Как следует из теоремы 1.5, при решении задачи ФВП систем, представленных автоматами Медведева A = (S,X,S) возможно использование автоматов типа (0,t2) без ущерба для общности получаемых выводов. Решения для систем, моделируемых автоматами типа (-/j,/2) и ( » г)» могут быть найдены обобщением результатов, полученных для автоматов типа (0,ґ2) 1.3 Применение представляющих автоматов для решения задачи ФВП систем, моделируемых автоматами с обобщенными временными характеристиками Решение задачи ФВП системы, моделируемой с помощью КДА, предполагает синтез и анализ соответствующего универсального автомата [1,5, 10, 11,31,51,50]. Как известно, методы синтеза, анализа и построения экспериментов хорошо разработаны для универсальных автоматов Мили (соответствуют временному типу (0,1,0,0)) и автоматов Мура (соответствуют временному типу (1,1,0,0)) [10,11,31, 51, 50]. Распространение этих методов на автоматы с обобщенными временными характеристиками возможно путем представления их поведения автоматами типов ( 0,1,0,0) и (1,1,0,0) [59]. Теоремы, приведенные в [59], составляют обоснование следующего утверждения: Утверждение 1.1. Для любого КДА произвольного типа существует КДА a(A) = (W,X,Y,Sa,Aa) типа (0,1,0,0), удовлетворяющий следующим условиям: а) существует взаимнооднозначное соответствие р вида (р: V — W, где V множество всех систем равенств, каждая из которых задает исходные данные для функционирования автомата А; б) система равенств X[t,t + \p\-l,p) и элемент veV определяют в соответствии с функциями 8 и Л, а так же в соответствии с типом автомата А, систему равенств У(ґ,ґ + д-1,#), тогда и только тогда, когда В [59] в качестве представляющего автомата используется автомат Мили, однако для представления автоматов Медведева типа (0,/2) удобнее использовать автомат Мура. Действительно, функция выходов автомата Медведева типа (0,/2) является сдвинутой на величину параметра t2 функцией отметок его состояний. Функция выходов автомата Мура так же сдвинута, но только на один такт. Это позволяет получить выходные последовательности, генерируемые автоматом Медведева типа (0,ґ2) в представляющем его автомате Мура, не применяя к ним дополнительных преобразований и, соответственно, значительно уменьшить вычислительные затраты. Используя данные в [59] определения представляющих автоматов для автоматов типов (-f,,/2,-/3,f4) (Мг зЛ)» ( і - зЛ}» ("Мг зЛ)» сформулируем определение автомата, представляющего автомат с обобщенными временными характеристиками, принадлежащий классу автоматов Медведева типа (0, t2). Определение 1.20. Пусть автомат Медведева A = (S,X,S) имеет тип (0,/2), где /2 1. Конечный детерминированный автомат Мура а(А) = [F$2 ,X,S,Sa(A),A,a(A)), соответствующий временному типу (1,1,0,0), где 5а{А) и K{A) отображения вида Sa{A):F xX- Fs2, Ла{А): F s2 х X - S, определяемые следующим образом: для любого элемента s є F s2 и любого хєХ, а(А) х)=7, (1.30) тд s = (pr2 t2s)S\prxs,x) (1-31) и 4( )W= Prt2s О-32) будем называть автоматом, представляющим автомат А. Замечание 1.20.1 Из определения 1.20 следует, что для случая, когда автомат Медведева A = {S,X,S) имеет тип (0,l), представляющий автомат СС(А) будет с ним совпадать. Действительно, для случая, когда t2 = 1, сс{А) = [S, X, S, Sa , Ла ). Согласно определению функции переходов (1.30, 1.31) автомата ос{А) получаем: Для функции выходов автомата ос{А) согласно (1.32) имеем: a(A)(S X) = S = S(S X) То есть автомат (Х(А) есть автомат а {A) = (S,X,S,S,S) ИЛИ A = {S,X,S), когда t2 = 1. Рассмотрим поведение автомата Мура ОС(А), заданного определением 1.20, на входных словах р є FJf . Для этого распространим функции переходов Sa(Ay. F$2 х X- F$2 (1.30,1.31) и выходов К{А) -F2 X- S (1.32) до функций вида Sa{A):F s2 хFJf1 - F s2 и Ла/А\ :Fs2 xFP - FJ? по правилу (1.10) из определения 1.11. В результате г(А) получим: На основании утверждения 1.1 для автоматов A = (S,X,S) типа (0,/2) и a(A)=(Fs2,X,S,Sa(AyAa(A)) типа (1,1,0,0), получим теорему, определяющую метод приведения автоматов типа (0,/2) к эквивалентным им автоматам типа (1,1,0,0). Теорема 1.6. Пусть дан автомат A = (S,X,S) типа (0,t2), где /2 1 и a(A)=\Fs2,X,S,SarA\,XatA\) автомат типа (1,1,0,0), представляющий автомат А. Системы равенств X\t,t + \p\-l,p), где peF}P, S\f,t + t2 -\,sJ, s eFJ2 и функция 8 однозначно определяют систему равенств S\t + t2,t + t2+\q\ \,q), q є Fg тогда и только тогда, когда
ФВП системы, моделируемой КДА Медведева типа <0,t2>, при изменении начального порядка расположения состояний автомата
Рассмотрим задачу ФВП, сформулированную в параграфе 1.1, с точки зрения организации процесса восстановления первоначального поведения исследуемой системы.
Существует два основных направления в организации средств восстановления (СВ) поведения: синтез встроенных средств восстановления (ВСВ) поведения и реализация самовосстановления поведения [45]. Данная глава посвящена разработке методов самовосстановления поведения систем, моделируемых КДА Медведева A = (S,X,S) типа (0,t2).
Самовосстановление поведения предполагает возможность получения из возникшего в результате неисправности текущего, наблюдаемого закона функционирования требуемого поведения. В терминологии универсальных автоматов данный подход равносилен решению задачи анализа (см. параграф 1.1) универсальных КДА, заключающейся в построении по заданному универсальному автомату соответствующего множества моделируемых объектов [50].
В параграфе 1.3 было показано, что автомату Медведева A = (S,X,S) типа (0,t2) с системой равенств у,/ + ґ2 -\,sJ, s eF$2 взаимнооднозначно соответствует инициальный автомат Мура a(A)=\Fs2 ,X,S,Sa fAa ,sJ, представляющий автомат А. При этом начальное состояние s автомата СС(А) есть начальное слово состояний автомата А (теорема 1.6), которое будем указывать в записи автомата A = \S,X,S,sJ. Принципы построения семейства автоматов по заданному универсальному автомату с обобщенными временными характеристиками определим, используя перечислительную форму для модели поведения универсального автомата [10,20,50,52,57], а так же критерии функционирования для автоматов с обобщенными временными характеристиками (теоремы 1.2,1.3). Рассмотрим класс неисправностей систем, заключающихся в изменениях временных характеристик процесса формирования выходных реакций. Системы с такими неисправностями моделируются, например, КДА Медведева A = \S,X,S,s0j типа (0,/2), где значение временного параметра t2 превосходит г2 - значение временного параметра автомата А{ =\S,X,S,sfj типа (0,г2), описывающего исправный закон функционирования системы. Математическая постановка задачи анализа универсального КДА в этом случае имеет следующий вид: Задача 2.1.1. Задан КДА Медведева A = [S,X,S,sJ с обобщенными временными характеристиками типа (0,/2). Требуется определить семейство КДА \At =\S,X,S,s?jfieI типа (0,г2), где 1 т2 t2, для которых автомат А является универсальным. Для решения задачи 2.1.1 определим условия, которым должен удовлетворять автомат A = [S,X,S,sJ типа (0,t2), чтобы являться универсальным перечислителем для семейства автоматов \А{ = \S,X,S,sf )/є/ типа (О, т2), где 1 т2 t2. конечное Теорема 2.1. Пусть дан автомат A = \S,X,S,sJ типа (0,t2) и и семейство КДА {лД-е/ типа (0,г2), где для каждого і el At = \S,X,S,sf) \ т2 t2. Тогда автомат А является универсальным перечислителем для автоматов семейства \А1 )ш, если выполняется одно из условий: а) т2 =t2 и sf является перестановкой состояний слова s, то есть семейство автоматов \А( =\S,X,S,sfjjjeI типа (0,/2) образуют автоматы, полученные из 4 = , , ,50] за счет определения различных исходных данных sf в результате применения операции перестановки к состояниям из s; б) 1 г2 /2 и sf является размещением состояний из 5 по г2, то есть семейство автоматов \At = \S,X,S,sf JjieI образуют автоматы типа (0,т2), у которых исходные данные являются результатом размещения состояний из s по т2. Доказательство. Докажем справедливость утверждения теоремы для автоматов типа (1,1,0,0), представляющих поведение автоматов { /}/є/ типа (0,г2) и автомата А типа (0,/2). Тем самым будет доказана справедливость теоремы для автоматов с обобщенными временными характеристиками. Рассмотрим автоматы: a(A)=\F?,X,S,SaiA),AaiA),7}, а(4.)=( ,Х,5, и)Даи),?),/є/. Эволюцию состояний автоматов СС(А) И О:(А;), і el под действием входных сигналов из X представим в виде: соответственно. По определению 1.15 автомат сс{А) является универсальным перечислителем для семейства автоматов {a{At)}/є/, і el, если (V/є/) Проверим справедливость этого утверждения для случаев а) и б) из формулировки теоремы. Для случая а) покажем что, когда г2 = /2 перечисление одинакового множества выходных последовательностей автоматами а(А) и а(А(), і el возможно, если sf является перестановкой состояний слова 5 . Запишем начальное состояние 5 автомата а(А) в виде перестановки
Синтез универсального автомата с обобщенными временными характеристиками для семейства автоматов произвольных временных типов
Пусть поведение исправной системы описывается КДА Медведева A = \S,X,S,sJ типа (0,t2) и начальное слово состояний skeF 2 автомата Ак = \S,X,S,slj типа (0,t2) является перестановкой, формируемой из s єF s2. Тогда V/?ЄF 2, neZ+ автомат Ак в процессе приложения входных последовательностей рА , определенных на основе равенства (2.25), моделирует поведение автомата А на слове р в моменты времени t + l2 +T]j -1, где / = 0,1,.,.,п-\, j = 1,/2 Доказательство. При доказательстве этой леммы 2.1 установлено, что для qA = Aa(A)\s,p) и qA = Ла(А \\s%,pA J справедливо соотношение (2.26). С учетом равенства pr,.t2+rjj{qAk)=s(t + l2+T]j-\), где / = 0,1,...,/7-1, j = \,t2, это означает справедливость следствия 2.1.1. Следствие доказано. Замечание 2.1 Лемма 2.1 позволяет описать класс неисправностей К, относительно которого возможно ФВП системы, моделируемой КДА Медведева A = \S,X,S,s) с обобщенными временными характеристиками типа (0,t2). Данный класс неисправностей системы представляют автоматы Ak = \S, X, S,s% J, к є К с измененным по отношению к автомату А начальным порядком расположения состояний. Доказанная лемма 2.1 и следствие 2.1.1 позволяют обосновать метод получения в универсальном автомате Ак выходной последовательности автомата А, индуцированной произвольным входным словом р є FJ? . Представленный далее метод можно рассматривать как модификацию метода 2.1, поскольку в нем сохраняется последовательность выполнения шагов и содержание некоторых из них (шаг 1, шаг 4) переносится из метода 2.1. Метод 2.2. Моделирование поведения автомата А на произвольном входном слове р є jpjf универсальным автоматом Ак из класса неисправностей К. Вход: Автомат A = \S,X,S,sJ типа (0,ґ2) и семейство автоматов {Ak}keK, образованное универсальными для А автоматами Ak = \S,X,S,skJ типа (О,t2), удовлетворяющими условию леммы 2.1. Произвольное входное слово р є F)P. Выход: Выходная последовательность qA автомата А на произвольном входном слове р є FJP, полученная универсальным автоматом Ак, к є К. Шаг 1. Формирование исходных данных автомата A = \S,X,S,sJ типа (О, t2 ), описывающего исправное поведение системы. На этом шаге задается начальное слово состояний s є Fj2 автомата А. Шаг 2. Формирование исходных данных sk є F$2 автомата Ак = \S, X, 8,sk) типа (0,ґ2), описывающего текущее поведение системы. Согласно условию леммы 2.1 отличие слов sfeF 2 автоматов Ак заключается в порядке расположения состояний, который задается перестановкой, формируемой из s е F(s2. Шаг 3. Формирование перестановок , к, о , т]. Определяем по формуле (2.1) перестановку ,. Определяем по формуле (2.2) перестановку %к . Согласно равенству (2.3) определяем перестановку а и находим г/ = j l. Шаг 4. Увеличение длины входного слова р є Fp до кратности /2 и определение п є Z+ на основании равенства \р\ = и t2 Входное слово р должно удовлетворять равенству \p\ = n2, где «eZ+, если оно не выполняется и \p\ = n2+m, где тФО, всегда можно продолжить слово р, добавляя справа t2-m пустых слов е. Шаг 5. Формирование входной последовательности рА для универсального автомата Ак. Используя полученную на шаге 3 перестановку а из входной последовательности р, определенной на шаге 4, формируем входную последовательность рА для автомата Ак согласно равенству (2.25). Шаг 6. Получение выходной последовательности qA автомата a{Ak) = \Fts2,X,S,8a AkyXa Akyslj, представляющего автомат Ак, на входной последовательности рА . Для генерирования выходной последовательности qA воспользуемся автоматом Мура а(Ак ) = \F 2, X, S, Sa(Ak)»Л (лА)»sl ) представляющим автомат Ак типа (0,ґ2) (см. теорему 1.6). Шаг 7. Формирование выходной последовательности qA автомата А из выходной последовательности qA автомата Я:(А) представляющего автомат Ak. Используя полученную на шаге 3 перестановку 77 из выходной последовательности qA , формируем qA согласно равенству (2.26). Проверку метода 2.2 реализуем на конкретном примере. Пусть исправное поведение системы задано автоматом A = \S,X,S,sj типа (0,t2)- Текущее поведение системы описывается КДА Ak =\S,X,S,skJ, кєК, у которого начальное слово состояний s% удовлетворяет условию леммы 2.1. Для восстановления поведения системы, моделируемого автоматом A = \S,X,S,sJ типа (0,t2) с помощью универсального автомата Ak = \S,X,S,sk J (см. лемма 2.1), применим описанный выше метод 2.2. Пример 2.3. Рассмотрим организацию ФВП системы дискретного типа, моделируемой КДА Медведева A = [S,X,S,sJ с обобщенными временными характеристиками типа (0,?2), в случае, когда все состояния в s различны. Пусть функция переходов-выходов 8 универсального автомата A = \S,X,S,s) типа (0,3) задана таблицей (табл. 2.1). Шаг 1. Формирование исходных данных автомата A = [S,X,S,s J типа (0,3), описывающего исправное поведение системы. Зададим начальное слово состояний s = 321.
Похожие диссертации на Функциональное восстановление автоматов-перечислителей с обобщенными временными характеристиками линейного типа
