Граф - переход - автомат
Cтраница 1
 |
Графы переходов управляющих автоматов, построенных по модели Мили ( а и модели Мура ( б. [1] |
Граф переходов автомата строят следующим образом. [2]
Граф переходов автомата Gn содержит в себе информацию о значениях выходных функций на всех переходах до размещения внутренних состояний. Эти значения определяются распределением вектора Y на дугах графа переходов. Каждую выходную функцию fj до размещения внутренних состояний представим в виде модели tyf. S ( U, jj), где 5-носитель модели, совпадающий с множеством вершин графа переходов автомата; U-множество дуг графа переходов; у - распределение значений у - й компоненты вектора Y по дугам графа переходов. [3]
Представим себе граф переходов автомата G и допустим, что автомат А может перемещаться по вершинам этого графа. Выбор конкретной функции выходов j, автомата G соответствует отметке вершин графа переходов автомата G символами алфавита X. В начальный момент времени автомат А находится в начальном состоянии я0, будучи помещен в вершину, соответствующую начальному состоянию g0 автомата G. А воспринимает отметку этого состояния ( 1 ( g0) - х, переходит в состояние aQx и выдает на выходе сигнал Л ( а0, х) у. Далее все повторяется аналогичным образом. [4]
Рассмотрим движение автомата А по вершинам графа переходов автомата G без циклов. [5]
Таким образом, это преобразование меняет линейные участки графа переходов автомата А. [6]
Задача параллельной декомпозиции автомата, как правило, сводится к разложению графа переходов исходного автомата в частичное декартово произведение более простых по числу вершин графов переходов функционально несвязных друг с другом подавтоматов. [7]
Задача соседнего кодирования внутренних состояний автомата в многозначном структурном алфавите сводится к вложению графа переходов автомата в ( К, и) - куб, где К - мощность используемого структурного алфавита; и - число кодирующих разрядов. При этом переходы из одного состояния в другое осуществляются только по ребрам ( К, и) - куба и коды соответствующих его вершин сопоставляются с вершинами графа переходов. Знание структуры запрещенных фигур вложения графа в ( К, и) - куб позволяет осуществлять соседнее кодирование внутренних состояний в заданном структурном алфавите преобразованием графа переходов автомата к ЛГ-кубируемому виду путем введения минимального числа дополнительных ( неустойчивых) состояний. Для этого с помощью покрытия семантических таблиц определяется множество ребер исходного графа, введение дополнительных состояний на которые переводит его в класс графов, вложимых в ( К, ) - куб. [8]
На вход системы автоматизации кроме формализованного описания алгоритма могут быть поданы задания на проектирование в виде системы логических функций графа переходов автомата, граф-схемы алгоритма. [9]
Синтез конечного автомата по лингвистическому описанию алгоритма функционирования на языке УПРАВЛЕНИЕ осуществляется в два этапа: получение помеченного описания и непосредственно построение графа переходов автомата. Первый этап заключается во введении в описание системных меток. [10]
Очевидно, что если внутренние состояния Sa и Sp зависят от некоторой входной переменной, то при удалении из входного вектора автомата компоненты, приписанной данной переменной, для сохранения детерминированности получаемого в результате графа переходов автомата состояния Sa и Sp необходимо объединить. [11]
Процедура построения УА заключается в выполнении следующих шагов: 1) осуществляют разметку ГСА для определения набора состояний автомата; 2) находят множество путей на ГСА для определения переходов автомата; 3) строят граф переходов автомата и его структурную таблицу; 4) осуществляют кодирование состояний автомата двоичными наборами с учетом типов используемых триггеров; 5) производят синтез и минимизацию комбинационной схемы автомата в выбранном базисе логических элементов; 6) составляют структурную схему УА. [12]
Все переходы графа переходов автомата отражены в каждом из путей. [13]
Представим себе граф переходов автомата G и допустим, что автомат А может перемещаться по вершинам этого графа. Выбор конкретной функции выходов j, автомата G соответствует отметке вершин графа переходов автомата G символами алфавита X. В начальный момент времени автомат А находится в начальном состоянии я0, будучи помещен в вершину, соответствующую начальному состоянию g0 автомата G. А воспринимает отметку этого состояния ( 1 ( g0) - х, переходит в состояние aQx и выдает на выходе сигнал Л ( а0, х) у. Далее все повторяется аналогичным образом. [14]
Возможна и другая процедура проставления системных меток, в частности, можно помечать различными метками все выполняемые инструкции описания. Однако такая процедура порождает существенно большее количество меток, что нецелесообразно, так как количество системных меток в описании в общем случае равно размерности графа переходов автомата. [15]
Страницы: 1 2