Эквивалентным преобразованием называется переход от автомата K к автомату K’ который неотличим от исходного. Постановка задачи минимизации : среди автоматов неотличимых от автомата K найти автомат Ko с наименьшим числом состояний.

Абстрактный синтез автоматов- это представление автомата в отдельных блоков функционирующих как одно целое. Например Микропроцессор можно представить как устройство состоящее из отдельных блоков, таких как: АЛУ, очередь комманд, регистровый файл и т.д. это и есть абстрак. синтез, но если Микропроц. представлять как схему из логических элементов то это уже структурный синтез.(не путать!)

Теорема : Для любого автомата K существует эквивалентный ему минимальный автомат Ko с точностью до изоморфизма , имеющий L состояний , если множество состояний Q разбивается на L классов эквивалентности.

Теорема : ( детерминация КА). Для любого недетерминированного КАвтомата K=< A,Q,B,b,l> существует эквивалентный ему детерминированный К автомат K1=< A,Q,B,b1,l1> имеющий не более чем 2ⁿ состояний ( n=|Q| , |Q1|=2^|Q| =2ⁿ). Замечание: 1). Заключительными состояниями детерминированного автомата являются все те состояния , подмножества состояний исходных автоматов, которых содержат заключительные состояния исходного автомата. 2). Может случиться так , что после перехода от источника к автомату- преобразователю он становится недетерминированным по входному знаку. Эта недетерминированность никак не связана с внутренней структурой автомата.