АВТОМАТ СВОБОДНЫЙ.
Автомат можно рассматривать как унарную универсальную алгебру

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

следующим образом. Каждое слово из А назовем состоянием автомата

), каждый элемент

назовем входом автомата

и, по определению, будем считать, что состояние

под действием входа

переходит в состояние

где

слово из А, полученное приписыванием справа к слову q буквы

Полученный автомат будет А. с. (с множеством свободнообразующих состояний Q и свободнообразующих входов X). Верно утверждение: любой другой автомат (с множеством образующих состояний Q и образующих входов X) является гомоморфным образом А. с.
М. И. Кратко.