определение: 1. Конечный автомат будем представлять как пятерку объектов: -, где входной алфавит ; — алфавит (множество) состояний содержит n элементов, начиная с нуля ; — выходной алфавит ; -отображения (функция) переходов ; — отображения (функция) выходов
Если не оговорено особо, начальное состояние автомата является , а заключительное . Если отображения и — функции, то автомат детерминированный, в противном случае автомат недетерминированный.
определение: 2. Конечный автомат называется полным, если для всех упорядоченных пар имеется команда вида . Из автоматного отображения (функции) , определены во всех точках. Это означает, что в автоматной таблице не существует пустых клеток, кроме разве что столбца соответствующего заключительному состоянию .
определение: 3. Автоматное отображение – это соответствие, отображающее входные строки конечного автомата в выходные.
Пусть задан конечный автомат . Подавая на его вход всевозможные строки в алфавите , на выходе получаем строки в алфавите т.е. конечный автомат есть отображение универсального множества над алфавитом в универсальное множество над алфавитом .

Если задана строка то, будучи поданная на вход конечного автомата, приводит к появлению на выходе строки , что записывается так: . — будем называть автоматным оператором.
Пусть строка есть (последовательностью ) : .
Индуктивное определение автоматного оператора, т.е. когда длина строки равна:1. ; . ; +1. ;
Свойства автоматного отображения
1. Свойство сохранения длины: пусть , где .
2. Отсутствие предвосхищения: если строку мы представили, как и нам известно, что и если , то , иначе говоря, образ отрезка длины равен отрезку образа той же длины, т.е. автоматный оператор перерабатывает строку слева на право, не заглядывая вперед или же — ый знак выходной строки зависит только о первых — знаков входной строки.
определение: 4. Достижимое состояние. Состояние называется достижимым из состояния , если существует такая входная строка , что  .

определение: 5. Сильно связный автомат – это такой автомат, когда из любого его состояния достижимо его любое другое состояние, т.е. на графе автомата существует путь соединяющий любые его две вершины.
определение: 6. Автоматный автомат (генератор) – это автомат, у которого входной алфавит состоит из одного знака , иногда говорят, что вход это вход синхронизаций, задающий такты работы автомата.
Гомоморфизм и изоморфизм
Пусть заданы два конечных автомата и
определение: 7. Гомоморфизмом автомата в автомат — называется тройка функций: ; ; ; Гомоморфизм означает, что существует такое переименование алфавитов, которое переводит функцию в , а в .

определение: 8. Изоморфизмом называется взаимно однозначный гомоморфизм. При изоморфизме происходит замена одного знака алфавита, на знак другого алфавита, это взаимно однозначно, в то время как при гомоморфизме происходит склеивание знаков (совмещение).
Пример

состояния 1 и 2 склеены, следовательно
определение: 9. Неотличимые состояния. Два состояния и называются неотличимыми, если для всех строк .
определение: 10. Автоматы и называются неотличимыми, если для каждого состояния автомата существует единственное состояние , такое что , , .
определение: 11. Эквивалентные автоматы – это такие автоматы и , когда для любого состояния автомата найдется неотличимое от него состояние автомата .