В [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
Z (t) |
Z (t + 1), l (t) | |
X=0 |
X=1 | |
1 |
4, 1 |
2, 0 |
2 |
4, 1 |
3, 0 |
3 |
1, 0 |
4, 0 |
4 |
2, 0 |
1, 0 |
Разработка контроллера управления робототехнической системы
Курсовая
работа
по
схемотехнике
Тема
Разработка
контроллера управления робототехнической системы
Исходные данные
1. Контроллер управления робототехнической системой (только ...
Разработка системы космической связи военного назначения с коммутируемым спутниковым моноканалом
О серьезности проблемы влияния помех - на приемо-передающие каналы
спутниковых систем связи говорят следующие факты.
. Заметное увеличение числа публикаций и сообщений по данной проблеме.
. Выработка международными и национальными орган ...