Автомат Конечный

Математическая модель устройства с конечной памятью, преобразующего дискретную информацию. А. к. является одним из важнейших видов управляющих сиcтем. Содержательно А. к. можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый из моментов дискретного времени, наз. тактовыми моментами, в одном из псостояний По входному каналу в каждый тактовый момент в устройство поступают сигналы — буквы входного алфавита. В те же моменты по выходному каналу устройство выдает сигналы — буквы выходного алфавита. С соответствующей точки зрения, к таким устройствам могут быть отнесены формальные системы, реальные автоматы, живые организмы и т. п. Существуют различные подходы к определению понятия А. к. При макроподходе, т. е. когда интересуются только внешним поведением устройств, определение А. к. может быть дано в виде совокупности функций, либо в виде конечного ориентированного графа, либо в алгебраич. форме — в виде конечной алгебры с унарными операциями (см. Автоматов способы задания). При микроподходе А. к. задается множеством элементов и схемой их соединения, т. е. в этом случае кроме функционирования описывается и строение автомата, в связи с чем это понятие обычно наз. структурным, а сами А. к.- структурными автоматами, или автоматными сетями. Макроподход. А. к.- это система где — конечные, как правило непустые, алфавиты, наз., соответственно, входным алфавитом, множеством состояний и выходным алфавитом; — функция переходов, отображающая множество в — функция выходов, отображающая в В. Такие А. к. иногда называются автоматами Мили. В случае, когда функция выходов отображает Sв В(т. е. не зависит от букв входного алфавита), А. к. называют а в-томатом Мура. Всякий автомат Мура является автоматом Мили. Важнейшей характеристикой А. к. является его поведение (см. Автомата поведение), к-рое может быть определено по-разному. В зависимости от того, какой тип поведения рассматривается, А. к. подразделяются на преобразователи, акцепторы (распознаватели), генераторы и др. Чтобы определить основные виды поведения А. к., функции j и y распространяют на множество (где — множество всех слов в алфавите А, включая пустое слово ): (здесь а запись обозначает слово, получаемое путем приписывания буквы акслову a). Таким образом распространенные функции для произвольных и описывают соответственно состояние, в к-рое переходит автомат из состояния s под действием входного слова и выходную букву, к-рая выдается автоматом в момент поступления последней буквы входного слова Пусть обозначает начало длины слова — слова в алфавитах определяемые следующим образом: Функции описывают уже последовательность всех состояний, в к-рых находился автомат при поступлении в него букв слова а также выходное слово, т. е. последовательность букв выходного алфавита, выдаваемых автоматом под воздействием входного слова Тернарное отношение наз. функционированием А. к. =( А, S, В,j, y). Функции естественно распространяются и на бесконечные последовательности (сверхслова) в алфавите А. Поэтому под функционированием А. к. иногда понимают отношение вида F, в к-ром a — произвольное сверхслово. В этом случае значение функции определяется как множество всех тех и только тех состояний, к-рые встречаются в последовательности бесконечное число раз. А. к. с выделенным начальным состоянием наз. инициальным и обозначается Поведением инициального А. к. наз. обычно одно из следующих трех отношений. 1) Функция отображающая (или , где — множества всех сверхслов в алфавитах Аи Всоответственно). Эта функция наз. функцией вычислимой, или реализуемой, инициальным А. к. 2) Множество определяемое для выделенного множества заключительных состояний так: Множество наз. событием, представимым А. к. с множеством заключительных состояний. 3) Множество значений функции для всевозможных называемое множеством, перечислимым данным 4) Множество определяемое для системы подмножеств множества следующим образом: Множество наз. сверхсобытием, представимым А. к. с системой' заключительных подмножеств состояний. А. к. с поведением типа 1) наз. конечным преобразователем, ас поведением типа 2) — конечным распознавателем, или акцептором. Если в качестве входного и выходного алфавитов взять декартовы произведения X соответственно, то поведением типа 1) будет набор из га функций от таргументов. В этом случае говорят, что автомат имеет твходов и n выходов, причем алфавиты наз., соответственно, входными и выходными алфавитами такого автомата. Класс событий, представимых А. к., и класс функций, вычислимых А. к., могут быть описаны различными математич. средствами. Основной результат состоит в том, что события, представимые А. к., совпадают с так наз. регулярными событиями, а функции, вычислимые А. к., совпадают с ограниченно-детерминированными функциями. Кроме того, класс множеств, перечислимых А. к., совпадает с классом событий, представимых А. к. Относительно поведений 2), 3) и 4) автоматы Мура эквивалентны автоматам Мили в том смысле, что для всякого автомата Мили найдется эквивалентный ему, т. е. имеющий то же самое поведение, автомат Мура, и обратно. Для поведения 1) это неверно. Однако, если в автоматах Мура вместо брать функции вида то автоматы Мура будут эквивалентны автоматам Мили. Автомат Мура наз. автономным автоматом, или генератором, если функция переходов не зависит от букв входного алфавита. Под поведением инициального автономного автомата принято понимать сверхслово где . Эта последовательность является периодической с нек-рым предпериодом. А. к. паз. переходной системой, если B-S и для всякого s из Sимеет место или же если выходной алфавит В — пустой. Таким образом, переходная система полностью определяется тройкой Понятия А. к. и функционирования А. к. могут быть определены различными эквивалентными способами (см. Автоматов способы задания, Автомата поведение). Широкое распространение получили так наз. канонические уравнения. Для произвольного слова пусть обозначает t- юбукву слова , а — длину слова Тогда функционирование FА. к. состоит из всех тех и только тех троек слов , к-рые удовлетворяют условиям: 1) 2) для всякого tтакого, что имеют место равенства Для определения поведения инициального А. к. необходимо добавить равенство Совокупность этих равенств однозначно определяет поведение инициального А. к. и наз. обычно каноническими уравнениями. Канонич. уравнения широко используются в задачах анализа и синтеза автоматов. Микроподход. Рассматривается множество элементов, состоящее из определенных выше А. к. с входными и выходными алфавитами вида где А — конечный алфавит, одинаковый для всех элементов. Правила построения структурных А. к. из элементов описывают дозволенные соединения (отождествления) входов и выходов, а также определяют множества входов и выходов, получаемых А. к. Важнейшим примером таких А. к. являются логические сети (л. с.). Ниже приводится один из вариантов этого понятия. В рассматриваемом случае и элементами являются так наз. функциональные элементы (ф. э.), представляющие собой А. к. с одним состоянием, а также специальные автоматы Мура, наз. задержками. Последние характеризуются тем, что они имеют два состояния, к-рые обычно обозначаются буквами О и 1 входного алфавита, при чем функции переходов и выходов удовлетворяют условиям: Поскольку ф. э. имеет только одно состояние, то он полностью характеризуется функцией выходов y, являющейся в этом случае булевой функцией от паргументов, где п — число входов ф. э. Элементы являются исходными л. с., входы и выходы к-рых совпадают, соответственно, с входами и выходами элементов. Дальнейшее построение более сложных л. с. производится по следующим правилам. 1. Объединение двух л. с. есть л. с., входами и выходами к-рой являются, соответственно, входы и выходы объединяемых л. с. (рис. 1). 2. Результат отождествления любых двух входов л. с. является л. с., выходы к-рой совпадают с выходами исходной л. с., а входами служат все входы исходной л. с., кроме одного из отождествленных (рис. 2). 3. Результат отождествления выхода одной л. с. с входом другой л. с. есть л. с. Ее входами являются все входы первой л. с. и те входы второй л. с., к-рые не отождествлялись с выходом первой л. с.; ее выходами являются все выходы обеих л. с. (рис. 3). 4. Результат отождествления выхода л. с., являющегося выходом задержки, с произвольным входом этой же л. с. есть л. с., входы к-рой — все входы исходной л. с., кроме отождествленного, а выходы — все выходы исходной л. с. (рис. 4). (При нек-рых ограничениях это правило может быть применимо и к выходам, не являющимся выходами задержек.) 5. В любой л. с. можно объявить выходами только часть выходов, определенных согласно правилам 1 — 4. Л. с., получаемые из ф. э. с помощью правил 1, 2, 3, 5, наз. обычно схемами из ф. э. Функционирование л. с. содержательно можно описать следующим образом. Пусть в момент tвсем входам л. с. приписаны входные буквы и определены состояния задержек. Тогда в этот же момент всем входам и выходам элементов л. с., в частности всем выходам л. с., будут приписаны буквы в соответствии со следующими правилами. Если входам ф. э. с выходной функцией приписаны, соответственно, буквы то его выходу в этот же момент будет приписана буква, являющаяся значением Если задержка находится в момент tв состоянии a, то в этот же момент ее выходу приписывается буква а. Отождествленным входам и выходам приписываются одинаковые буквы. Далее, в момент состояния задержек определяются входными буквами в момент t, как было определено выше, т. е. Таким образом, при фиксированных начальных состояниях задержек л. с. определяет нек-рое отображение входных последовательностей в алфавите в выходные последовательности в алфавите где — число входов, а n, — число выходов л. с. Класс таких отображений совпадает с классом функций, реализуемых А. к. в первом смысле (т. е. с классом ограниченно детерминированных функций), поскольку описанное выше функционирование л. с. совпадает с функционированием А. к. ( ), где — число входов, — число выходов л. с., S — декартово произведение множеств состояний всех задержек л. с.; функция переходов ф является покоординатным применением функций переходов задержек, а функция выходов определяется в соответствии с вышеописанным функционированием ф. э. и задержек. Пусть, напр., элементами являются задержки (к-рые на рисунке изображаются прямоугольниками) и ф. э. с выходными функциями (треугольники с соответствующими символами функции). На рис. 5 изображена л. с., к-рая в тактовый момент tвыдает выходную букву 1 в том и только в том случае, если среди входных букв в моменты 0, 1, 2, .. ., tсодержится нечетное число букв 1 (задержка в начальный момент имеет состояние 0; буквами а и bобозначены, соответственно, вход и выход л. с.). Если обозначить через s(t), a(t), b(t), соответственно, состояние, входную букву и выходную букву в момент t, то функционирование такой л. с. можно задать следующими канонич. уравнениями: При макроподходе этот автомат можно представить в виде (mod 2) и Понятие А. к. явилось отправным пунктом современной автоматов теории, изучающей также различные модификации и обобщения этого понятия.