ЗАДАЧИ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ

При решении задачи анализа по таблице переходов требуется получить словесное описание алгоритма функционирования КА.

3. Структурный синтез заключается в выборе элементарных автоматов (ЭА) и отыскании такого способа их соединения между собой, который обеспечивает функционирование схемы в соответствии с заданной кодированной таблицей переходов и выходов. Кодированная таблица переходов определяет зависимость внутренних состояний и выходных сигналов КА от значений входных сигналов и внутренних состояний в предыдущий момент времени (такт). Кодирование внутренних состояний осуществляется таким образом, чтобы исключить критические состязания.

Для синтеза КА необходимо иметь функционально полный набор элементов, который должен содержать:

– хотя бы один ЭА с двумя разными состояниями, для которого соблюдается условие полноты системы переходов и выходов (то есть существует хотя бы один входной сигнал, переводящий автомат из состояния в и в каждом состоянии автомат выдаёт выходной сигнал, отличный от сигналов, выдаваемых в других состояниях);

– логические элементы, образующие функционально полную систему для синтеза логических функций.

4. Структурный анализ.

При решении задачи структурного анализа по схеме автомата необходимо получить таблицу переходов и сравнить с исходной таблицей с целью проверки правильности синтеза.