1. Абстрактный синтез конечных автоматов. Минимизация и детерминация конечных автоматов. Автоматы Мили и Мура. (та)

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

По конечному автомату часто можно построить автомат с меньшим числом состояний, эквивалентный исходному. Соответствующий процесс называется минимизацией конечного автомата. Вначале выбросим из автомата все состояния, недостижимые из начального. Затем разобьем все состояния КА на классы эквивалентности следующим способом: в первый класс отнесем все конечные состояния, а во второй - все остальные. Назовем  эти  состояния  0-эквивалентными. Теперь построим новое 1-эквивалентное разбиение,  выделив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния. Последовательно строя n+1-эквивалентные состояния по n-эквивалентным, мы будем увеличивать число классов эквивалентности. Прекратим этот процесс тогда, когда n+1-эквивалентное состояние совпадет с n-эквивалентным. Каждый полученный класс эквивалентности и будет состоянием нового  минимизированного КА, эквивалентного исходному.

Детерминация КА. Для любого недетерминированного Конечного Автомата K=<A,Q,B,,> существует эквивалентный ему детерминированный конечный автомат K1=<A,Q,B,1,1> имеющий не более чем 2ⁿ состояний ( n=|Q| , |Q1|=2^|Q| =2ⁿ).

Замечание: Заключительными состояниями детерминированного автомата являются все те состояния, подмножества состояний исходных автоматов, которых содержат заключительные состояния исходного автомата.