Тема 11. Элементы теории автоматов

План:

1. Понятие автомата, принцип работы автомата

2. Способы задания конечных автоматов

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

Цель. Формирование простейших представлений о конечных автоматах  и двояким их токованием: как о механическом устройстве и как о математическом понятии – черном ящике.

Теоретические сведения

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

1. Понятие автомата, принцип работы автомата

Понятие автомат[1] рассматривается в двух аспектах:

1. Автомат – устройство, выполняющее некоторые функции без непосредственно участия человека.  Автомат это реальное устройство, понятное, почему и как оно работает, хотя бы для тех людей, которые его сконструировали  и изготовили. Автомобиль, трактор, самолет, светофор, телевизор, телефон  – все это автоматы.  В этом аспекте ЭВМ следует понимать как автомат, который работает по программе, составленной человеком.

2. Автомат – математическое понятие, обозначающее математическую модель реальных таежнических устройств. Автомат это абстрактное устройство, не понятное почему и как оно работает и, вообще, почему оно  может работать. В этом аспекте автомат есть “черный ящик”, который теоретически способен проводить некоторые действия. С точки зрения математики, абсолютно не важно что, как и почему производит те или иные действия.

Любой автомат должен иметь некоторое количество входов, некоторое количество выходов и некоторое количество внутренних состояний

Алгебраическая теория автоматов является разделом теорети­ческой кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения.

Общая теория автоматов содержит различные подразделы. В за­висимости от предмета изучения она делится на абстрактную тео­рию автоматов и структурную теорию автоматов.

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

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

1.1. Определение конечных автоматов

Автомат – абстрактная модель устройства, функционирую­щего в дискретном времени, которая перерабатывает конечную последова­тельность входных сигналов (стимулов) и превращает их в конечную после­довательность выходных сигналов (реакций).

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

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

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

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

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

Алгоритм – понятное и точное фор­мальное предписание исполнителю, направленное на решение конкретной задачи или на достижения конкретной цели.

Считается, что первым программным устройством, созданным чело­веком, были часы. Часовые механизмы с помощью пружины, приводя­щей в действие шестеренки и кулачковые механизмы, зубчатые колеса и рычаги, осуществляют ряд определенных действий. Примером такого ча­сового механизма могут быть знаменитые часы на Центральном театре кукол в Москве, где он приводит в действие двенадцать сказочных геро­ев, расположенных на циферблате[2].

Сейчас все чаще употребляется термин “интеллектуальный робот“, создано целое научное направление – “искусственный интеллект“.

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

1. Немецкий философ и алхимик Альберт Великий с 1216 по 1246 г., создавал “железного” слугу – ав­томат, который выполнял в доме обязанности привратника.

2. Астроном Иоганна Региамонтана (1436-1476) создал механического орла, который приветствовал наклоном головы и движением крыльев въезд в Нюрнберг императора священной Римской империи Максимилиана П.

3. Механик Жак де Вакансон (1709-1782) – автор первого в мире автоматического ткацкого станка. ОН создал образ механической утки, точной копии своего живого двойника – плавала, чистила перья, глота­ла с ладони зерна. Его механический флейтист, испол­нявший одиннадцать музыкальных пьес, поражал людей, живших в те далекие годы.

4. Русский изобретатель 19в. А. М.Гамулецкого создал целый механический кабинет, в котором было множе­ство сконструированных им автоматов. Здесь в том числе  была и говорящая голова чародея и  амур, играющий на арфе, которые поражали воображение современ­ников.

5. Первый примитивный арифмометр сконструировал в 1641 г. Блез Паскаль. Толчком для открытия были мучения его отца – налогового, инспектора, который днями и ночами работал с большими вычислени­ями. Изобретя арифмометр, восемнадцати летний сын избавил отца от сложных вычислений, а миру подарил первый калькулятор, производя­щий сложение и вычитание чисел.

6. Первый шахматный автомат был построен в 1890 г. испанским инже­нером Торресом Кеведо. Такой автомат мог разыграть лишь ладейный эндшпиль (король и ладья против короля).

7. Первую вычислительную машину с автоматическим управлением со­здал Чарльз Баббедж в 1822г,  Он спроектировал арифмометр, ко­торый имел запоминающие и арифметические устройства. Это устройства стали прототипами  аналогичных устройств современным ЭВМ

1.2.Виды автоматов.

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

Любой автомат имеет собственные базовые множества, которые включают в себя: алфавит входа, алфавит выхода, множество состоя­ний автомата

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

В работе конечных цифровых автоматов важным понятием является время.

Автоматы можно классифицировать по различным признакам.

1. По виду деятельности – автоматы делятся на: инфор­мационные, управляющие и вычислительные.

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

К управляющим автоматам принято относить устройства для уп­равления некоторым процессом, в том числе конкретно: лифтом, конвейером, стан­ком, шлагбаумом.

К вычислительным автоматам относятся  микрокалькуляторы, процессоры в ЭВМ и иные устройства, выполняющие вычисления.

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

2. Конечные автоматы – с точки зрения информатики это такие автоматы, которые представляют собой дискретные пре­образователи информации. К ним относятся преобразователи, в которых содержится конечное мно­жество входных и конечное выходных сигналов, а также конечное множество внут­ренних состояний

3. Цифровые автоматы - автоматы, которые преобразует цифровую информацию. В таком автомате входные сигналы задаются в виде конечного множества мгновенных символов: их длительность на­столько мала, что ею можно пренебречь. За фиксированное время  происходит преобразование входных символов, а на выходе про­исходит скачкообразный переход из одного состояния, в другое состояние.

4. Абстрактные автоматы – отображающие  множество слов входного алфавита Х во множество слов выходного алфави­та Y.

Абстрактный автомат есть:

~       Математическая модель,

~       Алго­ритм действия некоторого преобразования кодовых последователь­ностей,

~       Закон преобразования входного алфавита в выходной.

5. Синхронные и асинхронные автоматы. В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, авто­маты делятся на синхронные и асинхронные автоматы

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

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

6. Автоматы делятся на конечные и бесконечные автоматы. Если в основании классификации лежит объем памяти, то раз­личие заключается в том, имеет ли автомат конечное или беско­нечное число внутренних состояний.

Под бесконечным автоматом обычно понимают определенную математическую идеализацию представлений об автомате, имею­щую бесконечное число состояний. Память такого автомата по­тенциально может неограниченно возрастать. Например, извест­ные абстрактные автоматы Поста и Тьюринга являются бесконеч­ными автоматами, но сама ЭВМ или ее отдельные части – конечными автоматами.

7. Автоматы делятся на детерминированные и вероятностные автоматы. Если в основании классификации лежит механизм случайного выбора, то различают детерминированные и вероятностные (сто­хастические) автоматы.

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

В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором.

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

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

Математи­ческая модель цифрового автомата с одним входом задается пятью объектами:

X- конечное множество входных символов, входной алфавит:

Х= {x₁|(t), x₂(t), …, x_n(t)}; множество слов над Х- X*;

Y~ конечное множество выходных символов, выходной алфа­вит:

У={y₁|(t), y₂(t), …, y_n(t)};

Q ~ конечное множество состояний автомата:

Q= { q₀|(t ),q₁|(t), q₂(t), …, q_n(t), q₀ - начальное состояние;

δ(q, х) - функция перехода автомата из одного состояния в другое: (Q х X) ®Q;

λ(q, х) ~ функция выхода автомата: (Q x Х) ® Y.

Таким образом, конечный автомат Z= (X, Q, У, δ, λ.) определя­ется рекуррентными соотношениями

q(0) = q₀,           q(t + I) = δ (g(t), х(t)),           y(t) = λ (g(t), х(t)),

t- дискретизированный момент времен или  это есть образ мо­нотонной функции t:. Т ® N, причем Т – обычное непрерывное вре­мя, N – множество натуральных чисел.

Все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При этом t(Г₀) – показывает число изменений, произошедших до мо­мента времени Г₀.

Примером дискретизации служит обычный ки­нематограф: время разбито на интервалы длительностью 1/24с. Человеческий глаз воспринимает следование дискретных кадров как непрерывное движение.

9. Синхрон­ные автоматы делятся на автоматы Мили и автоматы Мура. В зависимости от способа организации функции выхода синхрон­ные автоматы делятся на автоматы Мили (автоматы I рода) и автоматы Мура(автоматы II рода).

В автоматах Мили -  выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент времени (t-1). Мате­матической моделью таких автоматов служит система уравнений:

q(t) = δ (g(t-1), х(t))  и  y(t) = λ (g(t-1), х(t)),

В автоматах Мура выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени t.Математической моделью таких автоматов является система:

q(t) = δ (g(t-1), х(t))  и   y(t) = λ (g(t)),

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

10. Комбинационные автоматы – есть автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущи­ми входными символами, т.е. в этом автомате все состояния эк­вивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неиз­менна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние.

11 Логические авто­маты – есть автоматы у которых входной алфавит состоит из 2^т двоичных набо­ров длины т, а выходной – из 2ⁿдвоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.

1.3. Представление событий в автомате.

Обозначим через X* мно­жество входных слов автомата Z, составленное из множества букв входного алфавита X.

Множества слов входного алфавита называ­ют также событием или языком.

Для некоторого автомата Z определим функции перехода δ_z и выхода λ_z индуктивно:

~     функция перехода δ(q_i; x_j) задается автоматной таблицей Z, т.е. известна функция перехода при входных буквах;

~     для любого слова α ÎX* и любой буквы x_j Î X справедливо равенство:

, где:

q_i ~ состояний автомата:

δ(q_i, х) - функция перехода автомата из одного состояния в другое

λ(q, х) ~ функция выхода автомата:

α –слово, x_j- буквы (символы) множества X.

Фактически это значит, что, опираясь на значения функции перехода при входных буквах, мы определяем ее значения при входных словах, состоящих из большего количества букв. После­дняя формула означает, что перед нажатием последней буквы x_j автомат после ввода слова α перешел во внутреннее состояние q = 8(q_i, α).

Если α = Λ (пустое слово), то на пустое слово автомат не должен реагировать: это задает начальное условие δ(q_i Λ) = δ(q_i )

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

Событие EÍ X* представимо в автомате Z= (X, Q, У, δ,, λ.) тогда и только тогда, когда:

,  такое, что определено δ(q_i, х)

На графе автомата события изображаются в виде подмножества всех путей, исходящих из вершины q_t.

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

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

Пустое слово аналогично 1: для любого α справедливо αΛ=Λα = α.

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

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

2. Способы задания конечных автоматов

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

Существуют три способа задания конечных автоматов:

~       Табличный (матрицы переходов и выходов);

~       Графический (с помощью графов);

~       Аналитический (с помощью формул).

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

Табличный способ. Составляется таблица состояния автомата для функции перехода – δ  и функции выхода. При этом:

~     столбцы таблицы соответствуют элементам входного алфавита X,

~     строки таблицы соответствуют состояни­ям (элементы конечного множества Q).

Пересечению i-и строки и j-го столбца соответствует  клетка (i, j), которая является аргументом функций 8 и λ автомата в момент, когда он находится в состоя­нии q_i на его входе – слово x_j, а в самой соответствующей клетке запишем значения функций 8 и λ. Таким образом, вся таблица соответствует множеству Q х X.

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

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

В матрице переходов на пересечении строки x_k и столбца q_r помещается значение функции  перехода δ(q_i, х) и функции выводов λ(q, х). В ряде случаев обе таблицы объединяются в одну таблицу.

Задание 11.1. Конечный автомат имеет алфавиты:

X={a,b} – множество входных символов,  Y={m,n,p} множество выходных символов,

Матрица перехода
δ(qi, х)	q
	1	2	3
a	3	3	1
b	2	3	3

Q={1,2.3} множество состояний.  Задать автомат таблицами (матрицами). По таблицам составить систему команд автомата.

Матрица вывода
λ(q, х)	q
	1	2	3
a	n	m	n
b	p	p	p

Решение. В виду того, что не указаны конкретные функции, расставим значения произвольно, причем:

~   для  матрицы переходов значения берутся  из множества Q={1,2.3}

~   для матрицы выводов значения берутся из множества Y={a,b,c}

Объединенная  таблица
δ(qi, х) и  λ(q, х)	q
	1	2	3
a	3, n	3, m	1, n
b	2, p	3, p	3, p

Объединим обе получившиеся таблицы  в одну общую таблицу:

Выпишем команды преобразования, осуществляемые рассматриваемым автоматом:

1). 1,a ® 3,n         2). 1,b®2,p          3). 2,a ®3,m      4). 2,b®3,p      5). 3,a®1,n     6). 3,b®3,p

Комментарии.

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

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

Графический способ.

Автомат задается с помощью графа, схемы, графика и др. Задание с помощью ориентированного гра­фа – более удобная и компактная форма описания автомата.

Граф автомата содержит

~       Вершины, соответствующие состоянию q_iÎQ,

~       Дуги, соединяющие вершины – переходы автомата из одного состояния в другое. На дугах принято указывать пары вход­ных и выходных сигналов – сигналов переходов.

Если автомат переходит из состояния q₁ в состояние q₂ под воз­действием нескольких входных сигналов, то на соответствующей дуге графа этот вариант будет представлен через дизъюнкцию. Для представления автомата используют двухполюсные графы с выде­ленными начальным и конечным состояниями.

Задание 11.2. В предыдущем задании автомат задан в виде таблицы. Задать его в виде графа.

Решение.

1. Отмечаем вершины графа – множество состояний Q={1,2.3}

2. Берется  первое преобразование:  1,a ® 3,n. Оно переводит  состояние 1 в состояния 3 с помощью входного сигнала a, в результате которой образуется выходной сигнал n. Строится первая стрелка (ребро) от 1 до 3, делая на ней надпись (a,n)

3. Берется  второе  преобразование 1,b®2,p. Строится стрелка от 1 до 2 с надписью (b, p)/

4. Аналогично рассматриваются остальные преобразования.

Ответ. Искомый граф представлен на рисунке.

Задание 11.1. Конечный автомат имеет алфавиты:

X={a,b} – множество входных символов,  Y={d,h,k,t} множество выходных символов,

Q={1,2,3,4} множество состояний.  Задать три автомата на заданных множествах таблицами (матрицами). Для каждого автомата записать систему команд преобразования и построить соответствующие им графы.

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

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

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

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

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

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

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

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

При выборе языка предпочтение отдается языкам, основан­ным на использовании логики предикатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

правильно сформулированные задачи, которые может решать человек. о ; Может ли автомат заменить человека?

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

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

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

Контрольные вопросы

1. Определение автомата – двоякий смысл автомата.

2. Виды автоматов.

3. Способы задания автоматов.

4. Привести идеи фантастов, которые нашли отражение в современной действительности

Требования к знаниям умениям и навыкам.

Студенты должны понимать различные трактовки понятия автомат. Знать назначение автоматов. Иметь представление о способах задания автоматов. Строить простейшие автоматы при  решении конкретных  задач

---

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

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