Универсальное тестирование в частных классах автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

ПОНОМАРЕНКО Александр Владимирович

УНИВЕРСАЛЬНОЕ ТЕСТИРОВАНИЕ В ЧАСТНЫХ КЛАССАХ АВТОМАТОВ

Специальность 0101 09-дискретная математика и математическая

кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Саратов 2007

^"¿ВШ'ДЩ

Работа выполнена в Институте проблем точной механики и управления РАН

Научный руководитель

доктор технических наук, профессор

Твердохлебов Владимир Александрович

Официальные оппоненты

доктор технических наук, профессор

Сытник Александр Александрович

доктор социологических наук, кандидат физико-математических наук, профессор

Печенкин Виталий Владимирович

Ведущая организация

Институт проблем управления РАН (Москва)

Защита состоится "31" мая 2007 г в 17 30 на заседании диссертационного совета К 212 243 02 при Саратовском государственном университете им НГ Чернышевского (410012, г Саратов, ул Астраханская 83)

С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета

Автореферат разослан "28" апреля 2007 г.

Ученый секретарь диссертационного совета к ф -м н , доцент

Сс57 Корнев В В

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Проблема распознавания содержимого "черного ящика" относится к одной из основных проблем математической кибернетики В частности, ее вариантом является задача технического диагностирования в классе неисправностей, модель каждой из которых представлена дискретной детерминированной динамической системой в форме конечного детерминированного автомата вида А = {5,Х,У,8Д} В этой задаче множество неисправностей I определено семейством конечных детерминированных автоматов а = {А,}1б1, где А, = {5,,Х,У,5,Д,} те предполагается, что содержимым "черного ящика" является некоторый автомат А2, из семейства а и требуется определить, при каком конкретном значении 1 выполняется равенство г — 1 Средством расшифровки "черного ящика "полагается эксперимент, т е процесс приложения к "черному ящику" воздействия, наблюдения реакции, анализ и построение логических выводов по которым определяется, достигнута ли расшифровка, продолжать или прекратить эксперимент Задача распознавания конечных автоматов, понимается как определение содержимого "черного ящика", т е расшифровки связей вход-выход, при условии когда содержимое "черного ящика" принадлежит какому-либо известному семейству автоматов

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

Теории конечных автоматов посвящено большое количество работ отечественных и зарубежных авторов В диссертации существенно и непосредственно использовались результаты исследований Э Мура, А Гилла, Т Хиббарда, В М Глушкова, С В Яблонского, В Б Кудрявцева, сотрудников школы П П Пархоменко (МВ Каравая и других), школы А М Богомолова (В А Твердохдебова, Д В Сперанского, А А Сытника) и некоторых других авторов

Задача технического диагностирования как задача распознавания автомата в заданном семействе автоматов была решена А Гиллом на основе сведения ее к установочной задаче Э Мура

Под установочной задачей понимается задача установки конечного детерминированного автомата находящегося в одном из допустимых начальных состояний в известное конечное состояние приложением некоторой входной последовательности Другими словами, если А = (Б.Х, У,8,/.) - конечный детерминированный автомат, где Б.Х.У -множества состояний, входных и выходных сигналов, а 5 БхХ—и X. 8 х X —> У - функции переходов и выходов, и 80 - множество

допустимых начальных состояний, то необходимо найти слово реХ*, удовлетворяющее предикату (Vs,s' s S0){5(s,p) ^ 5(s',p) -» X.(s,p) * /.(s',p)} Э Мур в 1956 году показал, что существует решение установочной задачи с помощью простого безусловного эксперимента

Задача распознавания автомата представляет собой определение его минимальной формы путем проведения эксперимента На практике, часто возникает задача распознавания автомата, о котором известно, что он принадлежит к определенному конечному семейству автоматов, те необходимо определить, каким из автоматов семейства а = {А,}1б[, где А, = (S,,X,Y,5, Д,) - конечный детерминированный автомат, является автомат А = (S,X, Y,8,>.) Решение этой задачи может быть найдено приложением к исследуемому автомату слова р е X , удовлетворяющего предикату (Vi,j е I)(Vs е S,)(Vs' eSjXi * j X.*(s,p) *>.*(s',p)} Поиск

решения этой задачи, А Гилл предложил осуществить путем замены семейства автоматов a = {A1},s[, расщепляемым конечным

детерминированным автоматом A = (yS,,X,Y,(j61,lJ^,), в который

iel iel tel

каждый автомат семейства входит как изолированный подавтомат, и решению для автомата Д установочной задачи

Метод, предложенный А Гиллом, напрямую зависит от конкретных функций переходов и выходов автоматов заданного семейства, следовательно, построенный тест является неприменимым для тестирования другого, пусть даже очень близкого семейства автоматов Изменение распознаваемого автомата или семейства требует замены тестом, полученным новым применение метода Это оказывается принципиальным недостатком при выполнении процедур контроля и диагностирования на этапах функционирования технических систем

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

В 1981-1982 годах на международных конференциях Твердохлебовым В А был предложен метод универсального решения задачи распознавания автомата в заданном семействе автоматов В дальнейших работах Твердохлебова В А продолжено исследование универсальных тестов - найдены оценки длины и методы построения универсальных тестов Полученная оценка длины универсальных тестов

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

Так как оценка длины универсального теста не может быть понижена для общего случая, на основании результата Т Хиббарда о достижимости оценки Э Мура длины решения установочной задачи, универсальные тесты, предложенные Твердохлебовым В А „ получили только теоретическое значение Актуальным оказался вопрос о возможности развития универсального тестирования с оценками длины универсальных тестов, позволяющими их практическое применение Сокращение оценки длины универсальных тестов может быть возможным в классах дискретных систем, обладающих специфическими свойствами

Целью диссертационной работы является

- доказательство возможности минимизации универсальных тестов в частных классах конечных детерминированных автоматов на основе проведения вычислительного эксперимента в собственных подклассах класса (4, 2, 2) — автоматов, выделенных на основе специфических свойств комбинационных частей автоматов,

- построение минимальных универсальных тестов для фундаментальных частных классов автоматов в классе (4, 2, 2) -автоматов, предполагаемом исходном базисе для построения композиции автоматов,

- построение на основе вычислительного эксперимента достижимых оценок длин минимальных универсальных тестов в выделенных фундаментальных частных классах автоматов,

- определение условий применимости универсальных тестов при диагностировании внутреннего элемента структурной системы, математической моделью которого является конечный детерминированный (4,2,2) - автомат,

- определение условий применимости минимизированных универсальных тестов при диагностировании в целом структурной системы, математической моделью которой является последовательная композиция (4,2,2) - автоматов

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

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

Научная новизна. Впервые показана возможность существенного (на несколько порядков) сокращения длины общетеоретического универсального теста, что дает возможность эффективного применения универсальных тестов в частных классах дискретных систем

Найдены оценки длины универсальных тестов в этих классах и построены конкретные универсальные тесты

Проведен анализ Постовских свойств функций переходов и выходов автоматов, с целью определения влияния этих свойств на длину универсальных тестов

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

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

На защиту выносятся:

- полученные оценки длин универсальных тестов в каждом исследованном классе автоматов линейных (4,2,2) - автоматов, самодвойственных (4,2,2) - автоматов, монотонных (4,2,2) - автоматов, линейных и самодвойственных (4,2,2) — автоматов, линейных и монотонных (4, 2,2) — автоматов, самодвойственных и монотонных (4,2,2) - автоматов, линейных, самодвойственных и монотонных (4,2,2) -автоматов (полученные оценки значительно меньше оценок для общего случая),

- разработанные методы сокращения универсальных тестов и конкретные минимизированные универсальные тесты для каждого исследованного класса автоматов линейных (4,2,2) - автоматов, самодвойственных (4,2,2) - автоматов, монотонных (4,2,2) - автоматов, линейных и самодвойственных (4,2,2) - автоматов, линейных и монотонных (4, 2,2) - автоматов, самодвойственных и монотонных (4,2,2) - автоматов, линейных, самодвойственных и монотонных (4,2,2) -автоматов,

- найденные условия для эффективного использования условия использования универсальных тестов в классе (4, 2, 2) - автоматов при тестировании композиции таких автоматов,

- разработанные алгоритмы и программы для выделения специфических подклассов в выбранном классе автоматов, для построения

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

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

Апробация работы Основные результаты диссертационной работы докладывались на 17-ой Международной научно-технической конференции "Перспективные информационно — управляющие системы на железнодорожном, промышленном и городском транспорте (Алушта, 2004г), на 5-ой Международной конференции "Автоматизация проектирования дискретных систем" (Минск, 2004г), на 2-ой Международной научной конференции "Аналитическая теория автоматического управления и ее приложения" (Саратов, 2005г), на Международной научно-техническая конференция "Гарантоспособные (надежные и безопасные) системы, сервисы и технологии" (Полтава, 2006г), на 9-ой Международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, 2006г), на Международной конференции "Проблемы и перспективы прецизионной механики и управления в машиностроении" (Саратов, 2006г), на семинарах в Институте проблем точной механики и управления РАН

Публикации. По результатам исследований в период с 2004 по 2006 гг опубликовано 9 научных статей (включая статью в журнале, входящем в Перечень периодических изданий, рекомендованных ВАК РФ для публикации основных результатов диссертаций на соискание ученой степени), список которых приводится в конце автореферата

Объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы (58 наименований) и приложений Объем работы 118 страниц машинописного текста

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность задач, исследуемых в диссертационной работе, сформулированы цели и задачи исследования, выполнен обзор работ по теме диссертации Кратко изложены основные результаты работы по главам

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

В основе классификации автоматов, лежит известная декомпозиция автомата на комбинационную часть, рассматриваемую как совокупность функций алгебры логики, и память Для функций алгебры логики имеется фундаментальная классификация по свойствам Поста - сохранять нуль, сохранять единицу, быть линейной, быть самодвойственной, быть монотонной Для любой булевой функции и любого свойства Поста существуют эффективные процедуры проверки, обладает ли функция рассматриваемым свойством (см , например [9]) В связи с этим всего возможно 32 варианта сочетаний свойств Поста Для обозначения этих классов будем использовать букву Н с пятью нижними индексами Н^ = Н,пНьпНспН<1пНв,где а = 0|0, Ь = 1|1, с = 5|§, & = е = М | М Также рассматриваются более широкие классы, например, Н0,Н0Ьи тд Для классификации автомата его функции переходов и выходов 5 и X представляются в виде наборов булевых функций 5 =<5,,52,...,8Ю >, X=<XI,X2,...,XV > Отнесение автомата к какому-либо классу автоматов происходит на основе принадлежности б,, 1 < 1 < ю и /^,1 <.) < V какому-либо классу функций Так, например, будем считать, что автомат является линейным АеНь, если все булевы функции из наборов, составляющих функцию переходов и функцию выходов — линейные, "к € Ньи5, е Нь

Не все из определенных выше классов отличны от пустых Для выделения непустых классов были доказаны следующие леммы

Лемма 1 Классы НЙ5ЬМ» Нойш> Н5ЁШ> Н01§Ш> Н0БШ' Н0ЙШ-

тт _ тт__т т ТТ_ II _ Т1__и___ тт__ II___

■"оЙЗЬМ' ПОВЬМ' 0151М' 015ЬМ' "оЮЬМ' "о^ЬМ' По1а.М' ■П018Ш' П018Ш'

Н01БЬМ' Н01§ьм булевых функций пустые

лемма 2 ГСлаССЫ нбйШ» НЙЕм> Нш§Ем' Н01ам' Нойы,

Н01Я-М> ' ^ОИЕм' ^ОКШ

булевых функций непустые

Итогом является следующая теорема

Теорема 1 В классе (4, 2, 2) - автоматов содержится точно 3375 непересекающихся подклассов, определяемых сочетаниями попарно различных наборов свойств Поста для функций переходов и выходов из комбинационной части автомата

Дня проверки свойств булевых функций составляющих функции переходов и выходов использовались следующие алгоритмы

Алгоритм 1 Определение принадлежности функции алгебры логики классу самодвойственных функций

Исходные данные и предположения Столбец значений функции алгебры логики задан одномерным массивом с длины i

Действия алгоритма 1-й шаг Полагается j = 0 2-й шаг Проверяется равенство ф] = ф-1-j] Если равенство выполняется, то функция не самодвойственная и алгоритм окончен 3-й шаг Проверяется равенство j = i/2-l Если равенство выполняется, то функция самодвойственная и алгоритм окончен Если равенство не выполняется, то полагаем j -=J+1 и переходим к шагу 2

Алгоритм 2 Определение принадлежности функции алгебры логики классу монотонных функций

Исходные данные и предположения Столбец значений функции алгебры логики задан одномерным массивом с длины i, размерность функции - п Известен алгоритм построения по номеру h элемента столбца значений и размерности функции п соответствующего набора значений переменных функции в виде одномерного массива - х£ массива -х^1 (Алгоритм 21) Известен алгоритм определения сравнимости двух наборов значений переменных, заданных одномерными массивами массива - xj,"1 (Алгоритм 2 2)

Действия алгоритма 1-й шаг. Полагается j = 0 2-й шаг Полагается k = j+1 3-й шаг Строятся два набора значений переменных,

соответствующих j-му и к-му элементу столбца с - х"и х£ 4-й шаг Определяется, являются ли сравнимыми два набора значений переменных - х"и х" Если наборы не сравнимы, то переходим к 6-му шагу 5-й шаг Проверяется истинность выражения (c[j] < c[k]) Если выражение ложно, то функция не монотонная и алгоритм окончен 6-й шаг Проверяется равенство k = i -1 Если равенство не выполняется, то полагаем к = к+1 и переходим к шагу 3 7-й шаг Проверяется равенство j = i -2 Если равенство не выполняется, то полагаем j = J+1 и переходим к шагу 2 Если равенство выполняется, то функция монотонная и алгоритм окончен

Алгоритм 2 1 Построение набора значений переменных функции в виде одномерного массива

Исходные данные и предположения Известен номер h элемента столбца значений и размерность функции п Задан пустой одномерный

массив длины п

Действия алгоритма 1-й шаг Полагается j = п-1 2-й шаг x{¡[j] полагается равным остатку от деления h на 2, x£[j] = h%2 3-й шаг h полагается равным целой части при делении h па 2, h =h/2 4-й шаг Проверяется равенство j = 0 Если равенство не выполняется, то полагаем j =j-l и переходим к шагу 2 Если равенство выполняется, то в массиве x{¡ содержится искомый набор значений переменных функции, и алгоритм окончен

Алгоритм 2 2 Определение сравнимости двух наборов значений переменных

Исходные данные и предположения Два набора значений переменных заданы одномерными массивами x¡¡( и хЦ^ длины п и h, < h2

Действия алгоритма 1 -й шаг Полагается J = 0 2-й шаг Проверяется неравенство (х^ [j] < [j]) Если выражение ложно, то наборы значений

не сравнимы и алгоритм закончен 3-й шаг Проверяется равенство j = п-1 Если равенство не выполняется, то полагаем j = j+1 и переходим к шагу 2 Если равенство выполняется, то наборы значений сравнимы и алгоритм окончен

Алгоритм 3 Определение принадлежности функции алгебры логики классу линейных функций

Исходные данные и предположения Столбец значений функции алгебры логики задан одномерным массивом с длины i, размерность функции - п Задан пустой одномерный массив indexn длины п Известен алгоритм построения столбца значений линейной функции размерности п в виде одномерного массива с' длины i по заданным индексам полинома Жегалкина массива - х ¡Г1 (Алгоритм 3 1)

Действия алгоритма 1-й шаг Полагается j = 0, index п[0] с[0] 2-й шаг Полагается к равным 2 в степени j, k=2Aj 3-й шаг Поверяется равенство mdexn[0] = с[к] Если равенство выполняется, то полагаем mdexn[j] = 0, если нет - mdexn[j] = 1 4-й шаг Проверяется равенство j =п -1 Если равенство не выполняется, то полагаем j = j+1 и переходим к шагу 2 5-й шаг По заданным индексам полинома Жегалкина, хранящимся в массиве index п строим столбец значений функции — с' 6-й шаг Сравниваем два массива си с', если массивы совпадают — функция линейна Алгоритм окончен

Алгоритм 3 1 Построения столбца значений линейной функции по заданным индексам полинома Жегалкина

Исходные данные и предположения Заданы индексы полинома Жегалкина в виде одномерного массива mdexn длины i Задан пустой одномерный массив с длины к равной 2 в степени i-l Известен алгоритм

построения по номеру h соответствующего набора значений переменных функции размерности i-l в виде одномерного массива - xj,-1 (Алгоритм 2 1) Известен алгоритм построения значения линейной функции с индексами полинома Жегалкина indexn на любом зафиксированном наборе значений переменных (Алгоритм 3 2)

Действия алгоритма 1-й шаг Полагается j = 1, с[0] = index „[0] 2-й шаг Строится набор значений переменных, соответствующих j-му номеру- х" 3-й шаг Находим значение а линейной функции с индексами

indexn на наборе значений переменных х" 4-й шаг Полагаем c[j] = а 5-й

шаг Проверяется равенство j = i -2 Если равенство не выполняется, то полагаем j = j+1 и переходим к шагу 2 Если равенство выполняется, то с -искомый столбец значений функции Алгоритм окончен.

Алгоритм 3 2 Построения значения линейной функции с известными индексами полинома Жегалкина на любом зафиксированном наборе значений переменных

Исходные данные и предположения Заданы индексы полинома Жегалкина в виде одномерного массива indexn длины х и набор значений переменных х

Действия алгоритма 1-й шаг Полагается j = 0, а = index ДО] 2-й шаг Проверяется равенство а == mdexn[j + l]* x[j] Если равенство выполняется, то полагаем а =0 Если равенство не выполняется, то полагаем а=1. Проверяется равенство j = i -1 Если равенство не выполняется, то полагаем j = j+1 и переходим к шагу 2 Если равенство выполняется, то а - искомое значение функции на наборе значений переменных х Алгоритм окончен.

На основании доказательств с использованием вычислительного эксперимента было установлено, что распределение автоматов по подклассам не равномерно

Лемма 3 1 В подклассах Hoís--, класса (4, 2, 2) - автоматов

содержится ровно по 216000 автоматов

Лемма 3 2 В подклассе Н--— класса (4, 2, 2) - автоматов

V loLM

содержится ровно 175616 автоматов

Лемма 3 3 В подклассе Н класса (4, 2, 2) - автоматов

содержится ровно 74088 автоматов

Лемма 3 4 В подклассе Н0]-~м класса (4, 2, 2) - автоматов

содержится ровно 2744 автомата

Лемма 3 5. В подклассах H^j-^, класса (4, 2, 2) - автоматов

содержится ровно по 64 автомата

Лемма 3 6 В подклассах H5i§l5í, H0ͧlSÍ, Н015Ш, H01SLM класса

(4, 2,2) - автоматов содержится ровно по 27 автоматов

Лемма 3 7 В подклассах На,§ш, Н0ЙЫ, Н015Ш, Н0]5ьП класса

(4,2, 2) — автоматов содержится ровно по одному автомату

Из приведенных выше лемм следует, что построение тестов в классах автоматов из лемм 3 1-33 должно представлять большие трудности в связи с тем, что в классе (4, 2, 2) - автоматов с такими свойствами большее число Для автоматов из лемм 3 4 — 3 7, в силу большой специфики соответствующих свойств в классе (4, 2, 2) — автоматов, построение тестов должно упрощаться

Для проведения минимизации универсального теста были выбраны более широкие подклассы класса (4,2, 2) - автоматов, а именно подклассы Н^ Н5, Нм, Н5М, Нш, Н5Ш

Для выделенных подклассов Нь, Н5, Нм, Н51_, Н5М> Нш, Н5Ш класса конечных детерминированных (4, 2, 2) -автоматов было вычислено общее число автоматов, число попарно неэквивалентных автоматов и определены пары автоматов, составляющие исключительные классы (см таб 1)

Таблица 1

Количественные характеристики исследуемых классов_

Класс автоматов Общее число автоматов Число попарно неэквивалентных автоматов Число пар, составляющих исключительный класс

4096 84 3378

н5 4096 356 61384

нм 8000 1460 621212

512 27 341

Ням 64 13 42

Нш 125 10 30

Нбьм 27 3 2

Алгоритм 4 Определение пар эквивалентных состояний

Исходные данные и предположения На сновании таблицы переходов и выходов автомата А = (Б, X, У,5Д) построен первый вариант таблица пар состояний по следующему принципу

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

- таблица содержит по одному столбцу на каждый символ входного алфавита уь,

- в клетке таблицы, находящейся на пересечении строки (s^Sj) и столбца yh содержатся преемники состояний s, и Sj по отношению к yh,

- все строки таблицы определяются как непомеченные

Таблица пар состояний содержит п строк, нумерация строк начинается с единицы

Действия алгоритма 1-й шаг k=0, label =0 2-й шаг Если к>п, то переходим к шагу 6 3-й шаг Если строка с номером к помечена, то переходим к шагу 5 4-й шаг Строка с номером к помечается, если в каком либо столбце, кроме основного, имеется пара состояний, которая либо отсутствует в основном столбце, либо содержится в основном столбце помеченной строки label =1 5-й шаг к = к+1, переходим к шагу 2 б-й шаг Если label = 1, то переходим к шагу 1 Если нет, то алгоритм окончен, и в непомеченных строках в основном столбце содержатся пары эквивалентных состояний

Во второй главе диссертационной работы рассмотрено сокращение двух вариантов универсальных тестов в исследуемых подклассах и найдены конкретные универсальные тест для исследуемых подклассов

Универсальный тест в классе (4,2,2) - автоматов вида А = ((Е2)2,Е2,Е2,8Д), где Е2 ={0,1}, по полученной ранее оценке имеет длину 524 306 символов Метод построения универсального теста, включает следующие этапы

- На множестве X - входном алфавите определяется линейный порядок х, ~<х2-< чхш

- Слово из старших по порядку "-<" букв xmxm .xm длины

n2+n-l, где п — максимальное количество состояний автоматов из тестируемого семейства, полагается префиксом универсального теста.

- Построенная часть универсального теста увеличивается добавлением справа на такую букву, которая вместе с n2 + п-2 последними буквами образует слово длины п2+п-1, не имеющее вхождение в уже построенную часть При этом должно выполняться условие добавляется буква, наименьшая по порядку среди букв, которые могут быть добавлены

Входной алфавит для класса (4,2,2) - автоматов состоит из двух символов Изменением задаваемого на множестве X порядка по предложенному методу можно получит два варианта универсального теста

-Вариант 1 На множестве X = {0,1} порядок "-<" задается по правилу-0 -< 1

-Вариант 2 На множестве Х = {0,1} порядок "-:" задается по правилу -1 ч 0

Для проверки возможности уменьшения длины универсального теста

были выбраны два способа сокращения

Метод суффиксного сокращение универсального теста

- построенный вариант универсальный теста побуквенно, начиная с первой, прилагается поочередно ко всем парам автоматов из исследуемого подкласса, образующим исключительные классы,

- по полученным выходным последовательностям определяется префикс универсального теста, на котором автоматы распознавались в паре,

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

Метод префиксного сокращения универсального теста

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

- длина полученного конечного отрезка универсального теста фиксируется для каждой пары автоматов,

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

В результате проведения вычислительного эксперимента в выбранных подклассах класса (4,2,2)-автоматов было установлено значительное сокращение оценки длины универсального теста

Теорема 2 В подклассе линейных автоматов Н, класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 24 символа,

- префикс 2-го варианта универсального теста длиной 24 символа,

- суффикс 1-го варианта универсального теста, длиной 22 символа,

- суффикс 2-го варианта универсального теста длиной 23 символа

Теорема 3 В подклассе самодвойственных автоматов Н8 класса

(4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 117 символа,

- префикс 2-го варианта универсального теста длиной 117 символа,

- суффикс 1-го варианта универсального теста, длиной 106761 символа,

- суффикс 2-го варианта универсального теста длиной 106761 символа

Теорема 4 В подклассе монотонных автоматов Нм класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 533 символа,

- префикс 2-го варианта универсального теста длиной 533 символа,

- суффикс 1-го варианта универсального теста, длиной 106765 символа,

- суффикс 2-го варианта универсального теста длиной 106765 символа

Теорема 5 В подклассе самодвойственных линейных автоматов Н^ класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 23 символа,

- префикс 2-го варианта универсального теста длиной 23 символа,

- суффикс 1-го варианта универсального теста, длиной 21 символа,

- суффикс 2-го варианта универсального теста длиной 22 символа Теорема 6 В подклассе самодвойственных монотонных автоматов

Нш класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 58 символа,

- префикс 2-го варианта универсального теста длиной 58 символа,

- суффикс 1-го варианта универсального теста, длиной 9368 символа,

- суффикс 2-го варианта универсального теста длиной 9368 символа

Теорема 7 В подклассе линейных монотонных автоматов Нш класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 22 символа,

- префикс 2-го варианта универсального теста длиной 22 символа,

- суффикс 1-го варианта универсального теста, длиной 20 символа,

- суффикс 2-го варианта универсального теста длиной 21 символа Теорема 8 В подклассе самодвойственных линейных и монотонных

автоматов Н5Ш класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе

- префикс 1-го варианта универсального теста, длиной 22 символа,

- префикс 2-го варианта универсального теста длиной 22 символа,

- суффикс 1-го варианта универсального теста, длиной 19 символа,

- суффикс 2-го варианта универсального теста длиной 19 символа Теоремы 2-8 показывают глубину сохранности свойства

универсального теста в зависимости от специфических свойств рассматриваемого подкласса автоматов Впервые показана возможность оценки проникновения универсального теста и различие префиксного и

суффиксного сокращений длины универсального теста

Полученные для класса (4,2,2)- автоматов результаты могут быть распространены на другие классы автоматов, если рассматривать класс (4,2,2) - автоматов как базисный класс для построения структурных автоматов большей размерности

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

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

Задача 1 Тестирование изолированной компоненты Задано Последовательность сигналов прикладывается к внутреннему входному узлу компоненты Ответная реакция наблюдается на внутреннем выходном узле компоненты

Требуется Найти последовательность Т входных сигналов, обладающую свойством теста для компоненты Задача 2 Задача управления

Задано Последовательность сигналов прикладывается к внешнему входному узлу системы Ответная реакция наблюдается на внутреннем выходном узле компоненты

Требуется Найти последовательность р входных сигналов системы, формирующую на внутреннем входном узле компоненты тест Т или его модификацию Т', обладающую свойством теста Задача 3 Задача наблюдения

Задано Последовательность сигналов прикладывается к внутреннему входному узлу компоненты. Ответная реакция наблюдается на внешнем выходном узле системы

Требуется Найти последовательность Т входных сигналов компоненты, обладающую свойством теста для компоненты такую, что диагностическая информация, полученная в результате тестирования компоненты будет наблюдаема на внешнем выходном узле системы

Рассмотрим следующую структурную схему (рис 1), представляющую собой последовательное соединение трех компонент

А, А2 Аз

Рис 1 Схема последовательного соединения трех компонент

В качестве компонент этой схемы будем рассматривать конечные детерминированные (4,2,2) - автоматы вида А, = ((Е2)2,Е2,Е2,5, Д), где Е2 = {0,1} Полученная схема - это структурный конечный детерминированный (64,2,2) - автоматом Областью определения такого

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

Диагностируемая компонента может располагаться в различных частях структурной схемы многокомпонентной системы Можно выделить три основных варианта расположения компоненты

Вариант 1) Входные узлы компоненты отождествлены с внешними входными узлами схемы, а выходные узлы компоненты являются внутренними узлами схемы (на рис 1 - компонента А|)

Вариант 2) Выходные узлы компоненты отождествлены с внешними выходными узлами схемы, а входные узлы компоненты являются внутренними узлами схемы (на рис 1 - компонента А3)

Вариант 3) Входные и выходные узлы компоненты являются внутренними узлами схемы (рис 1 - компонента А2)

Возможны также комбинации этих вариантов, например, в первом варианте только некоторые входные узлы компоненты отождествлены с внешними входными узлами, а остальные узлы — внутренние

Если математической моделью компоненты является конечный детерминированный автомат, то задача диагностирования компоненты (Задача 1) при всех основных вариантах ее расположения, может быть решена с помощью метода универсального тестирования автоматов Для этого необходимо найти решение задачи управления, которое формировало бы на входных узлах компоненты универсальный тест Для конкретной структурной схемы приведенной на рис 4 (если диагностируется компонента А2) это означает, что необходимо найти ограничения, налагаемые на компоненту А, и входное слово, что бы при приложении его к внешним входным узлам схемы, на внутренних входных узлах компоненты А2 формировался универсальный тест для (4,2,2)-автоматов

Определение 1 Будем говорить, что инициальный автомат (А,з0), где А = (8,Х,У,5,А.) транслирует универсальный тест р, если я=б(50,р) является универсальным тестом

Определение 2 Будем говорить, что инициальный автомат (А,з0), где А = (8,Х,У,5Д) тривиально транслирует универсальный тест р, если существует ф X —» У - биективное отображение такое, что ц = 8(з0,р) представляется в виде q = ф(рг,р)ф(рг2р) ф(ргир), где и = |р|

Определение 3 Будем говорить, что инициальный автомат (А,з0), где А = (5,Х,У,8Д) инвариантен относительно множества универсальных

тестов {р,},£1, где р,- универсальный тест, если инициальный автомат транслирует каждый тест из множества тестов, причем 1е[, для любого J 61

В работе исследуется возможность трансляции универсальных тестов компонентами структурных автоматов, в случае если они принадлежат специфическим классам конечных детерминированных автоматов Для исследования выбраны подклассы линейных, самодвойственных и монотонных (4,2,2) — автоматов

Вычислительный эксперимент состоит из нескольких этапов

- перечисляются все попарно неэквивалентные автоматы из выбранных подклассов,

- по алгоритму построения универсального теста, стоится вариант универсального теста при естественном порядке на множестве Е2 = {0,1}, состоящий из 524 306 символов,

- построенный вариант прилагается к инициальным автоматам из исследуемого подкласса,

- полученное выходное слово проходит проверку - является ли оно универсальным тестом (проверка осуществляется на основе представления универсального теста функцией к-значной логики)

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

Лемма 44 В классе (4,2,2) - автоматов содержится 84 попарно неэквивалентных линейных конечных детерминированных автомата Из 336 инициальных линейных конечных детерминированных автоматов 10 транслируют выбранный вариант универсального теста

Лемма 45 В классе (4,2,2) - автоматов содержится 356 попарно неэквивалентных самодвойственных конечных детерминированных автоматов Из 1424 инициальных самодвойственных конечных детерминированных автоматов 76 транслируют выбранный вариант универсального теста

Лемма 46 В классе (4,2,2) - автоматов содержится 1460 попарно неэквивалентных монотонных конечных детерминированных автоматов Из 5840 инициальных монотонных конечных детерминированных автоматов 81 транслируют выбранный вариант универсального теста

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

В заключении сформулированы основные результаты и выводы по диссертационной работе

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО ДИССЕРТАЦИИ

1 Доказано сокращение длин универсальных тестов для основных подклассов автоматов относительно универсальных тестов для всего класса (для линейных автоматов - на 5 порядков, для самодвойственных автоматов - на 5 порядков, для монотонных автоматов - на 4 порядка) и построены конкретные универсальные тесты в этих подклассах Для получения результатов в классе (4, 2, 2) - автоматов были разработаны алгоритмы и программы перечисления класса (4, 2, 2) - автоматов, выделения подклассов для исследования, построения пар автоматов, образующих исключительные классы, построения универсального теста, префиксного сокращения универсального теста, суффиксного сокращения универсального теста, нахождения наименьших универсальных тестов для линейных (4, 2, 2) — автоматов

2 Для исследования универсального тестирования композиций в классе (4, 2, 2) - автоматов разработаны алгоритмы и программы проверки трансляции универсальных тестов (4, 2, 2) - автоматами из конкретных подклассов автоматов - линейных, монотонных и тд Для исследуемых вариантов универсальных тестов показано, что они транслируются только некоторыми элементами последовательного соединения монотонных, линейных, самодвойственных автоматов Построены соответствующие подмножества транслирующих эти тесты и подмножества не транслирующих эти тесты (4, 2, 2) - автоматов Для класса линейных (по свойствам Поста) (4, 2, 2) — автоматов определен подкласс автоматов, любое (по порядку и числу элементов) последовательное соединение которых транслирует любой минимальный универсальный тест для класса линейных (4, 2, 2) — автоматов На основе этого впервые показано возможность универсального тестирования композиций универсальными тестами, построенными для элементов композиции Построены все такие тесты для подкласса линейных (4,2, 2) - автоматов

3 Полученные результаты доказывают возможность эффективного применения универсальных тестов в процедурах технического диагностирования и контроля дискретных детерминированных динамических систем Использование таких процедур повышает эффективность эксплуатации системы в работоспособном состоянии за счет сокращения времени их проведения и увеличения интервала эксплуатации системы Также при таком диагностировании повышается надежность технической системы, так как универсальный тест ориентирован не на конкретное семейство неисправностей, а на все возможные распознаваемые дефекты

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

Основные результаты диссертации опубликованы в работах:

1 Твердохлебов В А Классификация конечных автоматов по свойствам функций переходов и выходов /В А Твердохлебов, А В Пономаренко //Проблемы точной механики и управления Сб науч тр - Саратов, 2004 - С 16-25 (Пономаренко А В исследована предложенная классификация и выделены пустые и непустых классы конечных автоматов)

2 Пономаренко А В Параметры тестов для распознавания начального состояния в классе (4, 2, 2) - автоматов /А В Пономаренко //Проблемы точной механики и управления Сб науч тр - Саратов, 2004 - С 159-163

3 Пономаренко А В Исследование геометрических образов функционирования в классе (4, 2, 2) - автоматов /А В Пономаренко //Информационно-управляющие системы на железнодорожном транспорте - Харьков, 2004 - №4,5 - С 86-88

4 Пономаренко А В Минимизация универсальных тестов в классе (4, 2, 2) — автоматов /А В Пономаренко //Автоматизация проектирования дискретных систем Материалы V Межд конф -Минск, 2004 - Том 1 - С 211-216

5 Пономаренко А В Недостижимые траектории состояний при управлении автоматами из частных классов /А В Пономаренко //Аналитическая теория автоматического управления и ее приложения Труды 2-ой Межд науч конф - Саратов, 2005 - С 7980

6 Пономаренко А В Универсальные тесты для специальных классов конечных автоматов /А В Пономаренко //Радиоэлектронные и компьютерные системы - Харьков, 2006 - С 115-118

7 Пономаренко А В Оптимизация универсального тестирования поведения автоматов /А В Пономаренко //Интеллектуальные системы и компьютерные науки Материалы IX Межд конф -Москва, 2006 - Том 1. ч 2- С 213-215

8 Пономаренко А В Критерий трансляции универсального теста в композициях (4,2,2) - автоматов /А В Пономаренко //Проблемы и перспективы прецизионной механики и управления в машиностроении Материалы Межд конф - Саратов, 2006 - С 290295

9 Пономаренко А В Универсальное диагностирование в частных классах конечных автоматов /А В Пономаренко // Мехатроника, Автоматизация, Управление- Москва, 2006- №12- С17-24 (Журнал входит в Перечень периодических изданий, рекомендованных ВАК РФ для публикации основных результатов диссертаций на соискание ученой степени)

Подписано в печать 23 04 2007 Формат 60x84 1/16 Бумага офсетная Гарнитура Times New Roman Печать RISO Объем 1,0 печ л Тираж 100 экз Заказ №026

Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю Б Свидетельство № 3117 410600, Саратов ут Московская, д 152 офис 19 теп 26-18-19,51-16-28

ВВЕДЕНИЕ.

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ. ИССЛЕДОВАНИЕ НОВОЙ КЛАССИФИКАЦИИ АВТОМАТОВ. ВЫБОР ПОДКЛАССОВ ДЛЯ ИССЛЕДОВАНИЯ МИНИМИЗАЦИИ УНИВЕРСАЛЬНОГО ТЕСТИРОВАНИЯ.

1.1. Постановка задач минимизации универсальных тестов.

1.2. Описание используемой классификации конечных детерминированных автоматов.

1.3. Выбор подклассов для исследования минимизации универсальных тестов.

1.4. Некоторые замечания о выборе классов для исследования.

ГЛАВА 2. МИНИМИЗАЦИЯ УНИВЕРСАЛЬНЫХ ТЕСТОВ В ИССЛЕДУЕМЫХ ПОДКЛАССАХ.

2.1. Исследование структуры универсальных тестов.

2.2. Построение двух вариантов универсальных тестов для исследования

2.3. Сокращение универсальных тестов в выбранных подклассах.

2.4. Минимальные универсальные тесты в подклассе линейных (4,2,2) -автоматов.

ГЛАВА 3. УНИВЕРСАЛЬНОЕ ТЕСТИРОВАНИЕ КОМПОНЕНТЫ СТРУКТУРНОГО АВТОМАТА.

3.1. Общие положения структурной теории автоматов.

3.2. Задача тестирования компоненты структурного автомата.

3.3. Трансляция универсального теста в последовательной композиции автоматов.

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

В современных информационных технологиях конечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения: программное обеспечение, используемое для разработки и проверки цифровых схем; лексические анализаторы стандартных компиляторов; программное обеспечение для сканирования (поиск заданных слов, фраз и других шаблонов) больших текстовых массивов, таких как наборы Web-cтpaниц; программное обеспечение для проверки различного рода систем с конечным числом состояний (протоколы связи или защищенной передачи информации).

При разработке теоретических основ кибернетики многие сложные концепции и понятия были выработаны на базе теории конечных автоматов. Теория автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем. Универсальность теоретического и практического применения теории конечных автоматов определяет актуальность ее дальнейшего развития. Как показано выше, теория конечных автоматов имеет многочисленные приложения в технической и практической кибернетике и информатике, составляет важную часть дискретной математики и математической кибернетики.

Впервые, автоматы, как абстрактные модели нейронных сетей, были введены в 1943 году в работе Мак-Калокка и Питтса [1]. В дальнейшее автоматы неоднократно использовались для описания нейронных сетей [2].

Определение конечного детерминированного автомата как совокупности пяти объектов: А = (8,Х,У,8Д), где Б, X и У - конечные непустые множества, а 8 и X (функции переходов и выходов соответственно) - отображения вида: 8:8 х X -» 8 и А,: 8 х X -> У, введено в работе [3]. Такой тип автоматов получил название автоматы типа Мили. Другой основной тип конечных детерминированных автоматов - автоматы типа Мура введены в работе [4]. Конечный автомат типа Мура есть пятерка: объектов: А = (8,Х, У,8, ц), где 8, X и У-конечные непустые множества, а 8 и ц, (функции переходов и отметок состояния соответственно) - отображения вида: 8:8хХ-»8 и ц:8-»У. Равносильность двух этих типов автоматов показана во многих работах, например в работе [5]. Из работы Э. Мура [4] берет начало теория экспериментов с автоматами. В дальнейшем теория конечных автоматов и экспериментов с автоматами получила развитие во многих работах зарубежных и отечественных авторов (см., например [6 - 18]).

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

Эксперимент, требующий только одного экземпляра исследуемого автомата, называется простым. Эксперимент, требующий более одного экземпляра автомата, называется кратным.

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

1) Диагностическая задача. Задано:

- А = (Б, X, У, 8, X) - известный конечный детерминированный автомат;

- 80 с 8 - подмножество допустимых начальных состояний. Требуется:

- построить эксперимент, позволяющий определить, в каком именно из допустимых начальных состояний находился автомат А до проведения эксперимента, т. е. найти р еХ*, которое удовлетворяет предикату

Ув е БоХУб' е 80|){в Ф в'-> ЯГ(в,р) * .

2) Установочная задача. Задано:

- А = (8,Х, У,8Д) - известный конечный детерминированный автомат;

- 80 с 8 - подмножество допустимых начальных состояний. Требуется:

- построить эксперимент, позволяющий установить автомат А в известное конечное состояние, т. е. найти реХ*, которое удовлетворяет предикату (Ув^' е 80){5*(з,р) Ф 5*(б',р) -» (в, р) Ф А,*(б',р)} .

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

Эдвард Ф. Мур в 1956 г. в работе [4] показал, что существует решение установочной задачи с помощью простого безусловного эксперимента, предложил метод решения установочной задачи и нашел оценку длины эксперимента. Поиск решения предлагается осуществлять путем построения установочного дерева.

Теория экспериментов с дискретными динамическими системами с памятью является одной из важных проблем технической кибернетики. Целью эксперимента с реальной системой может быть построение математической модели системы, уточнение существующей модели системы или определение, какая модель из заданного семейства моделей является достаточно точной для данной системы. Последний тип эксперимента - задача диагностирования систем с памятью, - может решаться на основе методов теории экспериментов по распознаванию конечных автоматов в заданных семействах автоматов. Задача распознавания конечных автоматов, понимается как определение содержимого "черного ящика", т.е. расшифровки связей вход-выход, при условии, когда содержимое "черного ящика" принадлежит какому-либо известному семейству автоматов.

В 1962 году в работе [6] Артур Гилл свел задачу распознавания автомата в конечном семействе автоматов к установочной задаче. Задача распознавания автомат представляет собой определение (с точностью до изоморфизма), минимальной формы автомат путем проведения эксперимента.

На практике, часто возникает задача распознавания автомата, о котором известно, что он принадлежит к определенному конечному семейству автоматов, т.е. необходимо определить, каким из автоматов семейства а = {А;}м, где А! =(8|,Х,У,8!Д1)- конечный детерминированный автомат, является автомат А = (БД, У, 5, X). Решение этой задачи может быть найдено приложением такого слова р е X*, которое удовлетворяет предикату е 1)0/5 е ^о/з' е *} -> Х](з,р) * Х]@,р)}.

Критерием существования решения этой задачи является то, что семейство автоматов должно образовывать исключительный класс - ни одно состояние автомата А} недолжно быть эквивалентно никакому состоянию автомата Ар для любых [ ф], т. е. выполняется условие:

VI,] е 1)0/8 6 ЗДУз' е * } -> (Зи 6 Х*)Х](8,и) Ф и)}

Решение задачи распознавания автомата, предложенное А. Гиллом, сводится к замене семейства автоматов а = {А!}1-б1, где А1 =(81,Х,У,5|Д!), расщепляемым конечным детерминированным автоматом а-СиадУ.и^и*!). в который каждый автомат семейства входит как е1 1еI ¡€1 изолированный подавтомат, и решению для этого расщепляемого автомата установочной задачи методом Мура. А. Гиллом из оценки Мура для установочной задачи получена оценка длины 1 простого безусловного эксперимента для решения задачи распознавания автомата в семействе автоматов: 1 < (2п -1)(№1 -1), где п - максимальное число состояний автоматов семейства и N - число автоматов в семействе.

Метод решения задачи распознавания автомата в заданном семействе автоматов, предложенный А. Гиллом, имеет несколько существенных недостатков. Во-первых, так как для решения задачи необходимо построение установочного дерева, которое напрямую зависит от конкретных функций переходов и выходов автоматов заданного семейства, то построенный тест является неприменимым для тестирования другого, пусть даже очень близкого семейства автоматов. Во-вторых, отсутствует возможность сокращения длины теста, при условии, что автоматы исследуемого семейства обладают какими-либо специфическими свойствами.

В 1981-1982 годах на международных конференциях Твердохлебовым В. А. [19,20] был предложен метод универсального решения задачи распознавания автомат в заданном семействе автоматов.

Универсальным тестом в классе К(Х, п) семейств сравнимых конечных детерминированных автоматов с памятью по объему не превосходящих п состояний будем называть слово р е X*, которое для каждого семейства этого класса, удовлетворяющего условию исключительности, удовлетворяет условию: (VI, j е 1)(\/з е ^ХУэ' е вр^ * ] -> А,|(в,р) * ^(в'.р)}.

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

В дальнейших работах Твердохлебова В. А. с 1982 г. по 2005 г. (см., например [21-23]) продолжено исследование универсальных тестов - найдены оценки длины и методы построения универсальных тестов. Итоговые результаты работ по универсальному тестированию конечных детерминированных автоматов приведены в работе [23].

В работах Твердохлебовым В.А. были получены следующие результаты.

1) Доказано существование универсальных тестов в классе конечных детерминированных автоматов и найден критерий существования, совпадающий с критерием существования решения для задачи распознавания автомата по А. Гиллу.

2) Найдена оценка длины универсального теста: |р| < |Х|П +п1 + п2 + п - 2.

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

4) Показано, что универсальный тест может задаваться аналитической формулой для функции к-значной логики.

Как видно, из приведенной выше оценки, даже в случае сравнительно небольших размерности входного алфавита X и максимального числа состояний п универсальный тест имеет очень большую длину. Это делает его непригодным для практического использования. Так как оценка длины универсального теста не может быть понижена для общего случая, на основании результата Т. Хиббарда о достижимости оценки Э. Мура длины решения установочной задачи, универсальные тесты, предложенные Твердохлебовым В. А., получили только теоретическое значение. Однако практическое применение универсального тестирования могло бы значительно повысить эффективность процедур контроля и диагностирования технических систем.

Жизненный цикл технической системы можно представить как совокупность следующих этапов ее функционирования.

1. Функционирование системы в работоспособном состоянии, когда управление осуществляется в штатном режиме.

2. Контроль исправности состояния системы и принятие решение о возможности дальнейшей эксплуатации.

3. Диагностирование системы, т. е. локализация дефекта возникшего в системе по месту или функции.

4. Ремонт системы - восстановление ее работоспособности с первоначальной функциональностью.

5. Модернизация системы - восстановление ее работоспособности с улучшением технических характеристик системы и повышением ее функциональных возможностей.

6. Частичное восстановление системы - восстановление с ухудшением ее характеристик и функциональных возможностей.

7. Вывод системы из эксплуатации.

Взаимосвязь описанных выше этапов приведена на рис. 1.

Рис. 1. Схема функционирования технической системы при использовании в процедурах контроля и диагностирования частных тестов.

Точка 1 - точка начала контрольных процедур определяется:

- расчетным путем, во время проектирования системы;

- появлением в работе системы явных дефектов;

- срабатыванием аварийной сигнализации и т.д.

Для выполнения процедур контроля используется некоторый тест р^Х*, направленный на выявление конкретного класса дефектов р1={{А1,11,61,»{А|2}|2е,2,.,{А^}1ке1к} - множество подмножеств автоматов, распознаваемых на слове р| е X*, жестко зависящим от распознаваемого класса дефектов методом Мф) (Решение задачи распознавания автомата по А. Гиллу). Любое слово из символов входного алфавита может рассматриваться как тест для системы, поэтому множество тестов бесконечно.

Точка 2 - точка принятия решения о дальнейшей эксплуатации системы. Если при проведении контрольных процедур было установлено, что система находится в работоспособном состоянии, то продолжается ее дальнейшая эксплуатация, иначе проводиться диагностика системы. В точке 3 анализируются результаты диагностирования, и принимается решение о возможности ремонта системы или о выводе ее из эксплуатации.

Подобное описание является устоявшимся представлением жизненных циклов сложных систем и отражено в работах многих авторов (см., например,

25-29]). Недостатком такого подхода является то, что тест pi е X* строиться методом М(Р;), зависящим от конкретного подкласса дефектов е1, '{А|2 }\2€12.{А(к }|ке1к}» и не может быть использования для проверки системы на другие неисправности. Поэтому изменение выбранного подкласса неисправностей (как во время проектирования системы, так и во время ее эксплуатации) требует нового применения метода для построения нового теста.

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

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

При универсальном тестировании в процедурах контроля и диагностирования используется тест реХ*- универсальный тест, на котором распознаются все распознаваемые классы дефектов ^, методом М(тах|8|,|Х|), зависящим только от мощности входного алфавита и глубины памяти технической системы. Универсальное тестирование повышает надежность и эффективность управления системой в работоспособном состоянии. Повышение надежности осуществляется за счет замены наборов частных тестов (тестов, ориентированных на конкретное подмножество неисправностей) общим тестом, предельно расширяющим анализируемое множество неисправностей. Это позволяет увеличить продолжительность этапов эксплуатации системы и уменьшить количество этапов контроля и диагностирования. Эффективность управления повышает за счет сокращения временных интервалов для контроля и диагностирования на этапе эксплуатации системы, и за счет упрощения разработки процедур контроля и диагностирования на этапе проектирования системы.

Как было замечено ранее, значительным недостатком универсальных тестов, предложенных В. А. Твердохлебовым, явилась их большая длина. Так, например, по полученной оценки, универсальный тест для относительно простой дискретной технической системы с объемом памяти 25 и четырьмя двоичными входами имеет длину 2 * Ю1270символов.

В диссертации предлагается новый подход к построению универсальных тестов, основанный на использовании специфических свойств диагностируемых систем, исследуется возможность сокращения универсального теста в некоторых специфических классах автоматов. Для выделения классов автоматов используется предложенная Твердохлебовым В. А. в работах [29,30] в 2003-2004 годах классификация автоматов по свойствам их функций переходов и выходов, основанная на фундаментальной классификации Поста для функций алгебры логики. Исследование сокращения оценки длины универсального теста выполнено в подклассах класса (4,2,2) -автоматов: линейных; самодвойственных; монотонных; линейных и самодвойственных; линейных и монотонных; монотонных и самодвойственных; линейных, самодвойственных и монотонных автоматов.

Диссертационная работа состоит из трех глав основного текста.

В первой главе предлагается новый подход к универсальному тестированию, основанный на специфических свойствах автоматов. Исследуется классификация автоматов на основе свойств Поста функций переходов и выходов комбинационных частей автоматов. Предложенная Твердохлебовым В.А. классификация автоматов не была исследована. В этой главе доказываются леммы, на основании которых выделяются пустые и непустые классы автоматов. Далее строится решетка подклассов в классе (4, 2, 2) - автоматов и рассматривается распределение автоматов по подклассам. Выделяются для исследования минимизации универсальных тестов семь подклассов и находятся их количественные характеристики. Все полученные результаты сформулированы в виде лемм и теорем. Так же приведены описания алгоритмов, используемых для распределения автоматов по классам.

Во второй главе проводиться выбор двух вариантов универсальных тестов, которые используются для исследования сокращения оценки длины универсального теста в подклассах линейных; самодвойственных; монотонных; линейных и самодвойственных; линейных и монотонных; монотонных и самодвойственных; линейных, самодвойственных и монотонных (4, 2, 2) -автоматов. Дополнительно исследована структура универсальных тестов, показано, что по структуре они совпадают с последовательностями де Брюина. Доказаны леммы, позволяющие представлять последовательности де Брюина в двоичном алфавите функциями алгебры логики, полином Жегалкина которых имеет достаточно простую структуру. Сокращение универсальных тестов выполнено двумя методами: суффиксное и префиксное сокращение. Полученные оценки сформулированы в виде теорем. Так же в этой главе представлены минимизированные универсальные тесты для исследуемых подклассов. Более подробно рассмотрен подкласс линейных автоматов, для которого найдены минимальные по длине универсальные тесты.

В третье главе диссертационной работы рассмотрена задача тестирования автомата представленного последовательной композицией автоматов из исследованных подклассов. Задача тестирования композиции автоматов рассматривается как совокупность трех задач: задачи тестирования изолированной компоненты, задача управления и задача наблюдения. Для решения задачи тестирования изолированной компоненты используются полученные минимизированные универсальные тесты. Задачи наблюдения и управления могут быть решены при условии трансляции универсального теста внутрь композиции автоматов. Получены семейства автоматов, которые содержаться в исследуемых подклассах, и транслируют универсальные тесты. Полученные результаты сформулированы в виде лемм и теорем.

Большинство полученных в работе результатов носят количественный характер. Поэтому для получения этих результатов использовался метод доказательного вычислительного эксперимента. В таких полных вычислительных экспериментах исключаются интерполяция и экстраполяция, вероятностные процедуры, основным является логический вывод на основе полного перебора исследуемых объектов. Такой подход обосновывается в работах академика А.П. Ершова и H.H. Моисеева (см., например [31,32]).

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

Осуществление переборов с использованием ЭВМ принципиально расширяет возможности получения результатов, имеющих явную конструктивную форму. Количественные отношения, полученные в диссертации, требуют непосредственного использования вычислительных процедур большого объема, что возможно в рамках одного исследования только с использованием ЭВМ.

ЗАКЛЮЧЕНИЕ

В результате проведения диссертационного исследования было доказано значительное сокращение длин универсальных тестов для основных подклассов автоматов относительно универсальных тестов для всего класса (для линейных автоматов - на 5 порядков, для самодвойственных автоматов - на 5 порядков, для монотонных автоматов - на 4 порядка) и найдены конкретные минимизированные универсальные тесты в подклассах линейных (4,2,2)-автоматов, самодвойственных (4,2,2) - автоматов, монотонных (4,2,2)-автоматов, линейных и самодвойственных (4,2,2) - автоматов, линейных и монотонных (4,2,2) - автоматов, самодвойственных и монотонных (4,2,2)-автоматов, линейных, самодвойственных и монотонных (4,2,2) - автоматов. Для линейных (4, 2. 2) - автоматов были определены минимальные универсальные тесты.

Для получения численных характеристик исследуемых подклассов и проведения минимизации универсальных тестов в этих подклассах были разработаны алгоритмы и программы: перечисления класса (4, 2, 2) -автоматов; выделения подклассов для исследования; построения пар автоматов, образующих исключительные классы; построения универсального теста; префиксного сокращения универсального теста; суффиксного сокращения универсального теста; нахождения наименьших универсальных тестов для линейных (4,2,2) - автоматов.

Для исследования универсального тестирования композиций в классе (4, 2, 2) - автоматов разработаны алгоритмы и программы проверки трансляции универсальных тестов (4, 2, 2) - автоматами из конкретных подклассов автоматов - линейных, монотонных и т.д. Для исследуемых вариантов универсальных тестов показано, что они транслируются только некоторыми элементами последовательного соединения монотонных, линейных, самодвойственных автоматов. Построены соответствующие подмножества транслирующих эти тесты и подмножества не транслирующих эти тесты (4, 2,

2) - автоматов. Для классов линейных, монотонных, самодвойственных (4, 2, 2) - автоматов определены подклассы автоматов, любое (по порядку и числу элементов) последовательное соединение которых транслирует любой минимальный универсальный тест для класса линейных (4, 2, 2) - автоматов. На основе этого впервые показано возможность универсального тестирования композиций универсальными тестами, построенными для элементов композиции.

Полученные результаты доказывают возможность эффективного применения универсальных тестов в процедурах технического диагностирования и контроля дискретных детерминированных динамических систем. Использование таких процедур повышает эффективность эксплуатации системы в работоспособном состоянии за счет сокращения времени их проведения и увеличения интервала эксплуатации системы. Также при таком диагностировании повышается надежность технической системы, так как универсальный тест ориентирован не на конкретное семейство неисправностей, а на все возможные распознаваемые дефекты.

Результаты, изложенные в диссертационной работе прошли научную апробацию на семи международных конференциях. По результатам исследований в период с 2004 по 2006 годы было опубликовано 9 статей [30, 51-58] в том числе статья в журнал, входящем в Перечень периодических изданий, рекомендованных ВАК РФ для публикации основных результатов диссертаций на соискание ученой степени [58].

Выражаю глубочайшую признательность научному руководителю академику РАЕН и АВН, доктору технических наук, профессору Владимиру Александровичу Твердохлебову за постановку задач исследования, постоянное внимание к работе и обсуждение полученных результатов.

1. McCulloch W.S., A logical calculus of the ideas immanent in nervous activity /W.S. McCulloch, W. Pitts//Bulletin of Mathematical Biophysics.- 1943.-№5.- p. 115-133.

2. Клини С. К. Представление событий в нервных сетях и конечных автоматах //Сб. "Автоматы" под ред. К. Э. Шеннона и Дж. Маккарти: Пер. с англ.—М.: ИЛ, 1956.-С. 15-67.

3. Mealy G.H. Method for synthesizing sequential circuits /G.H. Mealy //Bell System Techn.- 1955.-J. 34.-p. 1045-1079.

4. Мур Э. Ф. Умозрительные эксперименты с последовательностными машинами /Э.Ф. Мур //Автоматы: Сб. под ред. К.Э. Шеннона и Дж. Маккарти.-Пер. с англ.- М.:ИЛ.- 1956.- С. 179-212.

5. Блох А.Ш. О задачах, решаемых последовательностными машинами /А.Ш. Блох //Проблемы кибернетики: Сб. статей под ред. A.A. Ляпунова.- М., 1960.-Вып.З.- С. 81—88.

6. Гилл А. Введение в теорию конечных автоматов /А. Гилл,- Пер. с англ.- М.: Изд-во «Наука», 1966.- 272 с.

7. Глушков В. М. Абстрактная теория автоматов / В. М. Глушков // Успехи матем. наук.-1961.-Т. 16, № 5.-С. 3-62.

8. Логика. Автоматы. Алгоритмы /М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр и др.- М.: Физматгиз, 1963.- 556 с.

9. Ю.Спивак М.А. Введение в абстрактную теорию автоматов / М.А. Спивак.-Саратов: Изд-во Сарат. ун-та, 1970.- 108 с.

10. Минский М. Вычисления и автоматы /М. Минский,- Пер. с англ.- М.: Мир, 1971.-364 с.

11. Трахтенброт Б. А. Конечные автоматы. Поведение и синтез /Б. А. Трахтенброт, Я.М. Барздинь.- М.: Наука, 1970.- 400 с.

12. Богомолов A.M. Эксперименты с автоматами /A.M. Богомолов, A.C. Барашко, И.С. Грунский.- Киев: Наук, думка, 1973.- 144 с.

13. Н.Богомолов A.M. Контроль и преобразования дискретных автоматов /A.M. Богомолов, И.С. Грунский, Д.В. Сперанский.- Киев: Наук, думка, 1975.- 174 с.

14. Брауэр В. Введение в теорию конечных автоматов /В. Брауэр.- Пер. с нем.-М.: Радио и связь, 1987.- 392 с.

15. Твердохлебов В. А. Логические эксперименты с автоматами /В. А. Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 1988.- 184 с.

16. Карпов Ю.Г. Теория автоматов /Ю. Г. Карпов.- СПб.: Питер, 2002.- 224 с.

17. Хопкрофт Дж. Ведение в теорию автоматов, языков и вычислений /Дж. Хопкрофт, Р. Мотвани, Дж. Ульман.- Пер. с англ.- М.: Издательский дом "Вильяме", 2002.- 528 с.

18. Твердохлебов В. А. Универсальное решение задачи распознавания автоматов /В. А. Твердохлебов // Методы и системы технической диагностики.-Саратов: Изд-во Сарат. ун-та, 1981.- Вып. 2.

19. Твердохлебов В. А. Универсальные генераторы тестов и системы диагностирования /В. А. Твердохлебов / Техническая диагностика,- Ростов-на/Д.: Изд-во РИСИ, 1982.

20. Твердохлебов В.А. Детерминированная и вероятностная оценки универсальных тестов /В. А. Твердохлебов //Марковские случайные процессы и их применение.- Саратов: Изд-во Сарат. ун-та, 1988.- Вып. 4.

21. Богомолов A.M. Диагностика сложных систем /A.M. Богомолов, В.А. Твердохлебов.- Киев: Наук, думка, 1974.- 128 с.

22. Пархоменко П.П. Основы технической диагностики: (Оптимизация алгоритмов диагностирования, аппаратурные средства) / П.П. Пархоменко, Е.З. Согомонян //Под ред. П.П.Пархоменко. М.: Энергия, 1981. - 320 с.

23. Резчиков А.Ф. Управление и диагностирование в сложных системах /А.Ф.Резчиков, В.А.Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 1997.- 128 с.

24. Резчиков А.Ф. Управление жизненными циклами сложных систем /А.Ф.Резчиков, В.А.Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 2000.- 110с.

25. Смирнов А.К. Управление жизненными циклами сложных систем /А.К.Смирнов, В.А.Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 2000,- 130с.

26. Твердохлебов В.А. Классификация конечных автоматов и информационные технологии в техническом диагностировании /В.А. Твердохлебов //Высокие технологии путь к прогрессу. - Саратов: Изд-во «Научная книга», 2003.- с. 9398.

27. Твердохлебов В.А Классификация конечных автоматов по свойствам функций переходов и выходов /В.А Твердохлебов, A.B. Пономаренко //Сб. научных трудов ИПТМУ РАН.- Саратов: Изд-во СГТУ, 2004.- с. 16-25.

28. Ершов А.П. Научные основы доказательного программирования / А.П. Ершов //Вестн. АН СССР, 1984.- № ю.- С. 9-19.

29. Моисеев H. Н. Математика ставит эксперимент /Н. Н. Моисеев,- М,: Наука, 1979.- 224 с.

30. Post Е. Introduction to a general theory of elementary propositions /Е. Post //Amer. J. Math.-1921.- №43.- p. 163-185

31. Яблонский C.B. Функции алгебры логики и классы Поста /С. В. Яблонский, Г. П. Гаврилов, В. Б. Кудрявцев.- М.: Наука, 1966.- 120 с.

32. Яблонский C.B. Ведение в дискретную математику /С. В. Яблонский.- М.:1. Высш. шк., 2002.- 384 с.

33. Марченков С.С. Замкнутые классы булевых функций /С.С. Марченков.- М.: ФИЗМАТЛИТ, 2000.- 128 с.

34. Сидоренко О. И. Секреты логической зависимости /О.И. Сидоренко.-Саратов: Изд-во Сарат. ун-та, 2001,- 56 с.

35. Токхейм Я. Основы цифровой электроники /Я. Токхейм.- М.: Мир, 1988.420 с.39.0падчий Ю.Ф. Аналоговая и цифровая электроника /Ю.Ф. Опадчий.- М.: Радио и связь, 1996,- 768 с

36. Миловзоров О. В. Электроника /О. В. Миловзоров, И.Г. Панков.-М.: Высш. шк., 2005.- 288 с.41.de Bruijn N.G. A Combinatorial Problem /N.G. de Bruijn //Nederl. Akad. Wetensch. Proc., 1946.- vol. 49.- p. 758-764

37. Lippel B. A Method for Obtaining Complete Digital Coding Chains /В. Lippel, I.J Epstein //IRE Trans., 1957.- vol. EC-6.- p. 121.

38. Глушков В. M., Некоторые проблемы синтеза цифровых автоматов /В.М. Глушков //Жур. вычислительной математ. и матем. физики.- т. 1, № 3,1961.

39. Глушков В.М. Синтез цифровых автоматов /В.М. Глушков.- М:, Физматгиз, 1962.- 476 с.47.3акревский А. Д. К синтезу последовательностных автоматов / А. Д. Закревский //Труды Сибирского физико-технического ин-та.- вып. 40,1961.

40. Поспелов Д.А. Логические методы анализа и синтеза схем /Д.А Поспелов-М.: Энергия, 1974.- 368 с.

41. Гаврилов М.А. Композиция и декомпозиция комбинационных автоматов /М.А. Гаврилов //В кн.: Теория автоматов.- М.: Наука, 1976,-с. 34-71.

42. Гаврилов М.А. Логическое проектирование дискретных автоматов / М.А. Гаврилов, В.В. Девятков, Е.И Пупырев.- М.: Наука, 1977.-352 с.

43. Пономаренко А. В. Параметры тестов для распознавания начального состояния в классе (4, 2, 2) автоматов /А. В. Пономаренко //Проблемы точной механики и управления: Сб. науч. тр.- Саратов, 2004.- С. 159-163.

44. Пономаренко А. В. Исследование геометрических образов функционирования в классе (4, 2, 2) автоматов /А. В. Пономаренко //Информационно-управляющие системы на железнодорожном транспорте.-Харьков, 2004.- №4,5.- С.86-88.

45. Пономаренко А. В. Минимизация универсальных тестов в классе (4, 2, 2) -автоматов /А. В. Пономаренко //Автоматизация проектирования дискретных систем: Материалы V Межд. конф.- Минск, 2004.- Том 1.- С.211-216.

46. Пономаренко А. В. Недостижимые траектории состояний при управлении автоматами из частных классов /А. В. Пономаренко //Аналитическая теория автоматического управления и её приложения: Труды 2-ой Межд. науч. конф.-Саратов, 2005.- С.79-80.

47. Пономаренко А. В. Универсальные тесты для специальных классов конечных автоматов /А. В. Пономаренко //Радиоэлектронные и компьютерные системы,- Харьков, 2006.- С. 115-118.

48. Пономаренко А. В. Оптимизация универсального тестирования поведения автоматов /А. В. Пономаренко //Интеллектуальные системы и компьютерные науки: Материалы IX Межд. конф.- Москва, 2006.- Том 1. ч.2- С.213-215.

49. Пономаренко А. В. Критерий трансляции универсального теста в композициях (4,2,2) автоматов /А. В. Пономаренко //Проблемы и перспективы прецизионной механики и управления в машиностроении: Материалы Межд. конф.- Саратов, 2006.- С.290-295

50. Пономаренко А. В. Универсальное диагностирование в частных классах конечных автоматов /А. В. Пономаренко //Мехатроника, Автоматизация, Управление.- Москва, 2006.- №12.- С. 17-24.