Cтраница 2
При решении последнего вопроса, составляющего предмет так называемой структурной теории автоматов, автоматы Мура приходится рассматривать как отдельный класс автоматов, не являющийся собственным подклассом класса всех автоматов Мили. Различие между зтими двумя классами автоматов в структурной теории обусловливается тем, что в автоматах Мили выходной сигнал возникает одновременно с индуцирующим его входным сигналом, а в автоматах Мура - с задержкой на одну единицу автоматного времени. [16]
Обратимся сначала к наиболее прикладному и вместе с тем наиболее раннему направлению в теории конечных автоматов - к так называемой структурной теории автоматов, предметом которой является изучение способов построения сложных автоматов из элементарных автоматов ( см. § § 4 - 6 гл. Результаты, устанавливаемые в этой теории для схем одного типа, в значительной мере удается переносить и на схемы другого типа. [17]
Если в абстрактной теории автоматов везде под автоматом подразумевается абстрактный автомат, заданный либо графоидом, либо матрицей соединений, то в структурной теории автоматов, говоря об автомате, имеют в виду структурную схему, состоящую из элементов некоторого стандартного комплекса, в который входят набор элементарных автоматов и функционально полный набор логических элементов. Поэтому на структурном уровне изучаются методы перехода от гра-фоида или матрицы соединений автомата к структурной схеме автомата, приемы построения схем сложных автоматов из схем элементарных автоматов и логических элементов, рассматриваются способы кодирования состояний, входных и выходных сигналов автомата, различные варианты которых определяют, в конечном счете, сложность структурной схемы автомата при неизменном законе его функционирования. [18]
Общая теория автоматов при сделанных выше допущениях естественно разбивается на две большие части, которым мы присвоим названия абстрактной теории автоматов и структурной теории автоматов. Различие между ними заключается в том, что в абстрактной теории мы отвлекаемся от структуры как самого автомата, так и его входных и выходных сигналов. [19]
В абстрактной теории автоматов важное значение имеют задачи анализа и синтеза автоматов, а на структурном уровне на первый план ставится проблема синтеза автоматов, которой посвящено большинство работ, связанных со структурной теорией автоматов. [20]
По сравнению с абстрактной теорией автоматов в структурной теории автоматов делаются дальнейшие шаги в направлении учета большего числа свойств реально существующих дискретных автоматов. Главная отличительная особенность структурной теории автоматов состоит в том, что, в отличие от абстрактной теории, она учитывает структуру входных и выходных сигналов автомата, а также его внутреннюю структуру на уровне так называемых структурных схем. Основной задачей структурной теории является изучение композиции автоматов, то есть методов построения сложных автоматов из автоматов, являющихся относительно более простыми. [21]
Значительные возможности упрощения схем обратных связей - и определяемых ниже схем выходов - заключены в выборе рационального способа кодирования состояний синтезируемого автомата. В выборе рационального, с указанной точки зрения, кодирования состояний автомата состоит так называемая проблема кодирования, являющаяся одной из трудных проблем структурной теории автоматов. В настоящее время решение этой проблемы в каждом конкретном случае сопряжено, как правило, с перебором большого числа различных вариантов кодирования состояний. [22]
Следует подчеркнуть, что структурная теория автоматов не ставит своей задачей отразить все свойства реально существующих автоматов. В ней, например, совершенно не учитываются переходные процессы в автоматах, вопросы надежности работы автома тов, физические свойства сигналов и многое другое. В этом смысле структурная теория автоматов также остается в значительной мере абстрактной теорией, хотя она и отличается значительно меньшей степенью абстракции, чем собственно абстрактная теория автоматов. [23]
Особенно важно отметить введение уровня абстракции, промежуточного между тем уровнем, который имеет место при применении булевой алгебры, и тем, с которым имеют дело при использовании заимствованных из радиотехники и импульсной техники методов расчета схем. Именно этот уровень, будучи тесно связанным с уровнем абстракции, принятым в абстрактной и структурной теории автоматов, позволяет осуществить тесную связь этих двух разделов теории с задачами, возникающими при синтезе реальных схем цифровых автоматов. Благодаря введению такого уровня абстракции оказывается возможным учесть особенности синтеза схем различных типов ( потенциальных, импульсных и смешанных) безотносительно к конкретной природе элементов, из которых построены эти схемы. [24]
Вторая глава посвящена изложению проблем, возникающих на этапе абстрактного синтеза автоматов. Эта глава почти полностью построена на основании собственных результатов автора), изложенных в упомянутых выше его работах, а также некоторых новых результатов, излагаемых впервые. То же самое относится к первым двум, а также к последнему, параграфам третьей главы, которая посвящена структурной теории автоматов. В остальных параграфах этой главы содержится теоретический материал, подготавливающий читателя к усвоению проблематики и методов комбинационного синтеза. Наряду с некоторыми новыми вопросами здесь изложены также основы булевой алгебры, включая теорему о функциональной полноте; § 7 гл. [25]
Рассмотрение этих вопросов на уровне структурной теории повлекло бы за собой загромождение хода рассуждения несущественными ( и к тому же подчас затемняющими суть дела) подробностями. Более того, трудности эквивалентных преобразований структурных схем автоматов с памятью делают практически невозможным ( по крайней мере в настоящее время) решение на уровне структурной теории такой задачи, как задача минимизации числа состояний автомата. В то же самое время имеется ряд вопросов - таких, например, как вопрос о композиции автоматов, - сама постановка которых выводит за рамки абстрактной теории автоматов. Таким образом, абстрактная теория автоматов и структурная теория автоматов взаимно дополняют друг друга и имеют собственные естественные области приложения. [26]
В отличие от абстрактной теории автоматов, в структурной теории как входные, так и выходные каналы рассматриваемых автоматов считаются состоящими, вообще говоря, из нескольких элементарных входных и соответственно элементарных выходных каналов. По всем элементарным каналам могут передаваться лишь так называемые элементарные сигналы. Набор всех возможных для данного автомата элементарных сигналов называется структурным алфавитом этого автомата. Структурный алфавит должен быть непременно конечным. Что касается природы букв ( элементарных сигналов), составляющих структурный алфавит, то в структурной теории автоматов ею обычно не интересуются. [27]