ЗАКЛЮЧЕНИЕ

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

Материал излагался в такой последовательности и форме, которые, с нашей точки зрения, были удобны для разъяснения основных понятий и методов теории конечных автоматов. Решения двух поставленных задач накапливались при этом постепенно и оказались разбросанными по разным главам. Не излагая нового материала, мы здесь постараемся систематизировать разрозненные факты, относящиеся к названным выше двум основным задачам теории конечных автоматов.

§ 1. Что может «делать» конечный автомат и последовательностная машина

Ответ дается в различных терминах в зависимости от того, является ли автомат (соответственно П-машина) автономным или нет.

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

Более того, какова бы ни была периодическая последовательность состояний конечной длины, всегда может быть построен автономный конечный автомат, который, начиная уже со второго такта, генерирует эту последовательность. Ничего иного, кроме периодического повторения одного и того же состояния или конечной последовательности состояний, автономный автомат «делать» не может.

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

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

Если автомат не автономен, т. е. состояние входа изменяется от такта к такту, то ответ на вопрос, что может «делать» и что не может «делать» конечный автомат, можно дать в разных терминах. Например, ответ можно сформулировать на языке представления событий.

Действительно, неавтономный конечный автомат или последовательностная машина лишь преобразуют входные последовательности символов в последовательности состояний или выходных символов, и сказать, что может и что не может «делать» конечный автомат, значит выяснить, какие преобразования последовательностей возможны в конечном автомате, а какие невозможны. Но так как количество состояний (соответственно выходных символов) конечно, этот вопрос эквивалентен такому вопросу: при каких входных последовательностях возникает каждое из возможных состояний (или каждый из выходных символов).

Этот последний вопрос в терминах, принятых в теории конечных автоматов, формулируется так: какие события могут и какие не могут быть представлены в конечном автомате каждым из возможных состояний (или каждым из выходных символов). Ответ дается теоремами Клини. Этот ответ точный, так как теоремы Клини устанавливают необходимые и достаточные условия представимости событий в автомате, а именно: выделяются особые множества последовательностей входных символов — регулярные множества. Факт появления входной последовательности из такого множества называется соответствующим регулярным событием. Теоремы Клини устанавливают, что в конечном автомате могут быть представлены регулярные события и только они. Таким образом, на языке представления событий ответ на вопрос, что может «делать» конечный автомат, дается однозначно: конечный автомат может представлять только регулярные события.

Ряд важных множеств входных последовательностей, с которыми часто приходится иметь дело на практике, заведомо регулярны. Так, например, заведомо регулярно множество, состоящее из любого конечного числа входных последовательностей конечной длины; множество любых периодических входных последовательностей; множество бесконечных последовательностей, которое содержит заданные конечные последовательности на протяжении нескольких последних тактов, и т. д. В общем случае, если каким-либо произвольным способом задано бесконечное множество входных последовательностей, то остается открытым вопрос о том, регулярно ли это множество. Дело в том, что понятие регулярного множества вводится индуктивно, т. е. устанавливается прием построения любых регулярных множеств. Однако не существует достаточно эффективного способа решения обратной задачи, т. е. установления того, является ли каждое заданное множество регулярным. Хотя теоремы Клини и отвечают на вопрос о том, что может делать конечный автомат, но отвечают они на этот вопрос не эффективно. Сделаны первые попытки построения иных языков, на которых ответ может быть дан эффективно.

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

Если расширить класс динамических систем, которые мы определили терминами «конечный автомат» и «последовательностная машина», включением бесконечной памяти (ее образом может быть, например, бесконечная лента или бесконечное число состояний), то для динамических систем этого более широкого класса (абстрактные системы этого класса называют машинами Тьюринга) ответ на вопрос «что они могут делать?» значительно более прост — они могут реализовать любой наперед заданный алгоритм. При этом само понятие алгоритма трактуется в современной математике как реализация вычисления значений какой-либо рекурсивной функции. Столь однозначный и четкий ответ на вопрос «что может делать машина Тьюринга?» дает возможность положить понятие о машине Тьюринга в основу определения понятия алгоритма: алгоритмом называется любой процесс, который может быть осуществлен на конечном автомате, дополненном бесконечной памятью, т. е. на машине Тьюринга.