Общие задачи теории автоматов

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

Рассмотрим основные задачи теории автоматов.

1. Задача синтеза —заключается в том, что необходимо построить некоторый автомат С, реализующий отображение множества слов алфавита X во множество слов над алфавитом Y.

В рамках общей задачи синтеза конечных автоматов возникают, отдельные частные проблемы.

Проблема существования — существует ли автомат данного типа, соответствующий заданным условиям?

Проблема единственности — единственным ли образом можно синтезировать заданный автомат?

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

2. Задача анализа (обратная задача) — заключается в поиске по заданному графу конечного автомата С отображения слов входного алфавита Х во множество слов его выходного алфавита Y.

Для конечных детерминированных автоматов разработано достаточное число алгоритмов их синтеза и анализа.

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

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

3. Задача декомпозиции —заключается в поиске таких эквивалентных преобразований автомата, которые при минимальном числе состояний имеют те же свойства, что и при заданном. То есть необходимо определить, как можно получить заданный автомат С, соединив минимальное число более простых автоматов, может быть, за счет усложнения комбинационных схем. Но при этом поведение автомата характеризуется одинаковыми внешними проявлениями. Так как понятие композиции имеет разное значение, то задачу декомпозиции автоматов можно ставить по-разному.

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

Тождественными автоматами принято считать такие автоматы, которые одинаково ведут себя при различном числе состояний.

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

Композицией автоматов называют операции, используемые для создания новых автоматов из других, исходных.

Автоматы, полученные в результате таких операций, также называют композициейавтоматов.

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

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

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

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

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

Очевидно, конечный автомат является частным случаем алгоритма, в частности алгоритма с конечной памятью, что соответствует конечному числу состояний автомата.

Благодаря исследованиям в области теории автоматов математика пополнилась новым направлением, связанным с понятием сложности некоторой системы.

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

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

Новые научные направления «теория коллективного поведения автоматов» и «поведение автоматов в случайных средах» опираются на тактику поведения обычных конечных автоматов. Изучены условия, характеризующие их способность к адаптации в стационарных и нестационарных средах.

Причем оказалось, что отдельный вид автоматов — автоматы с переменной структурой в нестационарных средах — более приспособлены к функционированию. Автоматы такого типа используют в системах автоматического управления стационарными и нестационарными объектами, когда информация о функционировании объекта известна частично или вообще не известна.

Благодаря широкому развитию вычислительной техники и глобальной информатизации современного общества особую актуальность приобрела проблема машинного интеллекта. Например, исследования в этом направлении английского математика А, М. Тьюринга показали, что автомат может решать любые логические правильно сформулированные задачи, которые может решать человек. Может ли автомат заменить человека?

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

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

[1] Греческое слово.- самодействующий

[2] Первые башенные часы были установлены в 1352 г. на соборе в городе Страсбурге.