О синтезе автоматов по конечным фрагментам их поведения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

механико-математическРй факультет

! ' -< ('.1

На правах рукописи "■'■••' УДК 519.713/.714

КЛЮЧНИКОВ Александр Валерьевич

О СИНТЕЗЕ АВТОМАТОВ ПО КОНЕтШШ ФРАГМЕНТАМ ИХ ПОВЕДЕНИЯ

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1993

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. М.В. Ломоносова

Научный руководитель: доктор физико-математических наук,

вед.н.с. В.А.Буевич. Официальные оппоненты: доктор физико-математических наук,

доцент С.Б.Гашков; кандидат физико-математических наук, доцент Э.А.Применко. Ведущая организация - Московский энергетический институт,

кафедра математического моделирования.

Защита диссертации состоится _" м&^а 199$т.

в |^час. 08? мин. на заседании специализированного Совета № 4 (Д.053.05.38) по математике при Московском государственном университете по адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, факультет ВМиК, зуд. 685.

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

Автореферат разослан " ^ " 199^ г.

Ученый секретарь специализированного Совета & 4

(.Д.053.05.38) при МГУ профессор Н.П.Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Р 1

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

1' Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. - в кн.Автоматы. - М.: ИЛ, 1956, G.179-210.

2) Яблонский C.B. О построении тупиковых кратных экспериментов для автоматов - Труды Математического института АН СССР, М.: изд-во АН СССР, 1973, т.133, С.263-272.

щих кратных экспериментов.

Обширную библиографию по этой теме можно найти в книге3 5, откуда, кроме того, почерпнута терминология и основше определения, используемые в данной диссертации.

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

-В работе51 исследовалась задача восстановления автомата при растущем ^потенциально бесконечном) объеме информации о его внешнем поведении. Оказалось, что в этом случае возможно правильное восстановление "почти всех" автоматов. В ряде работ' (например, б); информация о поведении автоматов включала в себя

. ч ,

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

При всех этих подходах однозначное восстановление автома-

Кудрявцев В.В., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. - М.: Наука, 1985.

Д) Лупанов O.E. О сравнении двух типов конечных источников. -В сб. Проблемы кибернетики. - М.: Физматгиз, I9G3, вып.9. 0.32I-32G.

й' Парздинь Я.М. О расшифровке автоматов при отсутствии верхней оценки числа состояний//ДАН СССР - 1970.- ТЛЭО.Лб, C.I048-I05I

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

Т.25, т.

7 1

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

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

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

Пусть X и У - соответственно, входной и выходной алфавиты,

7 1

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

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

95 Кудрявцев В.В., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. — М.: Наука, 1985. - С.5-6; 15-16.

мока.юти которых равны, соответственно, них. Алфавит и = Х*У всюду ниже считается фиксированным. Через К(Т1) обозначим класс всех конечных детерминированных автоматов Мили с входным алфавитом X и выходным алфавитом У, пятерок вида (Х,0,УД,8), где и - ,... - множество состояний автомата, I: 0*Х -> О - функция переходов, g: СЬХ - У - функция выходов.

Обычным образом, согласно10', можно определить словарную функцию СЬХ* У*, задающую соответствие вхо"""^: т» входных слов.

Число состояний автомата А будем обозначать Ъ(А).

Проемы, эксперта то.,и (ПЭ) длины п над и называется пара е = 1а,р), асХп, реУп. (т,п)-набором простых экспериментов над и называется набор Р = (е1,...,еш) не обязательно различных ПЭ над и, максимум длин которых равен п. В дальнейшем для краткости слова "простых экспериментов над И" будут опускаться.

Множество всех чш,п)-наборов обозначим Р(и,т,п), а через Р(II) обозначим объединения всех, тожеств Р(и,ш,п) по всем натуральным ш и п.

Будем говорить, что автомат А из К(II) реализует данный ПЭ е = (а,р) из состояния я, если = р. Соответственно,

автомат А реализует набор Р е ГШ), если он реализует ^вообще говоря, из различных состояний) каждый эксперимент набора Р. Для любого набора Р с Р(Ч) существует бесконечно много автоматов из К(11), реализующих Р. Под сложностью реализации набора р в классе К(И) понимается величина

1<Э) Там же, С.17.

L(P) = min { L(A) I AeK(U), А реализует P }.

Автомат, реализующий данный набор ПЭ Р, естественно назвать шнитльиым относительно Р, если он имеет число состояний, равное Ъ(Р). Заметим, что задача синтеза минимального автомата тривиально решается переборным алгоритмом.

Введем в рассмотрение функцию Шеннона - величину, характеризующую максимальную сложность реализации автоматами наборов ПЭ с данными параметрами -

L(m,n,G,t) = шах i L(P) | PeP(U,m,n) >-

Другим видом информации о внешнем поведении автомата могут быть кратные эксперименты^ ) (КЭ). Аналогичным образом можно определить понятия реализации КЭ автоматом, реализации автоматом (вообще говоря, из различных состояний) набора КЭ, сложности реализации данного набора КЭ, и ввести функцию Шеннона LKp(m,n,s,t). Отдельно рассмотрен случай наборов полных кратных экспериментов (ПКЭ), т.е. кратных экспериментов, полностью определяющих функционирование автомата при всех входных словах данной длины.

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

1. Получить асимптотические оценки функции Шеннона.

2. Получить асимптотические оценки сложности (числа состояний) автоматов для "почти всех" наборов экспериментов с данными параметрами.

11 ' Там же, С.63.

3. Описать "простые" алгоритмы, позволяющие синтезировать автоматы, сложность которых близка к минимальной.

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

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

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

Апробация диссертации. Результаты диссертации докладывались на 2-м и 3-м Всесоюзном семинаре по дискретной математике и ее приложениям, на Ломоносовских чтениях в МГУ, на Конференции выпускников мех.-мат. ф-та, на семинаре член-корр. РАН С.В.Яблонского "Математические вопросы кибернетики", на семинаре акад. АТН В.Б.Кудрявцева "Теория автоматов".

Структура и объем работы. Диссертация состоит из введения, трех глав и списка цитированной литературы (11 наименований). Общий объем диссертации 139 страниц.

Основные результаты диссертации опубликованы в работах автора П - 31, приведенных в конце автореферата. Работа носит

ь

теоретический характер. Полученные результаты могут применяться в теории автоматов и в теории синтеза управляющих систем.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

п п

Теорема 1.1 При ш ^ X выполнено Ь(т,п,зД) = г ;

п

при ли | п-»в выполнено

L(m,n,3,t) ^ ш-(n - [logtml)

+

[co(m,n,t)] , (d(m,n,t) > О [t-cj(m,n,t)], u(m,n,t) ^ О,

[log и] , - n)

где tiHm,n,t) = t г - m*—---- .

t - 1

Теорема 1.2 При n -> т , log(m) = о(п) для почти всех P£P(U,m,n) выполнено

" rn-n

Ь(Р)

(s-1)•logt(m-n)

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

Че-рез D(n) обозначим количество различных ПКЭ глубшш п над U; очевидно, истинно равенство щ+1 )

IH^r*)

D(n) = t

п i

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

Теорема 2 Л При п оо, ш ^ D(n) выполнены соотношения

п ' tn+3)

-^- < LKp(m.n.s.t) < -^-: ;

<s-1).logt(m-sn) ™ ~ (s-1)2.logt(m.sn)

n

при n oo, iog(m) = o(s ) выполняется

(n+1)

LKp(m,n,s,t) > - m's

(g~1)2.logt(m-sn)

при ш £ D(n) выполнено lKp(rn,n,s,t) = D(n).

Теорема 2.2 При n - оо для почти всех R e RP(U,ra,n)

L(R)

выполнено соотношение n

JJl'S

, - (3-1)-logt(m-sn)

n

а при п - со , iog(m) = о(з ) для почти всех R е RF(ü,m,n)

выполнено соотношение т+1)

L(R) > -^- .

is-1•logt(m>3n)

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

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

t

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ключников A.B. О сложности автоматов, реализующих конечные множества простых экспериментов // Труды семинара по дискретной математике и ее приложениям / Под ред. О.Б.Лупанова. - М.: Моск.Университет, 1989. - C.I95-20I.

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

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

Введение.

Глава I. Синтез автоматов по наборам простых экспериментов

§ I.I. Основные понятия и результаты.

§ 1.2. Доказательство верхней оценки функции Шеннона.

§ 1.3. Доказательство нижней оценки функции Шеннона.

§ 1.4. Доказательство теорем 1.2 и 1.4.

§ 1.5. Доказательство теоремы 1.

Глава 2. Синтез автоматов по наборам кратных экспериментов. Синтез акцепторов по конечным событиям

§ 2.1. Основные понятия и результаты.

§ 2.2. Доказательство теоремы 2.1.

§2.3. Доказательство теоремы 2.2.

§ 2.4. Доказательство теорем 2.3 и 2.4.

Глава 3. Алгоритмы синтеза автоматов

§ 3.1. Синтез автономного автомата по набору ПЭ.

§ 3.2. Синтез автомата Мура по набору ПЭ.

Синтез автомата Мура по набору ЦЭ.

§3.3. Синтез автомата по набору КЗ.

§3.4. Синтез акцептора по конечному событию.

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

Основы теории экспериментов с автоматами заложены в работе Мура [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(R) > n m«s s-1 ).iogt(m.sn) а при n oo , log(m) = o(sn) для почти всех R e RP(U,m,n)

L(R) > вшолнено соотношение (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.