Методы абстрактного синтеза

Определение абстрактного управляющего автомата (УА) совпадает с хорошо известным определением детерминированного конечного автомата:

,

где Х – алфавит входных сигналов; S – множество внутренних состояний; У – алфавит выходных сигналов, s ₁ – начальное состояние ; , – алфавитные отображения такие что

(1.1)

В зависимости от способов конкретизации отображений (1.1) могут быть определены различные модели управляющего автомата. Наибольшее распространение получили модели Мили и Мура, правильный выбор которых дает определенные преимущества при решении конкретных задач синтеза управляющих автоматов [1 – 4].

Под задачей абстрактного синтеза управляющего автомата будем понимать восстановление, отображений (1.1) в классе моделей Мили или Мура по формализованному (но не словесному!) описанию его «внешнего» поведения.

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