Cтраница 2
Возможность интерпретации всякого автомата Мура как автомата Мили в абстрактной теории автоматов не означает, разумеется, наличия обратной возможности. [16]
В упомянутых работах Клини и Мура было положено начало возникновению абстрактной теории автоматов, хотя сами полученные в них результаты были еще достаточно далеки от возможности реального их использования на этапе абстрактного синтеза автоматов, где в это время продолжали господствовать эмпирические методы. В работе Неймана было положено начало созданию общей математической теории для одной из самых интересных областей надежностного синтеза, именно - теории синтеза надежных схем из ненадежных элементов. [17]
В связи со всем сказанным становится понятной необходимость решения следующих важнейших задач абстрактной теории автоматов. Прежде всего нужно научиться решать задачу нахождения по заданному абстрактному автомату А соответствующего ему канонического множества событий; эту задачу мы будем называть канонической задачей анализа абстрактного автомата. Далее необходимо научиться решать обратную задачу: по заданному автоматному множеству событий М находить абстрактный автомат, каноническое множество событий которого совпадает с М; эту задачу мы будем называть канонической задачей синтеза абстрактного автомата. [18]
Общая теория автоматов при сделанных выше допущениях естественно разбивается на две большие части, которым мы присвоим названия абстрактной теории автоматов и структурной теории автоматов. Различие между ними заключается в том, что в абстрактной теории мы отвлекаемся от структуры как самого автомата, так и его входных и выходных сигналов. [19]
В структурной теории автоматов сохраняется абстракция дискретного автоматного времени, однако при построении этой теории оказывается более удобным несколько изменить порядок отсчета временных интервалов, принятый в абстрактной теории. В абстрактной теории автоматов было удобнее ( для того, чтобы не создавать двух различных теорий для автоматов первого и второго рода) относить входные и выходные сигналы к моменту перехода автомата из одного состояния в другое. В структурной теории мы будем придерживаться более естественного способа отсчета времени, считая моменты перехода автомата из одного состояния в другое границами интервалов, относящихся к одному и тому же значению автоматного времени. [20]
В абстрактной теории автоматов элементам входного и выходного алфавита обычно не приписывается никакого смысла и они рассматриваются просто как элементы некоторых абстрактных множеств. При использовании понятия автомата для описания алгоритмических процессов необходимо интерпретировать его входные и выходные сигналы соответственно как сигналы о перерабатываемой информации и выполняемых алгоритмом элементарных действиях. [21]
Изоморфные между собой абстрактные автоматы отличаются друг от друга лишь обозначениями входных и выходных сигналов и состояний. Поэтому, в абстрактной теории автоматов, не занимающейся проблемами кодирования состояний, а также входных и выходных сигналов, изоморфные автоматы считаются одинаковыми и будут заменяться один другим без каких-либо дальнейших пояснений. Операция перехода от данного абстрактного автомата к изоморфному ему автомату состоит просто в переобозначении элементов входного алфавита, выходного алфавита и множества состояний автомата. [22]
Конструктивное доказательство этих теорем как раз и приводит к алгоритмам абстрактного анализа и синтеза автоматов. Теорема 5.3 является фундаментальной теоремой абстрактной теории автоматов, поскольку из нее следует, что язык регулярных выражений оказывается достаточным для описания отображений, индуцируемых произвольными конечными автоматами. [23]
Описанный временной сдвиг дает возможность рассматривать автоматы Мура как частный случай автоматов Мили всякий раз, когда нас интересует не истинное время появления того или иного выходного сигнала, а лишь порядок следования выходных сигналов во времени. Именно с таким положением мы сталкиваемся в абстрактной теории автоматов, интересующейся лишь отображениями, индуцируемыми автоматами и переходами в их памяти, а не способом составления данного автомата из имеющихся в нашем распоряжении элементарных автоматов. [24]
В рамках абстрактной теории автоматов содержание понятий автомат и машина исчерпывается, по существу, стандартным описанием преобразования информации, которое осуществляется автоматом. В нашем изложении этой концепции соответствуют понятия ограниченно-детерминированного оператора) ( заданного своими каноническими уравнениями) или элементарного автомата. Типичными задачами абстрактной теории автоматов являются задачи с экспериментами над автоматами ( ср. IV), исследование которых продолжено в работах Гинзбурга. [25]
Следует подчеркнуть, что структурная теория автоматов не ставит своей задачей отразить все свойства реально существующих автоматов. В ней, например, совершенно не учитываются переходные процессы в автоматах, вопросы надежности работы автома тов, физические свойства сигналов и многое другое. В этом смысле структурная теория автоматов также остается в значительной мере абстрактной теорией, хотя она и отличается значительно меньшей степенью абстракции, чем собственно абстрактная теория автоматов. [26]
Рассмотрение этих вопросов на уровне структурной теории повлекло бы за собой загромождение хода рассуждения несущественными ( и к тому же подчас затемняющими суть дела) подробностями. Более того, трудности эквивалентных преобразований структурных схем автоматов с памятью делают практически невозможным ( по крайней мере в настоящее время) решение на уровне структурной теории такой задачи, как задача минимизации числа состояний автомата. В то же самое время имеется ряд вопросов - таких, например, как вопрос о композиции автоматов, - сама постановка которых выводит за рамки абстрактной теории автоматов. Таким образом, абстрактная теория автоматов и структурная теория автоматов взаимно дополняют друг друга и имеют собственные естественные области приложения. [27]
Рассмотрение этих вопросов на уровне структурной теории повлекло бы за собой загромождение хода рассуждения несущественными ( и к тому же подчас затемняющими суть дела) подробностями. Более того, трудности эквивалентных преобразований структурных схем автоматов с памятью делают практически невозможным ( по крайней мере в настоящее время) решение на уровне структурной теории такой задачи, как задача минимизации числа состояний автомата. В то же самое время имеется ряд вопросов - таких, например, как вопрос о композиции автоматов, - сама постановка которых выводит за рамки абстрактной теории автоматов. Таким образом, абстрактная теория автоматов и структурная теория автоматов взаимно дополняют друг друга и имеют собственные естественные области приложения. [28]
Вообще следует заметить, что во многих частях теоретической кибернетики наблюдается своеобразный параллелизм лапласовского и нелапласовского подходов. Под последним понимается такая трактовка причинной детерминации, которая допускает ее неоднозначность, предста-вимую, в частности, в вероятностно-статистических терминах. При этом нелапласовская трактовка причинности нередко оказывается обобщением лапласовской. Такая ситуация наблюдается, например, в теории автоматов. Вероятностный автомат с содержательной точки зрешш можно считать обобщением понятия детерминированного автомата, в силу чего хорошо известная проблематика абстрактной теории автоматов естественным образом переносится и в теорию вероятностных автоматов ( хотя в последней, конечно, и проблематика, и особенно методология исследований претерпевают существенные изменения) ( Б. А. Трахтенброт, Я. М. Барздинь, 1970, стр. Другим примером может служить теория формальных нервных сетей, развиваемая в духе Мак-Каллока на основе диаграмм Венна. [29]