Конечным автоматом (просто автоматом) называется система (пятерка) [19]:
S=<X,Y,Z,j,y>,
в которой Х={х1,х2,...,хi} – конечное входное множество (входной алфавит); Y={y1,y2,...,yj} – конечное множество внутренних состояний автомата (алфавит состояний); Z={z1,z2,...,zk} – конечное выходное множество (выходной алфавит); j – функция переходов (из состояния в другие состояния); y – функция выходов.
Если указанные множества бесконечные, то это уже не конечный автомат, но может быть дискретный автомат.
Если функция переходов – вероятностная, то это недетерминированный автомат.
Если в автомате выделено одно состояние, называемое начальным (обычно это y1), то полученный автомат называется инициальным и обозначается <S,y>. Таким образом, по неинициальному автомату с i состояниями можно i различными способами определить инициальный автомат.
Функция переходов представляет собой отображение вида j: 
или в другом виде:
y(t+1)=j[x(t),y(t)],
где x(t),y(t),y(t+1) – конкретные символы алфавитов Х и Y соответственно в моменты автоматного времени t, t+1 (в тактах t и t+1); y(t) называется текущим внутренним состоянием при соответствующем х(t), а y(t+1) – последующим внутренним состоянием.
Иначе говоря, функция переходов определяет последующее состояние автомата по заданному текущему и входному символу.
Функция выходов представляет собой отображение вида y: Х´Y®Z или в другом виде:
z(t)=y[x(t),y(t)],
где x(t),y(t),z(t) – конкретные символы алфавитов X,Y,Z соответственно. Мы не будем особо выделять последующие значения x(t+1) и z(t+1), поэтому зависимость от t будем указывать только для внутреннего состояния, чтобы отделять y(t) от y(t+1).
Указанная функция выходов – функция так называемого автомата Мили.
В теории конечных автоматов рассматривается также автомат Мура, у которого функция выходов проще: y: 
или z(t)=y[y(t)].
Автомат называется комбинационным, если для любого входного символа х и любых состояний yi, yj j(х,yi)=j(х,yj)=z, иначе говоря, если выходной символ z не зависит от состояния и определяется текущим входным символом. Говорят, что у такого частного класса автомата все состояния эквивалентны и, следовательно, комбинационный автомат имеет одно состояние. Такой автомат задается тройкой:
S=<X,Z,y>.
Рассмотрим представление конечного автомата в виде «черного» ящика (рис. 51).
Рис. 51. Конечный автомат (КА) в виде «черного» ящика
В комбинационном автомате внутренних состояний не указывают.
Входное слово – последовательность входных символов.
Выходное слово – последовательность выходных символов, соответствующих входному слову. В конечном автомате также выделяется последовательность символов внутренних состояний, соответствующих входному слову.
Большой вклад в теорию дискретных (цифровых) автоматов внесли отечественные ученые: М.А. Гаврилов, который опубликовал первую в мире монографию «Теория релейно-контактных схем» (1950 г.), В.М. Глушков, В.Н. Рогинский, П.П. Пархоменко, В.Г. Лазарев, С.И. Баранов, А.Д. Закревский, Э.А. Якубайтис, С.В. Яблонский, В.И. Варшавский и др.
