Синхронизирующие последовательности

В [10] приведены методы синтеза синхронизирующих последовательностей (СП) по таблице переходов-выходов автомата и по функциональной схеме ДУ. В этом разделе определена верхняя граница длины СП, которая сравнивается с известными оценками [16], анализируется сложность построения СП и условия существования в автомате однородных синхронизирующих последовательностей.

Определение 3.6 Входная последовательность XS автомата, которая устанавливает его в определенное конечное состояние независимо от состояния выхода и начального состояния, называется синхронизирующей последовательностью.

Если автомат A (X, Y, Z, d, l) задан таблицей переходов-выходов, то из определения 3.6 следует, что автомат имеет синхронизирующую последовательность тогда и только тогда, когда существует входная последовательность Xs такая, что d (Zi, XS) =Z0; Zi Z, Z0 Z. Множество переходов d (Zi, XS) =Z0; для Zi Z, автомата определяет отображение множества его состояний Z в некоторое определенное состояние Z0 при подаче на автомат входной последовательности XS, то есть Z Z0.

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

Так как синхронизирующая последовательность не связана с анализом выходной последовательности автомата, то функции выходов автомата не рассматриваются при построении синхронизирующего дерева. Вершины синхронизирующего дерева отмечаются s - множествами, коорые являются Xi-преемниками ( Xi X) состояний, входящих в s - множества предшествующих вершин. Вершина ранга j - синхронизирующего дерева является висячей, если:

а) вершина отмечается группой s - множеств, которая соответствует группе s - множеств какой-либо вершины ранга меньше j;

б) вершина j-го ранга отмечена одним простым s - множеством.

Путь в синхронизирующем дереве, корнем которого является начальное s - множество, включающее все состояния автомата, и завершающийся висячей вершиной, отмеченной единственным простым s - множеством, соответствует синхронизирующей последовательности автомата.

В качестве иллюстрации предлагается рассмотреть автомат А-2, заданный таблицей переходов-выходов (таблица 3.2). Синхронизирующее дерево (рисунок 3.2) является синхронизирующей последовательностью, которая устанавливает А-2 в состояние 4 независимо от начального состояния.

Таблица 3.2 - Автомат А-2

Прочитайте еще и эти статьи:

Информационные устройства и системы управления автосигнализацией
Современный термин “Мехатроника” (”Mechatronics”), согласно японским источникам, был введен фирмой Yaskawa Electric в 1969 году и зарегистрирован как торговая марка в 1972 году. Это название получено комбинацией слов “МЕХАника” и “элекТРО ...

Техническая реализация САУ давлением пара за котлом
Одним из решающих факторов повышения производительности общественного труда является автоматизация производства. В связи с этим за последние годы резко возрастает объем работ по автоматизации технологических процессов во всех отраслях народного ...