Методы теории автоматов. Теория автоматов

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

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

Энциклопедичный 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 } -переход (эпсилон-переход).сложности задач.

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

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Министерство образования РФ

Государственное образовательное учреждение

высшего профессионального образования

Сибирский Государственный аэрокосмический университет

имени академика М.Ф. Решетнева

Кафедра Системного анализа

Реферат по дисциплине "Теория систем" на тему:

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

Выполнил: Ларионов А.Ю.

Проверил: Иконников О.А.

Красноярск 2013 г.

Введение

1. Общие сведения о теории автоматов

1.1 Распознаватели

1.2 Классификация автоматов

1.2.1 Абстрактный автомат

1.2.2 Виды и подвиды автоматов

2. Цифровые автоматы. Общие сведения

2.1 Логические элементы

2.2 Теория конечных цифровых автоматов с памятью

2.3 Частичные автоматы

2.4 Т-триггер

2.5 D-триггер

2.6 RS-триггер

2.7 JK-триггер

2.8 Универсальный триггер

Заключение

Список использованных источников

Введение

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

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

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

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

1. Общие сведения о теории автоматов

Теория автоматов подразделяется на абстрактную и структурную теорию.

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

Структурная теория автоматов изучает общие приёмы построения структурных схем автоматов на основе элементарных автоматов.

1.1 Распознаватели

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

Язык L праволинейный тогда и только тогда, когда он определяется односторонним детерминированным конечным автоматом;

Язык L контекстно свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью;

Язык L контекстно зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным автоматом с магазинной памятью;

Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга (этот вид математических объектов рассматривается в курсе "Математическая логика и теория алгоритмов").

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

Рисунок 1 - Распознаватель

Работа распознавателя осуществляется следующим образом:

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

Незаполненные ячейки (по окончании входной строки) заполняются специальным символом, обозначающим конец строки. Обычно совпадает с символом пустой строки языка е (см. рис. 1);

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

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

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

1.2 Классификация автоматов

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

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

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

1.2.1 Абстрактный автомат

Абстрактный автомат - математический объект, представляющий собой совокупность элементов: A=(S,X,Y,д,л), где S - конечное множество состояний автомата; X,Y - конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом; д:SxY->S - переходное отношение (переходная функция); л - выходная функция.

Абстрактный автомат имеет следующую функциональную схему, в соответствии с рисунком 2.

Рисунок 2 - Функциональная схема абстрактного автомата

Где si - новое состояние автомата; xi - текущий входной символ; yi - текущий выходной символ.

Порядок работы абстрактного автомата следующий:

При поступлении очередного символа на вход автомата переходная функция у на основании поступившего символа xi и текущего состояния si определяет новое состояние автомата Si+1;

Выходная функция на основе текущего состояния автомата si и текущего входного символа xi определяет текущий выходной символ.

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

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

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

Рисунок 3 - Иерархия автоматов

1.2.2 Виды и подвиды автоматов

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

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

Детерминированные и недетерминированные автоматы различаются количеством состояний, в которых автомат может находиться одновременно. Детерминированный автомат в каждый момент времени находится в единственном состоянии, в то время как недетерминированный автомат в каждый момент времени может находиться в нескольких состояниях одновременно.

Частным случаем недетерминированного автомата является вероятностный автомат. Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным. Иными словами, вероятностным автоматом называется система, описываемая конечными наборами входных сигналов Х={x1, x2,..., xn}, состояний S={s1, s2,..., sn}, выходных сигналов Y={y1, y2,..., yn}. Также задан набор условных вероятностей того, что вероятностный автомат, находясь в состоянии aj и получив входной сигнал x, перейдет в состояние ai, и выдаст сигнал y.

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

По наличию дополнительно памяти выделяют автоматы с магазинной памятью. В отличии от абстрактных автоматов, объём памяти, которых определяется количеством состояний, в таких автоматах имеется дополнительный элемент, называемый стеком. Стек реализует модель памяти LIFO (Last In - First Out) и служит для хранения промежуточных результатов работы.

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

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

2. Цифровые автоматы. Общие сведения

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

Все схемы ЭВМ можно разделить на два больших класса:

Класс логических или комбинационных схем (КС).

Класс конечных автоматов.

В логических (комбинационных) схемах значение выходных сигналов в момент времени t однозначно определяется значениями входных сигналов в момент времени t1 t.

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

Технические вопросы синтеза комбинационных схем решаются с помощью аппарата математической логики. При этом используется самая простая часть математической логики, а именно, алгебра логики или Булева алгебра. Основным понятием в алгебре логики, на котором основывается её приложение к синтезу КС, является понятие Булевой или переключательной функции (ПФ).

2.1 Логические элементы

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

В эту систему элементов входят как элементы универсального базиса: И-НЕ, ИЛИ-НЕ, так и комбинации операций булевого базиса: И-ИЛИ-НЕ.

2.2 Теория конечных цифровых автоматов с памятью

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

y (t ) = f (x (t ) ) .

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

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

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

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

Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1 и т.д.

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

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

Автомат функционирует в дискретные моменты времени, интервал, между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T=const) и асинхронного действия (Tconst). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами, t=0,1,2,3,…., имеющими смысл номера такта.

Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y,), где A = {a0,a1,a2,...,an}- множество внутренних состояний автомата, X = {x1, x2,…, xm} - множество входных сигналов (входной алфавит), xi - буква входного алфавита, Y = {y1, y2,…, yk} - множество выходных сигналов (выходной алфавит),

Функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находится в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, то есть a(t+1) = ,

Функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = .

Автомат работает следующим образом: в каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний. Причем в начальный момент времени t = 0 он всегда находится в состоянии a(t = 0) = a0. В момент времени t автомат воспринимает входной сигнал x(t), выдает выходной сигналу y(t) = и переходит в следующее состояние a(t+1)=. Другими словами абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t+1) и y(t). Такие автоматы называют детерминированными. На преобразование информации в детерминированных автоматах наложены условия.

Условия преобразования информации в детерминированных автоматах:

1) любое входное слово, длинною l букв, преобразуется в выходное слово той же длины.

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

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

Применяемые на практике автоматы принято разделять на два класса - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Функционирование автоматов строго подчиняется определённым законам (законы функционирования автоматов). Законы функционирования автоматов описываются системами уравнений:

Автомат Мили:

a(t + 1) =
y(t) =

Автомат Мура:

a(t + 1) =

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

При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Таблица переходов

Строки этих таблиц соответствуют входным сигналам x (t ), а столбцы - состояниям. На пересечении столбца ai и строки x j в таблице переходов ставится состояние a s = [ a i, x j], в которые автомат перейдет из состояния a i под воздействием сигнала x j; а в таблице выходов - соответствующий этому переходу выходной сигнал y g = [ a i,x j]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых случаях более удобна.

Совмещенная таблица переходов и выходов автомата Мили:

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

Отмеченная таблица переходов автомата Мура:

В этой таблице каждому столбцу приписан, кроме состояния a i, еще и выходной сигнал y (t ) = (a (t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги - переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s, если в автомате имеется переход из a i в a s, то есть a s = (a i, x j). В автомате Мили дуга отмечается входным сигналом x j, вызвавшим переход, и выходным сигналом y g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

Граф для автомата Мили:

Граф для автомата Мура

2.3 Частичные автоматы

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

Пример таблицы переходов и выходов частичного автомата Мили

Из таблицы переходов видно, что Т-триггер обладает полной системой переходов и выходов, поскольку для каждой пары состояний (0-0, 0-1, 1-0,

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

Матрица переходов:

Матрица переходов определяет значения сигналов на входах элементарного автомата, обеспечивающие каждый их четырех возможных переходов. Здесь Q(t) и Q(t+1) - состояния автомата в моменты времени t и t+1 соответственно. Поскольку Т-триггер имеет один вход, а число возможных переходов равно четырем, то матрица переходов имеет четыре строки.

Для записи закона функционирования Т-триггера в аналитическом виде составим диаграмму Вейча по матрице перехода:

Из диаграммы имеем:


=> (T(t) + Q(t)) mod 2

Поскольку эта формула совпадает с аналитической записью переключательной функции сложение по модулю два, то Т-триггер часто называют триггером со счетным входом Т, а входной сигнал, поступающий на вход Т, счетным сигналом. На практике кроме асинхронного Т-триггера, работу которого мы рассмотрели, используют так же и синхронный Т-триггер, который в отличие от асинхронного меняет свои состояния только при Т = 1 и С = 1. Если хотя бы один из этих сигналов равен нулю, то триггер сохраняет свое состояние. Вход С называют входом синхронизации.

Поясняющая работу комбинационная схема и обозначение синхронного

Т-триггера представлены на рисунке:

2.5 D-триггер

D-триггером (триггером задержки) называют элементарный автомат Мура с двумя устойчивыми состояниями и одним входом D таким, что Q(t+1) = D(t). Название D-триггера происходит от английского слова "delay" - задержка. Из определения следует, что состояние триггера в момент времени t+1 повторяет значение входного сигнала D(t) в момент времени t (отсюда и название триггера задержки).

Матрица переходов для D-триггера:

Обозначения асинхронного и синхронного D-триггеров:

В синхронном D-триггере при С=0 триггер свое состояние не меняет, а при С=1 работает так же, как и асинхронный, то есть

Q(t+1)=D(t)C(t) v Q(t)

Асинхронный D-триггер практического значения не имеет.

Граф D-триггера

2.6 RS-триггер

RS-триггером называют автомат Мура с двумя устойчивыми состояниями, имеющий два входа R и S такие, что при S=1 и R=0 триггер принимает состояния 1, а при R=1 и S=0 состояние 0. В соответствие с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R нулевым.

Матрица переходов RS-триггера:

Комбинация сигналов R=1 и S=1 является запрещенной и поэтому переход в триггере при таких значениях входных сигналов не определен. Переход триггера из 0 в 0 возможен при двух комбинациях входных сигналов: R=0, S=0 и R=1, S=0. Поэтому в первой строке матрицы переходов RS триггера в столбце R поставлена переменная b1, которая может принимать два значения 0 v 1. Аналогично, переход из состояния 1 в 1 также возможен при двух комбинациях входных сигналов: R=0, S=0 и R=0, S=1. Поскольку при таком переходе значения сигнала на входе S безразлично, то в нижней строке матрицы переходов в столбце S записана переменная b2. По матрице переходов можно построить граф RS-триггера.

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

Запишем закон функционирования RS-триггера в аналитическом виде, для чего составим по матрице переходов диаграмму Вейча:

2.7 JK-триггер

JK-триггером называют автомат Мура с двумя устойчивыми состояниями и двумя входами J и K, который при условии J * K = 1 осуществляет инверсию предыдущего состояния (т.е. при J*K=1, Q(t+1) = Q(t)), а в остальных случаях функционируют в соответствии с таблицей истинности RS триггера, при этом вход J эквивалентен входу S, а вход K - входу R. Этот триггер уже не имеет запрещенной комбинации входных сигналов и его таблица истинности, то есть зависимость Q(t+1) = f имеет вид:

Таблица истинности JK-триггера:

По этой таблице можно построить диаграмму Вейча для Q(t+1), которую можно использовать для минимизации, и матрицу переходов:

Матрица переходов JK-триггера:

В интегральной схемотехнике применяются только тактируемые (синхронные) JK триггера, которые при C=0 сохраняют свое состояние, а при C=1 работают как асинхронные JK триггера.

2.8 Универсальный триггер

Триггер JK относится к разряду универсальных триггеров, поскольку на его основе путем несложной внешней коммутации можно построить RS-, D- и T- триггера. RS-триггер получается из триггера JK простым наложением ограничения на комбинацию входных сигналов J=K=1, так как эта комбинация является запрещенной для RS триггера.

Счетный триггер на основе JK триггера получается путем объединения входов J и K.

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

Заключение

В данной работе были описаны основные принципы работы автоматов. При этом автоматы были разделены на абстрактные и автоматы, применяемые в микросхемотехнике. Так же теория автоматов тесно связана с теорией алгоритмов.

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

Список использованных источников

1. Дискретная математика. Учебное пособие. Саяпин А.В., Сливина Т.А. Редакционно-издательский отдел СибГАУ. Красноярск 2010 163с.

2. Лекции по теории цифровых автоматов [Электронный ресурс]. Лекции [Сайт]. URL: http://www.twirpx.com/file/455856/

Размещено на Allbest.ru

...

Подобные документы

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

курсовая работа , добавлен 18.10.2015

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

учебное пособие , добавлен 07.06.2009

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

контрольная работа , добавлен 04.02.2012

Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.

дипломная работа , добавлен 08.08.2007

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

реферат , добавлен 13.06.2011

Предмет вычислительной техники - задачи, которые умеют решать машины. Измерение сложности задачи. Алгоритм сортировки слиянием. Полиномиальные и не полиномиальные задачи. Понятие недетерменированного алгоритма. Графическое представление классификации.

презентация , добавлен 22.10.2013

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

учебное пособие , добавлен 11.02.2014

реферат , добавлен 13.01.2011

Изучение конкретного раздела дискретной математики. Решение 5-ти задач по изученной теме с методическим описанием. Методика составления и реализация в виде программы алгоритма по изученной теме. Порядок разработки программного интерфейса и руководства.

курсовая работа , добавлен 27.04.2011

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

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

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

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

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

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

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

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

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

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

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

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

Абстрактный конечный автомат 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 - поддеревья.

А.А. Ожиганов Теория автоматов. Учебное пособие - Санкт-Петербург: НИУ ИТМО, 2013. - 84 с. - экз.

Аннотация:

Целью данного учебного пособия является ознакомление студентов с методами синтеза цифровых автоматов. Приводятся сведения об абстрактных автоматах Мили и Мура. Рассматриваются табличный и графовый способы представления автоматов, вводится понятие реакции автомата на входное слово и определение эквивалентных автоматов. Представлены методы взаимного эквивалентного преобразования автоматов. Приводятся общие сведения о микропрограммном управлении, понятия микрокоманды, микрооперации, микропрограммы, способы представления микропрограмм в виде граф-схем алгоритмов (ГСА), формул переходов, матричных и логических схем алгоритмов. Приводятся методы разметки ГСА и правила построения по ним автоматов Мили и Мура. Рассматриваются методы канонического синтеза структурных автоматов. Приводятся примеры синтеза памяти структурного автомата на базе D -, Т -, RS - и JK триггеров.

Описание:

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

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

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

Термин «А. т.» вошел в обиход в 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. Б. А, Трахтенброт.