2. Постановка задачи «Теории автоматов»

В основе любой деятельности лежит преобразование и обработка информации. Информация имеет разнообразные представления и в общем преобразование (обработку) информации можно представить (рис.1.2.1) в виде существования:

• входного информационного потока (A);

• некоторого преобразователя информации (Ф);

• выходного информационного потока (B).

Преобразователь Ф формирует по определённым правилам выходной поток В, базируясь на данных потока А, т.е. выполняет преобразование АВ.

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

Для решения этих проблем необходим некоторый универсальный преобразователь ИП АВ, в качестве которого используются цифровые преобразователи информации. Эти преобразователи представляются в виде конечных автоматов (КА) и их место в общем преобразовании показано на рис.1.2.2. Здесь преобразователь информации Ф разбит на три блока:

• Входной преобразователь (АХ), приводящий входной ИП произвольного вида А в цифровой (бинарный) вид;

• Конечный автомат (КА) , выполняющий преобразование по установленным правилам бинарного потока Х в бинарный поток Y, т.е. выполняющий преобразование XY.

• Выходной преобразователь (YB), переводящий результирующий цифровой поток Y в выходной поток В.

КА в виду его цифровой (бинарной) природы обладает возможностями:

• логической обработки информации на основе алгебры логики (булевой алгебры);

• накопления информации об истории процесса;

• представления процесса обработки в виде алгоритмов;

• простотой технической реализации алгоритмов;

• относительной простотой отладки и наладки схемы КА.

Отметим, что, если потоки А и В цифровые с аналогичными параметрами, то входной и выходной преобразователи могут отсутствовать.

Структура самого КА представлена на рис.1.2.3. В КА можно выделить два основных блока:

• ЛС – логическая схема;

• ЭП – элементы памяти.

Основное назначение блока элементов памяти – хранение кода текущего состояния КА.

Блок логической схемы предназначен для:

• приёма входного ИП;

• выработки на основании информации о текущем состоянии КА и входного информационного потока:

  • выходного информационного потока;

  • значения новых состояний КА.

Работа КА синхронизируется во времени серией синхросигналов, которые представляют собой последовательность синхронизирующих импульсов (СИ). При поступлении одного СИ происходит переход в новое состояние КА и вырабатывается одно слово выходного ИП.

Существуют асинхронные КА, но они сложно синтезируемы, неустойчиво работают и не получили широкого распространения.