Интегрированная среда автоматизированного синтеза
конечных автоматов
М.В. Грешилова, С.Г. Калашников, А.А. Лебедь, А.В. Логинов, А.А.
Фролова, студенты; рук. И.И. Дзегеленок, д. т. н., проф.
(МЭИ(Технический
университет) г.Москва Россия)
Разработка конечных
автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем.
Они во многом проясняют причины, по которым необходимо систематическое развитие
теории алгоритмов и теоретического
программирования, сопровождаемого подробным анализом корректности и сложности
реализуемых алгоритмов [1]. Теория
автоматов имеет многочисленные практические приложения, связанные как с
разработкой компактных и емких по содержанию математических моделей управления,
так и с синтезом цифровых устройств [2]. В
этой связи знание методов теории автоматов необходимо многим
специалистам в области логического проектирования моделей, схем и устройств
управления различного назначения.
Разработанная
авторами интегрированная среда автоматизированного синтеза базируется на
известных методах теории автоматов, позволяет на практических примерах повысить
эффективность построения автоматных моделей и при этом значительно упростить
работу пользователя.
Программный
комплекс осуществляет синтез абстрактной модели автомата одним из двух
возможных способов.
1.Построением
дерева управления.
В данном методе пользователю
предлагается ввести в качестве исходных данных входной алфавит, выходной
алфавит и дерево управления (первоначально хотя бы один ярус), а в качестве
результата получается минимизированный автомат Мили (его таблица переходов).
2.Использованием регулярных выражений.
Здесь необходимо указать
входной и выходной алфавиты, регулярные выражения и соответствующие им реакции
(из выходного алфавита), а результатом операции синтеза являются первичный и
минимизированный автоматные операторы Мили или Мура (их таблицы переходов) и
соответствующие им графы.
Далее синтезированные
конечно–автоматные модели по желанию проектировщика могут быть преобразованы в
функционально-логическую схему создаваемого устройства управления. Программно
реализованная методика структурного синтеза
позволяет по таблице переходов автомата построить логические функции
возбуждения для D- и T-триггеров, функции выходов
автомата, а также получить логические выражения отмеченных функций для
последующего структурного построения автомата из элементарных автоматов.
Комплекс содержит базу данных,
в которую автоматически записываются уже решенные задачи синтеза автоматных
моделей, на основе которых пользователь может легко обучаться работе в
автоматизированной среде. Интуитивно понятный интерфейс и наличие системы
подсказок обеспечивают удобное взаимодействие с программой.
Литература
1.
Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию
автоматов, языков и вычислений, 2-е изд.: Пер. с англ. М.: Издательский дом
«Вильямс», 2002. 528 с.
2.
Теория автоматов/ Ю.Г. Карпов и др. СПб.: Питер, 2002. 224 с.