Лекции по теории автоматов - файл теория автоматов.doc. Основные понятия теории абстрактных автоматов По теории автоматов

Вычислительные машины, представленные в виде математических моделей - и задачи, которые они могут решать.

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

Энциклопедичный YouTube

1 / 3

✪ Урок 12. Основы теории автоматов. Математическая логика. Уроки по информатике

✪ Как управлять миром, изучив всего одну простую модель!

✪ Урок 15. Решение прикладных задач по теории автоматов. Математическая логика. Уроки по информатике

Субтитры

Терминология

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

Слово - строка символов, создаваемая через конкатенацию (соединение).
Алфавит - конечный набор различных символов (множество символов)
Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным .

Автоматы Детерминированный конечный автомат (ДКА) - последовательность (кортеж) из пяти элементов (Q , Σ , δ , S 0 , F) {\displaystyle (Q,\Sigma ,\delta ,S_{0},F)} , где: Недетерминированный конечный автомат (НКА) - последовательность (кортеж) из пяти элементов (Q , Σ , Δ , S , F) {\displaystyle (Q,\Sigma ,\Delta ,S,F)} , где: Слово Автомат читает конечную строку символов a 1 ,a 2 ,…., a n , где a i ∈ Σ, которая называется входным словом .Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если q n ∈ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита Σ {\displaystyle \Sigma } таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

L = { w ∈ Σ ⋆ | δ ^ (S 0 , w) ∈ F } {\displaystyle L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(S_{0},w)\in F\}}

Обычно автомат переходит из состояния в состояние с помощью функции перехода δ {\displaystyle \delta } , читая при этом один символ из ввода. Есть автоматы, которые могут перейти в новое состояние без чтения символа. Функция перехода без чтения символа называется ϵ {\displaystyle \epsilon } -переход (эпсилон-переход).сложности задач.

Типовые задачи

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

ТЕОРИЯ АВТОМАТОВ.

ВВОДНЫЕ ПОЛОЖЕНИЯ.

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

В этой теории достаточно четко выявляются ее направления, обусловленные:

выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)

принятым уровнем абстракции (абстрактные и структурные автоматы)

спецификой применяемых математических (алгебраическая теория автоматов)

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

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

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

Основные понятия теории автоматов

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

a i  A , b j  B, q k  Q

Когда на вход подается сигнал a i , то в зависимости от него и текущего состояния q k  Q автомат переходит в следующее состояние q l  Q и выдает сигнал на выход b j  B. Это – один такт действия автомата q k a i  q l b j . Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигнала на входе меняет состояние автомата и его выходной сигнал означает элементарное преобразование поступающей в виде сигналов информации.

Бесконечный автомат – абстрактный автомат, хотя бы одно из определяющих множеств A, B, Q которого бесконечно.

Ситохастический (вероятностный) автомат - абстрактный автомат, правила преобразования информации, которого R являются вероятностными.

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

Структурный автомат - конечный автомат, внутреннее устройство которого известно.

Формальная грамматика = - система правил построения P в заданном алфавите TH(T – терминальный алфавит, Н – нетерминальный алфавит, ТН=) конечных знаковых последовательностей, множество которых образует некоторый формальный язык () (JH, Н - аксиома).

Формальный язык - язык, построенный по правилам некоторого логического исчисления (иначе – язык, синтаксис которого определен формальной грамматикой ).

Слово – цепочка символов в некотором алфавите (принято цепочки в алфавите (TH) обозначать греческими буквами; так, например,  (TH)*).

Предложение – слово в терминальном алфавите.

Продукция (синтаксическое правило) – способ преобразования цепочки вида  (, ,  (TH)*) в цепочку вида  ((TH)*).

Дерево вывода (разбора) – форма наглядного представления вывода предложения в заданной грамматике.

АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ.

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

Тип языка () по Хомскому	Тип формальной грамматики Хомского	Автоматная модель языка
	Произвольная (алгоритмическая) грамматика типа 0 	Машина Тьюринга
	Грамматика типа 1 (контекстная грамматика, Н.С. грамматика, грамматика непосредственно составляющих) В	Автомат с линейно-ограниченной памятью
	Грамматика типа 2(контекстно-свободная грамматика, К.С. грамматика, бесконтекстная грамматика) В	Магазинный автомат
	Грамматика типа 3(автоматная, регулярная, конечная) ВаС, Ва	Конечный автомат

Классы языков по Хомскому являются иерархией, т.е. язык типа 3 является подклассом языка типа 2, т.е. ( 3) ( 2) ( 1)  ( 0). Следуя приведенной таблице, можно говорить, что

регулярный язык (т.е. язык, порождаемый грамматикой типа 3) распознается конечным автоматом и в этом плане является самым простым в математическом плане

бесконтекстный язык (т.е. язык ( 2)) распознается магазинным автоматом – бесконечным автоматом, внутренняя структура которого представляет собой стековую память

контекстный язык ( 1) распознается автоматом с линейно-ограниченной памятью, т.е. автоматом, которому для распознавания последовательности длины nN необходима память объемом не более k*n, где k – число, независящее от входного слова

произвольный формальный язык, т.е. ( 0), распознается машиной Тьюринга – математического понятия для формального уточнения интуитивного понятия «алгоритм»

Замечание : В синтаксическом правиле В являются контекстами (левый и правый), которые могут быть пустыми цепочками; ВН, а,, ,   (ТН).

ФОРМАЛЬНЫЕ ГРАММАТИКИ.

Формальные грамматики = как процедуры могут быть порождающими и распознающими. Порождающая грамматика по существу является частным случаем формальной системы FS / =<, D>-=. В этом случае A=TH, F(TH) * , JH, P= i  j  i , j  N ,  i ,  j (TH) * , т.е. правила вывода P позволяют получать слова в терминальном алфавите Т из единственной аксиомы J путем замещения нетерминальных символов цепочек в алфавите (TH).

Распознающая грамматика – алгоритм, распознающий по любой цепочке, является ли оно словом языка  T * .

Автомат для распознавания и порождения слов можно рассматривать как устройство обработки входных цепочек символов с целью:

определения их принадлежности формальному языку ()

порождений выходных цепочек символов

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

Пример 1 : Т=a, b, c, H=B, C, J=B, P=BaBС, BCc, Cb

Возможным выводом в этой грамматике может быть последовательность слов:

В, аВС, аСсС, аbсС, аbсbТ *

Эта грамматика порождает язык b, bc, abcb.

Пример 2 : множество нечетных чисел в унарном представлении – это множество терминальных слов вида а, ааа, ааааа….., т.е. язык =хТ * : ха 2 n -1 , nN. Этот язык порождается автоматной грамматикой  3 =<a, J, J, Ja, JaB, BaJ>.

Пример 3 : Язык =хТ * : х=a n b n  n  N порождается К.С. грамматикой, т.е.  2 =<a, b, J, J, JaJb, Jab>.

Пример 4 : Язык булевых формул с переменными x, y, z порождается К.С. грамматикой  2 =<x, y, z, , , , (,), J, J, J(JJ), J(JJ), JJ, Jx, Jy, JZ>.

ДЕРЕВЬЯ ВЫВОДА ПРЕДЛОЖЕНИЙ.

На практике вывод слов языка () в виде последовательности цепочек часто оказывается громоздким. Кроме того, такой способ не позволяет получить в удобном виде информацию о синтаксических конструкциях. Наилучшим способом компактного представления вывода слов в таком случае является дерево вывода (дерево синтаксического анализа, дерево грамматического разбора). Говорят, что задано стандартное дерево вывода, если правилу r i:  1 A 2  1  2 (здесь  1 ,  2 – контекст,  1 ,  2 (TH) *), АН, (TH) *) поставлено в соответствие элементарное поддерево t(r i) с вершиной А и кроной  1  2.

Пример 1 : Пусть 1=<a, b, c, A, B, C, D, J, J, JAAB, ABDBB, aBBabB, Aa, Da, BC, Cc>.

Вывод J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc представим деревом:

ЗдесьJ – корень дерева, J A , A a - поддеревья.

Теория автоматов

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

Терминология

Слово - строка символов, создаваемая через конкатенацию (соединение).
Алфавит - конечный набор различных символов (множество символов)
Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.

Автомат Автомат - последовательность (кортеж) из пяти элементов , где: Слово Автомат читает конечную строку символов a 1 ,a 2 ,…., a n , где a i ∈ Σ, и называется словом .Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если q n ∈ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

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

Применение

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

Другое важнейшее применение теории автоматов - математически строгое нахождение разрешимости и сложности задач.

Типовые задачи

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

См. также

Литература

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. - М .: Вильямс, 2002. - С. 528. - ISBN 0-201-44124-1
Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ, 1995. - C. 112.

Ссылки

Wikimedia Foundation . 2010 .

Азиатская конфедерация футбола
Теория сложности вычислений

Смотреть что такое "Теория автоматов" в других словарях:

Теория автоматов

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

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

теория автоматов - сущ., кол во синонимов: 1 тавт (1) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

теория автоматов - automatų teorija statusas T sritis automatika atitikmenys: angl. automata theory vok. Automatentheorie, f rus. теория автоматов, f pranc. théorie des automates, f … Automatikos terminų žodynas

Диаграмма состояний (теория автоматов) - У этого термина существуют и другие значения, см. Диаграмма состояний. Диаграмма состояний ориентированный граф для конечного автомата, в котором вершины обозначают состояния дуги показывают переходы между двумя состояниями На практике… … Википедия

Теория механизмов и машин - Теория машин и механизмов (ТММ) это научная дисциплина об общих методах исследования, построения, кинематики и динамики механизмов и машин и о научных основах их проектирования. Содержание 1 История развития дисциплины 2 Основные понятия … Википедия

ТЕОРИЯ - (1) система научных идей и принципов, обобщающих практический опыт, отражающих объективные природные закономерности и положения, которые образуют (см.) или раздел какой либо науки, а также совокупность правил в области какого либо знания млн.… … Большая политехническая энциклопедия

Теория алгоритмов Экономико-математический словарь

Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Проблема построения алгоритма с теми или иными свойствами называется алгоритмической проблемой, ее неразрешимость означает отсутствие соответствующего алгоритма; если… … Экономико-математический словарь

Книги

Теория автоматов. Учебник для бакалавриата и магистратуры , Кудрявцев В.Б.. Учебник содержит обширный материал по теории автоматов. В нем вводится понятие автомата, даны теории…

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

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

Термин «А. т.» вошел в обиход в 50-е годы 20 ст., хотя соответствующая проблематика в значительной мере начала складываться еще в 30-е годы в рамках теории алгоритмов и теории релейных устройств. Еще тогда в алгоритмов теории были сформулированы достаточно общие понятия вычисл. автомата (см. Тьюринга машина) и (неявно) понятие автомата конечного (головка машины Тьюринга). Было установлено, что для осуществления

всевозможных эффективных преобразований информации вовсе не обязательно строить каждый раз специализированные автоматы; в принципе все это можно сделать на одном универсальном автомате при помощи подходящей программы и подходящего кодирования. Этот теор. результат позже получил инженерное воплощение в виде современных универсальных вычисл. машин. Однако развернутое изучение процессов, протекающих в автоматах различного рода, и общих закономерностей, которым они подчинены, началось позднее лишь в рамках А. т. Различие в постановках между задачами теории алгоритмов и А. т. можно кратко охарактеризовать как различие между вопросами о том, что могут делать автоматы и как они это делают. Поскольку привлечение др. типов автоматов (отличных от машин Тьюринга) заведомо не расширяет запаса вычислимых преобразований информации, то для теории алгоритмов такое привлечение носит лишь эпизодический характер и связано только с применяемой техникой доказательств. С другой стороны, для А. т. такое рассмотрение становится уже самоцелью. Теор. и прикладные задачи автоматики, вычисл. техники и программирования, моделирования биол. поведения и др. продолжают стимулировать проблематику А. т. Однако наряду с этим, А. т. уже вырабатывает собственную внутреннюю проблематику. В А. т. широко применяется аппарат алгебры, логики математической, комбинаторного анализа (включая графов теорию) и вероятностей теории.

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

Поведение и структура. В основе А. т. лежат точные матем. понятия, формализующие интуитивные представления о функционировании и поведении автомата, а также о его структуре (внутреннем устройстве). С точки зрения их поведения, автоматы чаще всего рассматриваются как преобразователи словарной информации, т. е. преобразователи последовательностей букв в последовательности букв. Реализуемое преобразование интерпретируется обычно как вычисление значений некоторой ф-ции (оператора) по заданным значениям аргументов или как преобразование записей условий задач некоторого типа в записи соответствующих решений. В частности, т. н. распознающие автоматы, воспринимая входную информацию, реагируют на нее так, что некоторые входные последовательности сигналов они принимают, а другие - отвергают. В этом смысле они распознают или, как говорят еще, представляют мн-ва входных последовательностей. Наконец, порождающий автомат функционирует как автономная система, не связанная со входной информацией, его поведение определяется тем, какие выходные последовательности он способен порождать. Приведенная классификация в терминах преобразования, распознавания и порождения зависит от правил функционирования автомата, т. е. от программы взаимодействия его внутренних состояний со входными (поступающими из внешней среды) и выходными (вырабатываемыми во внешнюю среду) сигналами. Пусть Q, X, Y - соответственно мн-ва внутренних состояний входных и выходных сигналов автомата. Если это детерминированный автомат, его программа формализуется в терминах ф-ции переходов Ч и ф-ции выходов Ф, указывающих для каждого входного сигнала х и каждого состояния состояние в которое переходит автомат, и вырабатываемый им при этом выходной сигнал

Абстрактная А. т. характеризуется более высоким уровнем абстракции: в ней понятие автомата отождествляется с понятием программы автомата, т. е. с пятеркой (), при полном отвлечении от его структуры. Структура автомата отражает способ его организации из более простых взаимодействующих компонент (элементарных автоматов или просто - элементов), надлежащим образом соединенных в единую систему. Напр., вычисл. машина составлена из элементарных ячеек типа триггеров, инверторов и т. п.; нервная система построена из нейронов. Структурная классификация автоматов определяется характером допускаемых соединений (соединения могут быть жесткими или же изменяться в процессе работы, подвергнуты тем или иным геом. ограничениям), а также спецификой функционирования и взаимодействия употребляемых элементов (напр., элементы могут только обмениваться информацией или же они могут порождать новые элементы, наращивая структуру). Формализация структурных понятий осуществляется в терминах различного рода схем (см. Сеть логическая). А. Н. Колмогоров наметил подход, приведший к формулировке весьма общего, но все еще конструктивного понятия структуры автомата (см. Автоматы растущие), которое, по-видимому, охватывает все известные типы структур автоматов и все те, которые можно предвидеть на современном уровне науки. Вполне очевидно, что имеется тесная связь между структурой автомата и его поведением. Однако раздельное изучение каждого из этих двух аспектов при значительном отвлечении от другого не только возможно, но зачастую и полезно при постановке и решении многих важных проблем. Такое изучение производится соответственно в абстрактной (поведенческой) и структурной теории автоматов.

Типы автоматов. Наиболее распространенной является классификация автоматов и со-отв. разделов А. т., посвященных различным

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

1) Объем памяти. Конечные и бесконечные автоматы характеризуются соотв. конечностью и бесконечностью объема памяти (числа внутренних состояний). Конечными автоматами являются отдельные блоки современных вычисл. машин и даже машина в целом. Мозг также можно рассматривать как конечный автомат. Бесконечные автоматы представляют собой естественную матем. идеализацию, вырастающую из представления об автомате с конечным, но необозримо большим числом состояний. При этом имеется в виду лишь потенциальная бесконечность памяти, проявляющаяся в том, что память, хотя и остается конечной в каждый момент времени, может неограниченно возрастать. Такая идеализация возникла впервые в рамках теории алгоритмов в процессе уточнения интуитивного представления об алгоритме. Структурно-растущий автомат представляют в виде соединения элементов, способных к размножению и наращиванию схемы. Современные ЭВМ можно рассматривать как растущие (а вместе с тем и потенциально бесконечные) автоматы в следующем смысле: чтобы вычисления во всех случаях могли быть доведены до конца, приходится допускать возможность неограниченного наращивания внешней (ленточной) памяти.

2) Механизм случайного выбора. В детерминированных автоматах поведение и структура в каждый момент времени однозначно определены текущей входной информацией и состоянием автомата, сложившимся в непосредственно предшествующий момент. В вероятностных (стохастических) автоматах они зависят еще и от некоторого случайного выбора. Стохастические автоматы не следует смешивать с недетерминированными, в которых так же нарушено условие однозначности (однако без участия к.-л. механизма случайного выбора).

Проблемы и методы. К центр, проблемам А. т. относятся проблемы анализа, т. е. описания поведения автомата, исходя из заданной его программы или структуры, и синтеза - т. е. конструирования автоматов, поведение которых удовлетворяло бы заранее предъявляемым требованиям. С этими проблемами тесно связаны и многие др. задачи, которые интенсивно исследуются (полнота и универсальность, минимизация, языки, асимптотические оценки и др.). Более всего анализ и синтез исследованы в теории конечных детерминированных автоматов, причем они по-разному трактуются в абстрактной и в структурной теориях автоматов. Так, напр., в структурной теории под синтезом (см. Синтез автоматов структурный) подразумевается построение схемы из заданного ассортимента элементов, которая была бы оптим. (или близка к оптим.) в смысле некоторого выдвигаемого критерия сложности схем. Здесь преобладают комбинаторно-информационные методы и асимптотические оценки (К. Шэннон, С. В. Яблонский, О. Б. Лупанов и др.). В абстрактной теории автоматов довольствуются построением программы функционирования автомата (см. Синтез автоматов абстрактный), напр., в виде ф-ций перехода и выхода для конечного автомата, которая обычно служит исходным материалом для дальнейшего развертывания структурного синтеза. Здесь используются преимущественно алгебраические (С. К. Клини, В. М. Глушков и др.), математико-логич. (Б. А. Трахтенброт, Р. Бюхи и др.) и игровые (Р. Мак-Нотоп) методы и понятия. Проблема анализа и синтеза конечных детерминированных автоматов занимает видное место и в теории релейных устройств.

В теории экспериментов с автоматами (Э. Мур) разрабатываются методы, которые позволяют по сведениям, получаемым при внешнем наблюдении за поведением автомата, восстанавливать программу его функционирования или по крайней мере некоторые ее свойства. Эти методы можно рассматривать как своеобразный прием абстрактного синтеза и расшифровки автоматов (Я. М. Барздинь). Работы К. Шэннона, М. Рабина и др. послужили толчком к развитию теории вероятностных автоматов в следующих направлениях: 1) в какой мере понятия и методы теории детерминированных автоматов переносятся на стохастические автоматы; 2) какие упрощения вычисл. процесса достижимы при выходе из более узкого класса детерминированных автоматов в более широкий класс автоматов вероятностных. Изучение растущих автоматов сосредоточено в основном на следующих проблемах: 1) разработка моделей растущих автоматов и изучение отдельных их классов (автоматы итеративные - Ф. Хенни, автоматы регистровые - В. М. Глушков, автоматы самовоспроизводящиеся - Дж. фон Нейман, обобщенные растущие автоматы - А. Н. Колмогоров, Я. М. Барздинь); 2) оценка вычисл. способности и сложности вычислений растущих автоматов (Я. М. Барздинь, Б. А. Трахтенброт, Ю. Хартманис, Г. С. Цейтин, М. Рабин и др.).

Связь с другими научными направлениями.

Значение теории алгоритмов и теории релейных устройств для А. т. уже было разъяснено выше. Следует указать и на обратную отдачу А. т., методы которой позволили решить ряд задач, возникших в матем. логике и теории алгоритмов (Р. Бюхи). Проблематика, складывающаяся в теории растущих автоматов (напр., сложность вычислений), лежит по существу на стыке теории алгоритмов и асимптотических закономерностей структурного синтеза автоматов. Сильное взаимное проникновение А. т. и лингвистики математической, одним из важных понятий которой является грамматика порождающая, - объект весьма близкий к порождающему автомату. Поэтому отдельные довольно важные положения теории грамматик могут быть в принципе отнесены к А. т. В абстрактной теории автоматов матем. вопросы обучения, а также целесообразного поведения одного индивидуума или коллектива были уточнены и исследованы в терминах автоматов игр (М. Л. Цетлин). Полезной

оказалась также связь теории конечных автоматов с теорией проектирования ЦВМ и теорией программирования (В. М. Глушков, А. А. Летичевский).

Лит.: Гаврилов М А. Теория релейно-контактных схем. М.- Л., 1950 [библиогр. с. 298-299]; «Труды математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464- 469]; Кобр инский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М., 1962 [библиогр. с. 399-402]; Цетлин М. Л. Исследования по теории автоматов и моделированию биологических систем. М., 1969 [библиогр. с. 306-316]; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389-395]; Автоматы. Пер. с англ. М., 1956. Б. А, Трахтенброт.