ПОВЕДЕНИЕ АВТОМАТОВ.

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

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

Если — автомат детерминированный или автомат недетерминированный, то координаты текущей точки должны удовлетворять рекуррентным соотношениям

где Y — ф-ция переходов, Ф — ф-ция выходов (для недетерминированного автомата эти ф-ции не однозначны). В случае же автомата вероятностного на мн-ве всех траекторий определена вероятностная мера, индуцируемая матрицами переходных и выходных вероятностей.

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

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

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

В соответствии с этим возможна такая классификация концепций поведения: реализация оператора в автомате — с автоматом ассоциируется словарный оператор представление (распознавание) мн-ва — с автоматом ассоциируется мн-во М, элементы которого он принимает; порождение (перечисление) мн-ва — с автоматом ассоциируется мн-во М, элементы которого он порождает. Другой признак, по которому различаются концепции поведения: являются ли аргумент и значение оператора Т (элементы мн-ва М) конечными или бесконечными словами. Соответственно говорят о конечном или бесконечном П. а.

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

Поведение детерминированных автоматов. Рассмотрим сначала некоторые варианты реализации оператора в детерминированном автомате при фиксированном начальном состоянии (в автомате инициальном

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

а) Реализация в реальное время (бесконечное поведение) определяется вполне аналогично. Оператор ) перерабатывает каждое бесконечное слово в то бесконечное слово которое однозначно определяется рекуррентными соотношениями (2) и начальным условием

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

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

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

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

Пусть мн-во состояний головки, алфавит ленты.

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

Говорят, что на ленте записано некоторое слово в алфавите если в ячейках, следующих одна за другой слева направо без пропусков, записано это слово, а в остальных ячейках — символ Для слова х в алфавите процесс вычисления слова только оператор Т определен для этого значения аргумента) заключается в следующем. В качестве q (1) берется такая начальная конфигурация, в которой на ленте записано слово х, начиная с обозреваемой головки ячейки. Процесс (3) продолжается до первого появления заключительной конфигурации q (v); если при этом окажется, что на ленте записано некоторое слово у в алфавите то по определению

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

д) Представление языка М в реальное время. Настройка: фиксируются начальное состояние и мн-во заключительных состояний Для каждого слова в алфавите X рекуррентное соотношение дополненное начальным условием однозначно определяет состояние Слово х считается принятым, если , и отвергнутым в противном случае. Мн-во М, представляемое при такой настройке, состоит из всех принимаемых слов.

е) Представление в реальное время мн-ва М бесконечных слов. Настройка: фиксируется начальное состояние и система Z подмножеств мн-ва Q. Каждому бесконечному слову в алфавите X соответствует

единственный процесс где .

Пусть H — мн-во всех тех состояний, каждое из которых встречается бесчисленное мн-во раз в этом процессе; тогда автомат принимает слово х, если Н е Z, и отвергает в противном случае.

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

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

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

Спектр равен максимальному числу попарно к-различимых состояний автомата ЗЛ Аналогичный спектр вводится и для операторов без предвосхищения.

Исследование поведения автоматов сосредоточено на следующих направлениях.

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

II. Исследование вычисл. средств, пригодных для решения задач заданного типа. Задан некоторый класс операторов (множеств) и нужно выяснить, автоматами какого типа и при какой концепции возможна их реализация (возможно представление). Некоторые результаты: 1) для реализации всех эффективных (рекурсивных) операторов достаточно привлечь машины Тьюринга с тремя состояниями головки или машину Тьюринга с некоторыми жесткими ограничениями на допустимые замены символов на ленте; 2) для реализации оператора без предвосхищения Т в реальное время необходимо, чтобы спектр различимости автомата был не меньше спектра этого оператора. В частности, оператор, спектр которого имеет рост порядка , не реализуем ни в какой машине Тьюринга или автомате Неймана со входом и выходом. Проблему синтеза автомата также можно отнести к этому направлению.

III. Сравнение вычисл. силы автоматов различных типов сводится к сравнению соответствующих классов реализуемых операторов (представимых множеств). Это позволяет выяснить в ряде случаев, какие факторы существенны для расширения вычисл. возможностей автоматов и какие — нет.

Некоторые результаты: 1) в классе конечных автоматов сравним поведение детерминированных, недетерминированных и вероятностных автоматов, в смысле концепций д) — е). Поскольку детерминированный автомат можно рассматривать как частный случай недетерминированного, а также вероятностного

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

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

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469]; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389—395]; Бухараев Р. Г. Вероятностные автоматы. Казань. 1970: Автоматы. Пер. с англ. М., 1956. Б. А. Трахтенброт.