Содержание к диссертации
Введение
Глава 1. Синтез автоматов по наборам простых экспериментов
1.1. Основные понятия и результаты 11
1.2. Доказательство верхней оценки функции Шеннона 15
1.3. Доказательство нижней оценки функции Шеннона 23
1.4. Доказательство теорем 1.2 и 1.4 46
1.5. Доказательство теоремы 1.3 59
Глава 2. Синтез автоматов по наборам кратных экспериментов. Синтез акцепторов по конечным событиям
2.1. Основные понятия и результаты 61
2.2. Доказательство теоремы 2.1 65
2.3. Доказательство теоремы 2.2 69
2.4. Доказательство теорем 2.3 и 2.4 73
Глава 3. Алгоритмы синтеза автоматов
3.1. Синтез автономного автомата по набору ПЭ 78
3.2. Синтез автомата Мура по набору ПЭ.
Синтез автомата Мура по набору ЦЭ 80
3.3. Синтез автомата по набору КЗ. .87
3.4. Синтез акцептора по конечному событию 90
Литература 92
Работы автора по теме диссертации 93
Приложение. Программы, реализующие алгоритмы синтеза 94
- Доказательство верхней оценки функции Шеннона
- Доказательство теоремы 2.1
- Синтез автономного автомата по набору ПЭ
Введение к работе
Настоящая работа посвящена одному из важных разделов теории синтеза управляющих систем - задаче синтеза автоматов по заданной информации об их внешнем поведении. Такая задача возникает, например, когда требуется синтезировать управляющее устройство (УУ) последовательностного типа, определенным образом реагирующее на различные последовательности входных сигналов. В работе под информацией о внешнем поведении автоматов понимаются конечные наборы экспериментов, т.е. множества вход-выходных слов.
Основы теории экспериментов с автоматами заложены в работе Мура EI], где рассматривалась задача расшифровки "черного ящика", ставшая классической в теории автоматов. Эта задача состоит в восстановлении автомата - "черного ящика" по результатам проведенных с ним экспериментов. (См. также [2 - 9].) В дальнейшем она развивалась и изучалась, в частности, в рамках исследований, связанных с проблемами контроля и диагностики управляющих устройств. Обширную библиографию по этой теме можно найти в книге [23, откуда, кроме того, почерпнута терминология и основные определения, используемые в данной диссертации. Оказалось, что по конечному множеству экспериментов однозначное восстановление автомата невозможно.
В работах [6,7] исследовалась задача восстановления автомата при растущем (потенциально бесконечном) объеме информации о его внешнем поведении. Оказалось, что в этом случае возможно правильное восстановление "почти всех" автоматов. В ряде работ (см., например, Е83) информация о поведении автоматов включала в себя множества "допустимых" и "недопустимых" экспериментов.
При этом рассматривались задачи контроля и диагностики, то есть распознавания принадлежности автоматов к некоторым классам.
При всех этих подходах однозначное восстановление автомата, вообще говоря, невозможно. В работе [93 было введено важное понятие неизОъточности автомата относительно реализации им данного конечного множества экспериментов. Количество неизбыточных относительно реализации данного множества экспериментов автоматов конечно; были исследованы условия, при которых существует единственный неизбыточный автомат.
В отличие от описанных выше задач, в данной работе не исследуются вопросы, связанные с однозначностью восстановления автоматов или с распознаванием автоматов по данному множеству экспериментов. Синтезируемые автоматы рассматриваются здесь как управляющие устройства, и основное внимание при этом, в соответствии с ЕЮ], уделяется оценкам их сложности.
Как известно (см., например, [21,0.5-6, или [4]) существуют различные способы задания и изучения конечных автоматов. Один из них - абстрактная (поведенческая) теория автоматов, в которой поведение автомата, т.е. его реакции на входные сигналы, изучается в отрыве от его внутренней структуры. Автоматы при этом могут быть заданы в виде диаграмм переходов или таблиц переходов ([21,0.15-16, также Ш,[31), однозначно определяющих реакцию автоматов на всевозможные входные слова. Этот подход и принят в данной работе. При этом под сложностью автомата естественно понимать число его состояний.
В работе рассмотрено два вида множеств экспериментов, описывающих поведение автомата.
В первом случае информация о поведении автомата представлена в виде набора простых экспериментов, то есть набора вход- выходных слов, не связанных друг с другом. При этом требуется синтезировать неинициальный автомат, который для каждого из данных экспериментов имеет такое состояние, что, начиная работу в этом состоянии и получая на входе данное входное слово, автомат выдает данное выходное слово. Эта задача может возникнуть при синтезе УУ, если возможны различные внешние ситуации, в каждой из которых последовательность входных сигналов однозначно определена и требует соответствующего "отклика" УУ, причем существует возможность заранее "настроить" УУ на данную ситуацию, то есть привести его в соответствующее начальное состояние.
Такая же задача возникает при восстановлении абстрактного автомата по результатам экспериментов с различными экземплярами одного и того же автомата. Если автомат не имеет "кнопки возврата", позволяющей в любой момент привести его в исходное состояние, а имеющиеся его экземпляры изначально могут находиться в различных состояниях, то в результате проведения экспериментов мы получим набор вход-выходных слов.
Кроме того, алгоритм синтеза автомата по набору простых экспериментов может иметь следующее приложение. Предположим, в памяти компьютера необходимо хранить набор слов. Обычно набор слов хранится в виде двух одномерных массивов - массива символов и массива адресов начал слов в первом массиве. Если интерпретировать исходный набор слов как набор выходных слов некоторого автомата, то алгоритм синтеза минимального автономного автомата, приведенный в 3.1 диссертации (с некоторыми незначительными изменениями), может позволить иногда уменьшить объем памяти, необходимой для хранения этой информации, без существенного усложнения ее считывания.
Во втором случае информация о поведении автомата представлена в виде набора кратных экспериментов. Как известно ([23, С.63), кратные эксперименты возникают при возможности одновременной подачи различных входных слов на различные экземпляры одного и того же автомата (находящиеся изначально в одинаковых состояниях), или же при наличии у автомата "кнопки возврата", позволяющей вернуть его в исходное состояние после подачи любого слова. С точки зрения задачи синтеза УУ, возможна иная интерпретация. Процесс, требующий управления, может быть недетерминированным, и, следовательно, на вход УУ могут поступать различные последовательности входных сигналов. Цель управления заключается в том, чтобы на любую из них УУ реагировало соответствующим образом. Ясно, что это соответствие может быть задано кратным экспериментом.
Так же, как и в первом случае, при возможности предварительной "настройки" УУ на различные внешние ситуации возникает задача синтеза автомата по набору нескольких кратных экспериментов.
Отдельно рассмотрен случай наборов полных кратных экспериментов, задающих требуемое поведение синтезируемого автомата для всех входных слов определенной длины. С практической точки зрения такая ситуация выглядит вполне правдоподобной.
В работе исследована еще одна задача, связанная с другой точкой зрения на поведение автоматов. Автомат может быть использован как акцептор, то есть устройство, распознающее входные слова. Поступление на вход автомата слова из некоторого множества вызывает особую внешнюю реакцию автомата (выделенный выходной символ). В работе исследован случай конечных событий (выделенных множеств входных слов). Задача синтеза акцептора, распознающего данное конечное множество входных слов, сходна с задачей синтеза автомата по одному кратному эксперименту, однако не эквивалентна ей, так как дополнительное множество (множество слов, "отвергаемых" автоматом) бесконечно.
Основное внимание уделялось оценкам сложности (числа состояний) синтезируемых автоматов в зависимости от параметров заданных наборов экспериментов. Под сложностью реализации данного набора экспериментов понимается минимальное число состояний, которое может иметь автомат, синтезируемый по этому набору. При этом для каждой из рассотренных задач получены оценки как функции Шеннона, характеризующей максимальную сложность реализации наборов с данными параметрами, так и "типичных" значений сложности реализации наборов экспериментов с данными параметрами.
Разработаны также достаточно простые (полиномиальной сложности) алгоритмы синтеза автоматов для различных случаев, гарантирующие построение автоматов с числом состояний, близким к минимальному. Глава I посвящена синтезу автоматов по наборам простых экспериментов, глава 2 - синтезу по наборам кратных экспериментов и синтезу акцепторов, представляющих конечные события. В главе 3 изложены разработанные алгоритмы синтеза.
В диссертации получены следующие результаты. Пусть з и t обозначают, соответственно, мощности входного и выходного алфавитов; s ^ 2, t ^ 2; алфавиты считаются фиксированными.
Простые эксперименты
Для наборов ш простых экспериментов, длина каждого из которых не превосходит п, получена асимптотически точная оценка функции Шеннона L(m,n,s,t) (точные определения даны в 1.1). А ИМЄННО: при m t выполнено L(m,n,a,t) = t ; n при m < t , и при n * да выполнено { [w(m,n,t)] , w(m,n,t) > 0 [t'W(m,n,t)], w(m,n,t) ^ 0, Elog+rn] - (Elogtm3 - n) где to(m,n,t) = t * - m»— t - 1
Фактически в 1.1 получены верхняя и нижняя оценки функции
Шеннона, дающие асимптотическую точность. В частном случае п - оо, ш = o(t ) асимптотическая оценка функции Шеннона упрощается и принимает вид L(m,n,s,t) ^ m>(n - log+m).
Получена асимптотически точная оценка типичных значений числа состояний синтезируемого автомата. А именно, при п - оо, log(m) = о(п) для почти всех наборов m простых экспериментов, длина каадого из которых не превосходит п, минимальное число состояний L синтезируемого по данному набору автомата удовлетворяет соотношению ^ пьп (s-1)iogt(m-n)
Разработан алгоритм синтеза, для почти всех наборов гарантирующий эту оценку (описан в 3.2). Этот алгоритм применим также для синтеза автомата по набору циклических экспериментов. Точное определение циклического эксперимента содержится в 1.1,-неформально говоря, это бесконечный периодический простой эксперимент. Если под длиной циклического эксперимента понимать сумму длин предпериода и периода, то алгоритм синтеза для почти всех наборов циклических экспериментов гарантирует ту же верхнюю оценку сложности синтезируемого автомата.
Кратные эксперименты
Для наборов кратных экспериментов (КЭ) получена оценка функции Шеннона по порядку величины. Пусть m - количество КЭ в наборе, an- максимальная длина составлящих их простых эк спериментов (точные определения даны в 2.1). Кратный экспери мент называется полным кратным экспериментом (ПКЭ) глубины п, если все составлящие его простые эксперименты имеют длину п и они содержат все sn входных слов длины п. Через D(n) обозначим количество различных ПКЭ глубины п; очевидно, истинно равенство (п+1) D(n) = t Через RP(U,m,n) обозначим класс всех наборов различных ПКЭ глубины п над U; этот класс не пуст при m ^ D(n).
Для функции Шеннона LKp(m,n,s,t) получены следующие оценки: при п -» оо, ш ^D(n) выполняются соотношения п (п+3) m's < LKpdn.n.B.t) < m's
8-1)'logt(m*sn) ~ ~ (s-1)2*logt(m«sn) при n - со, log(m) = o(s ) выполняется (n+1) LKp(m,n,s,t) > 1^ ; (s-1)2.logt(m.sn) при m ^ D(n) выполнено LKp(m,n,3,t) = D(n).
Для- типичных значений сложности реализации наборов ПКЭ из класса RF(U,m,n) получены следующие оценки: при п -* « для почти всех R є KF(U,m,n) выполнено соотношение L(R) > (s-1).iogt(m.sn) а при n -» oo , log(m) = o(sn) для почти всех R e RF(U,m,n) выполнено соотношение (n+1) L(H) > ^ , (8-1)2-logt(ffl.Sn) то есть типичные значения по порядку величины совпадают с функцией Шеннона. Алгоритм синтеза, гарантирующий верхнюю оценку, и, следовательно, по порядку наилучший, приведен в 3.3.
Автоматы как акцепторы
Пусть в выделенном конечном событии (множестве входных слов) максимальная длина слова равна п. Для функции Шеннона La(n,s) получены следующие оценки: при п + с» выполняется (п+1) (п+з) s < La(n.s) < 3 n*(s-1)2>iog2(s) ~ ~ n«(s-1)2*iog2(s) причем для почти всех событий минимальное число состояний синтезируемого автомата асимптотически не меньше приведенной нижней оценки. Алгоритм синтеза, гарантирующий верхнюю оценку, и, следовательно, по порядку наилучший, приведен в 3.4.
Автор выражает глубокую благодарность своему научному руководителю В.А.Буевичу, а также профессору В.Б.Кудрявцеву и доценту О.В.Алешину за постановку задач, замечания, советы и обсуждение работы.
Доказательство верхней оценки функции Шеннона
Будем говорить, что автономный автомат А генерирует слово р е Y из состояния q, если g(q, if)! ) = р. Соответственно, А генерирует набор виходиш: слов В, если он генерирует (вообще говоря, из различных состояний) все слова набора В. Ясно, что автономный автомат реализует из состояния q простой эксперимент е - (а,р) в смысле определения из 1.1 тогда и только тогда, когда он генерирует из состояния q слово р. Следовательно, автономный автомат реализует набор простых экспериментов Р е P(U) тогда и только тогда, когда он генерирует набор выходных слов В(Р), сопоставленный набору Р. Кроме того, любой набор выходных слов может быть сопоставлен некоторому набору простых экспериментов. Поэтому для оценки функции Шеннона LA(m,n,t) достаточно рассматривать полные (т,п)-наборы выходных слов и генерирующие их автономные автоматы.
Доказательство теоремы 2.1
Автомат A(n) є K(U) будем называть п-униЗерсалъкыж, если он реализует любой ПКЭ глубины п (и следовательно, любой КЭ глубины, не превосходящей п).
Выполняются следующие утверждения.
Лемма 2.1. Автомат реализует из состояния q данный КЭ г глубины п тогда и только тогда, когда для любого входного слова а, !а! п, он реализует подэксперимент г(а) из состояния i(qfa) (при а = Л полагаем f(q,A) = q ).
Лемма 2.2. Если автомат реализует данный КЭ г глубины п, то при любом k п он реализует из того же состояния префикс г/к .
Лемма 2.3. При любом натуральном п существует п-уни-версальный автомат A(n)K(U), имеющий D(n) состояний.
Лемма 2.4. При любых натуральных m,n и при любом нату ральном к е 1 п для любого набора КЭ R R(U,m,n) вы полняется неравенство
Леммы 2.1,2.2 очевидны. Леммы 2.3 и 2.4 доказаны в 3.3, где описан синтез п-универсалъного автомата и синтез автомата по данному набору КЭ, удовлетворяющего приведенной оценке.
Синтез автономного автомата по набору ПЭ
На первом этапе среди всех суффиксов слов набора В выделяются суффиксы 1-го рода. Дня этого следует занумеровать все суффиксы в порядке убывания их длин (порядок суффиксов одинаковой длины несуществен, важно лишь, чтобы более длинные предшествовали более коротким). По определению (см.1.2),суффикс называется суффиксом 1-го рода (набора В), если он префиксно различим с любым предшествующим ему (относительно заданного порядка) суффиксом, и суффиксом 2-го рода - в противном случае. Заметим, что, согласно этому определению, свойство суффикса быть суффиксом 1-го (2-го) рода данного набора может зависеть от выбранной нумерации в случае присутствия в наборе двух одинаковых суффиксов, префиксно различимых со всеми более длинными суффиксами. При этом один из них (получивший меньший номер) будет суффиксом 1-го, а другой - 2-го рода. Впрочем, из изложенного ниже алгоритма ясно, что это не играет никакой роли.
На втором этапе всем суффиксам всех слов набора В ставятся в соответствие состояния синтезируемого автомата, причем различным суффиксам 1-го рода ставятся в соответствие различные состояния. Суффиксам же 2-го рода состояния автомата ставятся в соответствие следующим образом - каждому суффиксу 2-го рода ставится в соответствие состояние, соответствующее суффиксу 1-го рода, префиксно неразличимому с ним (такой суффикс существует в силу леммы 1.4).
Таким образом, любому суффиксу 2-го рода b b ...Ь (±) поставлено в соответствие то же состояние автомата, что и некоторому суффиксу 1-го рода большей или равной длины, префикс которого равен b b ...b . В принципе, данный суффикс 2-го рода может совпадать с префиксом более чем одного суффикса 1-го рода. В таком случае можно выбрать любой из них. Можно доказать, что при различном выборе будут синтезированы неизоморфные минимальные автоматы.
Функции переходов и выходов 1 и g синтезируемого автомата определяются следующим образом. Пусть состояние q соответствует суффиксу 1-го рода bib .. -b (1) , а суффиксу )j+i ,j+2 l)n(i) (1-го или 2-го рода) поставлено в соответствие состояние q . Положим g(q) = b , r(q) = q . В случае З = n(i) (если последняя буква слова р1 является суффиксом 1-го рода) переход f(q) можно определить произвольным образом. Опять же можно показать, что при различном выборе будут синтезированы неизоморфные автоматы.
