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

В [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

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

Создание низкоразмерной среды в арсениде галлия для устройств микро- и наноэлектроники
В настоящее время основным материалом функциональной электроники является ареснид галлия, как самый универсальный по своим электрофизическим свойствам из всех полупроводниковых материалов типа. Физико-химические свойства пористых полупро ...

Сотовые сети стандарта СDMA
Как известно, наиболее прогрессивная часть человечества ныне стоит на пороге вступления в эру глобального информационного общества и соответствующего коренного улучшения телекоммуникационного обслуживания населения. И достигнуто э ...