АВТОМАТ СВОБОДНЫЙ.

Автомат можно рассматривать как унарную универсальную алгебру (см. Автоматов способы задания). Автомат наз. свободным, если алгебра А — свободная. Напр., пусть дано два непересекающихся множества Q и X. Образуем множество слов А таких, что первая их буква — элемент множества Q, а все остальные (если они имеются) — элементы множества X. Образуем теперь из полученного множества слов А автомат следующим образом. Каждое слово из А назовем состоянием автомата ), каждый элемент назовем входом автомата и, по определению, будем считать, что состояние под действием входа переходит в состояние где слово из А, полученное приписыванием справа к слову q буквы Полученный автомат будет А. с. (с множеством свободнообразующих состояний Q и свободнообразующих входов X). Верно утверждение: любой другой автомат (с множеством образующих состояний Q и образующих входов X) является гомоморфным образом А. с.

М. И. Кратко.