О синтезе автоматов по конечным фрагментам их поведения

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

Основы теории экспериментов с автоматами заложены в работе Мура [13, где рассматривалась задача расшифровки «черного ящика», ставшая классической в теории автоматов. Эта задача состоит в восстановлении автомата — «черного ящика» по результатам проведенных с ним экспериментов. (См. также [2 — 93.) В дальнейшем она развивалась и изучалась, в частности, в рамках исследований, связанных с проблемами контроля и диагностики управляющих устройств. Обширную библиографию по этой теме можно найти в книге [23, откуда, кроме того, почерпнута терминология и основные определения, используемые в данной диссертации. Оказалось, что по конечному множеству экспериментов однозначное восстановление автомата невозможно.

В работах [6,73 исследовалась задача восстановления автомата при растущем (потенциально бесконечном) объеме информации о его внешнем поведении. Оказалось, что в этом случав возможно правильное восстановление «почти всех» автоматов. В ряде работ (см., например, [83) информация о поведении автоматов включала в себя множества «допустимых» и «недопустимых» экспериментов.

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

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

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

Как известно (см., например, С23, С.5−6, или [43) существуют различные способы задания и изучения конечных автоматов. Один из них — абстрактная (поведенческая) теория автоматов, в которой поведение автомата, т. е. его реакции на входные сигналы, изучается в отрыве от его внутренней структуры. Автоматы при этом могут быть заданы в виде диаграмм переходов или таблиц переходов ([23,0.15−16, также [ 13,13 3), однозначно определящих реакцию автоматов на всевозможные входные слова. Этот подход и принят в данной работе. При этом под сложностью автомата естественно понимать число его состояний.

В работе рассмотрено два вида множеств экспериментов, описывающих поведение автомата.

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

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

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

Во втором случав информация о поведении автомата представлена в виде набора кратных экспериментов. Как известно ([2], С.63), кратные эксперименты возникают при возможности одновременной подачи различных входных слов на различные экземпляры одного и того же автомата (находящиеся изначально в одинаковых состояниях), или же при наличии у автомата «кнопки возврата», позволяющей вернуть его в исходное состояние после подачи любого слова. С точки зрения задачи синтеза УУ, возможна иная интерпретация. Процесс, требующий управления, может быть недетерминированным, и, следовательно, на вход УУ могут поступать различные последовательности входных сигналов. Цель управления заключается в том, чтобы на любую из них УУ реагировало соответствующим образом. Ясно, что это соответствие может быть задано кратным экспериментом.

Так же, как и в первом случав, при возможности предварительной «настройки» УУ на различные внешние ситуации возникает задача синтеза автомата по набору нескольких кратных экспериментов.

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

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

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

Разработаны также достаточно простые (полиномиальной сложности) алгоритмы синтеза автоматов для различных случаев, гарантирующие построение автоматов с числом состояний, близким к минимальному. Глава I посвящена синтезу автоматов по наборам простых экспериментов, глава 2 — синтезу по наборам кратных экспериментов и синтезу акцепторов, представляющих конечные события. В главе 3 изложены разработанные алгоритмы синтеза.

В диссертации получены следующие результаты. Пусть s и t обозначают, соответственно, мощности входного и выходного алфавитовs ^ 2, t ^ 2- алфавиты считаются фиксированными.

Простые эксперименты.

Для наборов га простых экспериментов, длина каждого из которых не превосходит п, получена асимптотически точная оценка функции Шеннона L (m, n, s, t) (точные определения даны в § 1.1). А именно: n n при m? t выполнено L (m, n, s, t) = t — n при m ^ t, и при n oo выполнено w (m, n, t)], w (m, n, t) > 0 [t"oj (ffl, n, t)]f o)(m, n, t) < 0, iog+m] 1 (tiogtm] - n) где w (m, n, t) = t x — m"—!—-t — 1.

Фактически в § 1.1 получены верхняя и нижняя оценки функции.

Шеннона, дающие асимптотическую точность. В частном случае п n oo, ш = о (t) асимптотическая оценка функции Шеннона упрощается и принимает вид.

L (m, n, s, t) ^ m"(n — log^m).

Получена асимптотически точная оценка типичных значений числа состояний синтезируемого автомата. А именно, при п <�", log (m) = о (п) для почти всех наборов m простых экспериментов, длина каждого из которых не превосходит п, минимальное число состояний L синтезируемого по данному набору автомата удовлетворяет соотношению ^ ^ ш"п з-1)iogt (m-n).

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

Кратные эксперименты.

Для наборов кратных экспериментов (КЭ) получена оценка функции Шеннона по порядку величины. Пусть m — количество КЭ в наборе, anмаксимальная длина составляющих их простых экспериментов (точные определения даны в § 2.1). Кратный эксперимент называется полным кратным экспериментом (ПКЭ) глубины п, если все составляющие его простые эксперименты имеют длину п и они содержат все sn входных слов длины п. Через D (n) обозначим количество различных ПКЭ глубины почевидно, истинно равенство (п+1).

Ч+Т*].

D (n) = t.

Через RF (U, m, n) обозначим класс всех наборов различных ПКЭ глубины п над Uэтот класс не пуст при m < D (n).

Для функции Шеннона LKp (m, n, s, t) получены следующие оценки: при п -" оо, m < D (n) выполняются соотношения п (п+З) -—- < LKp (m, n, s, t) < — m’s s-1)'logt (m"sn) «» (s~1)2.iogt (m"sn) n при n -" oo, log (m) = o (s) выполняется.

LKp (m, n, s, t) > m’s n+1) s-1)2.iogt (m.sn) при m ^ D (n) выполнено LKp (m, n, s, t) = D (n).

Длятипичных значений сложности реализации наборов ПКЭ из класса RF (U, m, n) получены следующие оценки: при п со для почти всех R <е RP (U, m, n) выполнено соотношение I.

L® > n m"s s-1).iogt (m.sn) а при n oo, log (m) = o (sn) для почти всех R e RP (U, m, n).

L® > вшолнено соотношение (n+1) ш’э s-1)2.iogt (m.sn) то есть типичные значения по порядку величины совпадают с функцией Шеннона. Алгоритм синтеза, гарантирующий верхнюю оценку, и, следовательно, по порядку наилучший, приведен в § 3.3.

Автоматы как акцепторы.

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

La (n, s) получены следующие оценки: при п со выполняется п+1) (п+3) s < La (n, s) < 8 n-(s-1)2-iog2(s) ~ ~ n"(s-1)2-iog2(s) причем для почти всех событий минимальное число состояний синтезируемого автомата асимптотически не меньше приведенной нижней оценки. Алгоритм синтеза, гарантирующий верхнюю оценку, и, следовательно, по порядку наилучший, приведен в § 3.4.

Автор выражает глубокую благодарность своему научному руководителю В. А. Буевичу, а также профессору В. Б. Кудрявцеву и доценту С. В. Алешину за постановку задач, замечания, советы и обсуждение работы.

1. Мур Э. Ф. Умозрительные эксперименты с последовательностными машинами. — в кн.Автоматы. — М.: ИЛ, 1956, C.1.9−2I0.

2. Кудрявцев В. Б., Алешин С. В., Подколзин А. С.

Введение

в теорию автоматов. М.: Наука, 1985.

3. Яблонский С. В.

Введение

в дискретную математику.- М. :Наука, 1979.

4. Грунский И. С., Козловский В. А., Пономаренко Г. Г. Представления конечных автоматов фрагментами поведения. Киев: Наук, думка, 1990.

5. Гилл А.

Введение

в теорию конечных автоматов. М.: Наука, 1966.

6. Барздинь Я. М. О расшифровке автоматов при отсутствии верхней оценки числа состояний // ДАН COOP. 1970., — Т. 190, Л5С.1048−1051.

7. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы. Поведение и синтез. М.: Наука, 1970.

8. Таль А. А. Анкетный язык и абстрактный синтез минимальных последовательностных машин // Автоматика и телемеханика.1964. Т.25, *6.

9. Богомолов С. А. О синтезе автоматов по конечному множеству экспериментов // ДАН СССР. 1985. — Т.281, JH — С.20−22.

10. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: МГУ, 1984.

11. Мс Millan В. Two unequalltles implied by unique decipherability. // IRE Trans IT-2, 1956. N4, P.115−116.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

12. Ключников А. В. О сложности автоматов, реализующих конечные множества простых экспериментов. // Труды семинара по дискретной математике и ее приложениям. / Под ред. О. Б. Лупанова. М.: Моск. Университет, 1989. — С.195−201.

13. Ключников А. В. О числе состояний акцепторов, представляющих конечные события. // Конструкции в алгебре и логике./Под ред.Ю. М. Горчакова.- Тверь: Тверской гос. университет, 1990. С.49−53.

14. Ключников А. В. Реализация конечных наборов простых экспериментов автоматами. М.: ВЦ АН СССР, 1991.