Конечный автомат: различия между версиями

''Берем автомат без выхода. Обозначаем состояния и входные сигналы натуральными числами. Фиксируем значение входного сигнала и начинаем прогонять автомат на этом постоянном сигнале от начального состояния до зацикливания. Получаем конечную таблицу значений зависимости следующего состояния от предыдущего. Интерполируем эту функцию полиномом Лагранжа, который единственен и имеет степень длины полученного цикла. Затем из полученных полиномов по тем же известным правилам строим полином, отвечающий любым значениям входного сигнала. И получает воo-оот такое здоровенное аналитическое выражение для функции состояния s(t+1)=f(s(t),x(t)), чем по идее и решается задача синтеза...Ну а оптимизация сводится к тому, чтобы это выражение упростить.  ''

Да, например, для простенькой задачки из учебника Гилла (пример1 "Введение в теорию конечных автоматов" Пример №1):

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