вход Вход Регистрация



 

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

Структурная теория автоматов и абстрактная теория автоматов являются двумя различными частями общей теории автоматов. При синтезе реальных автоматов многие вопросы проще и эффективнее решаются на уровне абстрактной теории. К числу таких вопросов относится определение необходимого объема памяти автомата (т.е. числа его состояний), переходов в памяти, а также вопросы, относящиеся к минимизации числа состояний автомата. В то же время имеется ряд вопросов – таких, например, как вопрос о композиции автоматов, - сама постановка которых выводит за рамки абстрактной теории автоматов.

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

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

Сформулируем определение общего способа композиции автоматов.

Пусть (где ) конечное множество автоматов. Произведем объединение этих автоматов в систему совместно работающих автоматов следующим образом.

Введем в рассмотрение некоторое конечное множество узлов, которое назовем внешними входными узлами, и некоторое конечное множество других узлов, которое назовем внешними выходными узлами (полюсами). Эти узлы предполагаются отличными от входных и выходных узлов рассматриваемых автоматов, которые будем называть внутренними (входными и выходными) узлами.

Композиция автоматов состоит в том, что в полученной системе, состоящей из данных автоматов и внешних узлов, производится отождествление некоторых узлов (как внешних, так и внутренних). С точки зрения совместной работы системы автоматов смысл операции отождествления узлов состоит в том, что элементарный сигнал, попадающий на один из узлов, входящих во множество отождествленных между собой узлов, попадает сразу на все узлы этого множества. Для электронных ЦА операции отождествления узлов соответствует соединение этих узлов проводниками.

В результате проведения операции отождествления (соединения) узлов, все узлы, входящие в данную систему (внутренние и внешние), разобьются на попарно непересекающиеся множества отождествленных между собой узлов.

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

Предположим, что в каждый момент дискретного времени структурный выходной сигнал схемы однозначно определяется 1) поступившей к этому времени последовательностью структурных входных сигналов; 2) начальными состояниями входящих в схему автоматов и 3) сделанными при построении схемы отождествлениями узлов. Построенная схема может рассматриваться как некоторый ЦА , а сама схема называться структурной схемой этого автомата.

Полученный описанным способом автомат есть результат композиции исходных автоматов .

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

- в любой момент времени на каждый узел схемы (как внешний, так и внутренний) поступает какой-либо элементарный сигнал;

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

Правильной композицией автоматов называется операция построения схемы автомата, для которой выполняются три условия:

1. Для любого узла схемы должна существовать цепь, состоящая из некоторого множества (м.б. пустого) автоматов Мили, начинающаяся каким-нибудь задающим (внешние входные или внутренние выходные узлы автомата Мура) узлом и кончающаяся узлом (условие передачи элементарных сигналов от задающих узлов на все узлы автомата в каждый момент автоматного времени).

2. Любой узел схемы должен быть отождествлен (соединен) не более чем с одним внешним входным или внутренним выходным узлом.

3. Любая нетривиальная (содержащая не менее одного ЦА) петля в схеме должна содержать в своем составе хотя бы один автомат Мура.

© 2018
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру