Автоматов Композиции

направление в автоматов теории, характеризующееся использованием алгебраич. Средств в изучении автоматов. А. А. Т. Основана на том, что автоматы можно рассматривать как нек-рые специальные алгебры или алгебраические системы. Кроме того, события, представимые конечными автоматами, относительно операций объединения, произведения и итерации образуют алгебру, порождаемую конечным множеством так наз. Элементарных событий, каждое из к-рых состоит из одного одно-буквенного или пустого слова. Алгебраи..

отображение входного и выходного алфавитов, а также множества состояний одного автомата в аналогичные множества другого автомата, сохраняющее функции переходов и выходов. Более точно А. Г. Автомата в автомат (см. Автомат конечный) - это отображение множества в множество такое, что и для любых s из S1 и аиз А 1 имеют место равенства. Для автоматов инициальных, кроме того, требуется, чтобы функция hначальное состояние переводила в начальное. Автоматы наз. Гомоморфными, если сущес..

минимизация значений параметров автоматов, приводящая к эквивалентным и в определенном смысле оптимальным автоматам. Задача А. М. Возникает при синтезе автоматов, и ее специфика зависит от подхода к их изучению. При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. Так, если в качестве поведения автомата конечного, заданного, напр...

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