АВТОМАТОВ СПОСОБЫ ЗАДАНИЯ

— способы описания структуры или алгоритма функционирования автоматов. В зависимости от степени детализации и целей исследования автомат может быть задан: во-первых, автоматным отображением, т. е. соответствием между последовательностями входных и выходных сигналов (см. Оператор автоматный), или алгоритмом вычисления ф-ций переходов и выходов (алгоритм, описание); во-вторых, сетью известных автоматов (структурное описание). Часто используется смешанное описание, в котором автомат описывается как сеть логическая или автоматов композиция, составленная из автоматов, которые, в свою очередь, могут иметь алгоритмическое или структурное описание.

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

Структура конечного автомата задается сетью из элементарных автоматов. Чаще всего структура представляет собой композицию регистра состояний и комбинационной схемы. Соответствие между последовательностями входных и выходных сигналов иногда удобно задавать явно, выписывая для каждой входной последовательности, во что она перерабатывается. Этот способ применяют, когда автоматное отображение является частичным, с конечной областью определения. Бесконечное автоматное отображение удобно задавать с помощью конечной системы регулярных выражений. При этом каждой букве у выходного

алфавита ставится в соответствие мн-во всех тех входных последовательностей — слов, которые переводятся данным автоматным отображением в выходные слова, оканчивающиеся буквой у. Таблица переходов автомата явно задает ф-цию переходов. Если автомат имеет состояний и входных букв, то таблица переходов содержит соответственно столбцов и строк, а на пересечении столбца и строки — значение ф-ции переходов для состояния и входного сигнала. Таблица выходов автомата явно задает ф-ции выходов. В ней, как и в табл. переходов, имеется столбцов и строк, а на пересечении столбца и строки — значение ф-ции переходов для состояния и входного сигнала. Граф переходов и выходов представляет собой графическое задание ф-ции переходов и выходов (см. Абстрактного автомата граф). В нем есть вершин, соответствующих состояниям; состояния соединены направленным к ребром, помеченным буквой X (входной сигнал), если значение ф-ции перехода для пары равно . Для Мини автомата ребра, кроме входных сигналов, помечаются еще и соответствующим значением ф-ции выходов. Для Мура автомата значениями ф-ции отметок помечают вершины графа. Автомата матрица переходов представляет собой квадратную табл. . Каждому состоянию автомата соответствует столбец и строка. На пересечении строки и столбца в таблице выписывается мн-во таких входных сигналов X, для которых значение ф-ции переходов для пары равно Программа автомата представляет собой последовательность отмеченных операторов — команд. Метки команд соответствуют состояниям автомата. Каждая команда состоит из последовательности строк. Каждая строка имеет вид: где некоторое условие, заданное на мн-ве входных сигналов, F (У) — дизъюнкция выходных сигналов, N — метка команды. Каждая строка означает: если для входных сигналов автомата выполняется условие Е (X), то следует выдать выходные сигналы, входящие в F (У), и перейти к команде с меткой N данной программы. Во многих случаях задание автомата программой более экономно, чем другие способы задания. Особенно удобно применять его для задания не полностью определенных и недетерминированных автоматов. При синтезе управляющего автомата, который в дальнейшем служит в качестве блока ЦВМ, программу его работы часто наз. микропрограммой. Структура автомата задается явным перечислением всех ее компонент и связей между компонентами.

Автомат может иметь алгоритмическое и структурное описания. Соответствие между ними задается табл. кодирования состояний автомата, входных и выходных сигналов, участвующих в алгоритм, описании, и, соответственно, состояниями, а также входными и выходными сигналами компонент, участвующих в структурном описании. Если автомат задают в виде регистра состояний и комбинационной схемы, то эту композицию лучше всего задавать в виде перечисления элементов — компонент регистра, и системы ф-ций возбуждений, управляющих переключением состояний этих элементов. Бесконечные автоматы чаще всего задаются в виде композиции некоторого конечного автомата и бесконечного автомата с регулярным законом порождения состояний и выходных сигналов. См. также Автоматов декомпозиция, Автоматов теория, Язык анкетный для задания автоматов, Язык логический для задания автоматов, Язык описания устройств ЦВМ.

Лит.: Глушков В. М. Введение в кибернетику. К., 1964 [библиогр. с. 319—322]. Ю. В. Капитонова.