Интегрированная среда автоматизированного синтеза

конечных автоматов

М.В. Грешилова, С.Г. Калашников, А.А. Лебедь, А.В. Логинов, А.А. Фролова, студенты; рук. И.И. Дзегеленок, д. т. н., проф.

(МЭИ(Технический университет) г.Москва Россия)

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

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

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

1.Построением дерева управления.

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

2.Использованием регулярных выражений.

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

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

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

Литература

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

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