3 Модели и методы для обоснования выбора состава аппаратных средств ВС

Анализатор некорректного поведения минимизированных

конечно-автоматных моделей

 

 

Д.А. Орлов, студ.; В.Ю. Харитонов, студ.; научн. рук. И.И. Дзегелёнок., д.т.н., проф.

 

 

(МЭИ (ТУ))

 

 

 

 

 

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

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

Рассмотрим подробнее алгоритм. Вначале происходит минимизация исходного автомата Мили. Этот процесс состоит из 3 основных этапов: удаление недостижимых состояний, «склеивание» совместимых состояний (методом Глушкова). Затем происходит выявление всех последовательностей, реакция на которые исходного и минимизированного автоматов различаются. Данный алгоритм реализован программно в 32-разрядном Windows-приложении, условно названном «Анализатор катастроф». Помимо основной функции в программе также реализованы: загрузка автоматной модели из файла, сохранение модели в файле. Также предусмотрено выполнение произвольной заданной входной последовательности. Программа написана в среде Borland Delphi.