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

• Автор: Ключников, А. В.
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1993
• Место защиты: Москва
• Количество страниц: 140 с. : ил.

Содержание
Введение
Глава I. Синтез автоматов по наборам простых экспериментов
§ 1.1. Основные понятия и результаты
§ 1.2. Доказательство верхней оценки функции Шеннона
§ 1.3. Доказательство нижней оценки функции Шеннона
§ 1.4. Доказательство теорем 1.2 и
§ 1.5. Доказательство теоремы
Глава 2. Синтез автоматов по наборам кратных экспериментов. Синтез акцепторов по конечным событиям
§ 2.1. Основные понятия и результаты
§ 2.2. Доказательство теоремы
§2.3. Доказательство теоремы
§ 2.4. Доказательство теорем 2.3 и
Глава 3. Алгоритмы синтеза автоматов
§3.1. Синтез автономного автомата по набору
§ 3.2. Синтез автомата Мура по набору ПЭ.
Синтез автомата Мура по набору ЦЭ
§ 3.3. Синтез автомата по набору КЭ
§ 3.4. Синтез акцептора по конечному событию
Литература
Работы автора по теме диссертации
Приложение. Программы, реализующие алгоритмы синтеза

Введение.
Настоящая работа посвящена одному из важных разделов теории синтеза управляющих систем - задаче синтеза автоматов по заданной информации об их внешнем поведении. Такая задача возникает, например, когда требуется синтезировать управляющее устройство (УУ) последовательностного типа, определенным образом реагирующее на различные последовательности входных сигналов. В работе под информацией о внешнем поведении автоматов понимаются конечные наборы экспериментов, т.в. множества вход-выходных слов.
Основы теории экспериментов с автоматами заложены в работе Мура [I], где рассматривалась задача расшифровки "черного ящика", ставшая классической в теории автоматов. Эта задача состоит в восстановлении автомата - "черного ящика" по результатам проведенных с ним экспериментов. (См. также [2 - 91.) В дальнейшем она развивалась и изучалась, в частности, в рамках исследований, связанных с проблемами контроля и диагностики управляющих устройств. Обширную библиографию по этой теме можно найти в книге [23, откуда, кроме того, почерпнута терминология и основные определения, используемые в данной диссертации. Оказалось, что по конечному множеству экспериментов однозначное восстановление автомата невозможно.
В работах [6,73 исследовалась задача восстановления автомата при растущем (потенциально бесконечном) объеме информации о его внешнем поведении. Оказалось, что в этом случае возможно правильное восстановление "почти всех" автоматов. В ряде работ (см., например, [83) информация о поведении автоматов включала в себя множества "допустимых" и "недопустимых" экспериментов.

При этом рассматривались задачи контроля и диагностики, то есть распознавания принадлежности автоматов к некоторым классам.
При всех этих подходах однозначное восстановление автомата, вообще говоря, невозможно. В работе [9] было введено важное понятие неиздыточности автомата относительно реализации им данного конечного множества экспериментов. Количество неизбыточных относительно реализации данного множества экспериментов автоматов конечно; были исследованы условия, при которых существует единственный неизбыточный автомат.
В отличив от описанных выше задач, в данной работе не исследуются вопросы, связанные с однозначностью восстановления автоматов или с распознаванием автоматов по данному множеству экспериментов. Синтезируемые автоматы рассматриваются здесь как управляющие устройства, и основное внимание при этом, в соответствии с СЮ], уделяется оценкам их сложности.
Как известно (см., например, С23,С.5-6, или С43) существуют различные способы задания и изучения конечных автоматов.
Один из них - абстрактная (поведенческая) теория автоматов, в которой поведение автомата, т.е. его реакции на входные сигналы, изучается в отрыве от его внутренней структуры. Автоматы при этом могут быть заданы в виде диаграмм переходов или таблиц переходов (С23,С.15-1б, также Ш.СЗЗ), однозначно определяющих реакцию автоматов на всевозможные входные слова. Этот подход и принят в данной работе. При этом под сложностью автомата естественно понимать число его состояний.
В работе рассмотрено два вида множеств экспериментов, описывающих поведение автомата.
В первом случае информация о поведении автомата представлена в виде набора простых экспериментов, то есть набора вход-

3{<і) > ае*сі - шіп(к+1,7).
После удаления всех слов вида (1.10) удаляются слова вида (1.9). Эти слова удаляются в порядке возрастания 1, при каждом значении 1 - в порядке возрастания 3, при фиксированных 1 и 1 - в порядке 2 = уг,у3
(к-1*7-3-р) р
При фиксированном (3 € ¥ удаление всех 1 слов
приводит к тому, что
вида у2...Ур У
V ,£-у г.З У 1 Ь У ;
(1-1) ±'1+3 р
во всех словах вида
у ...у Уо -Уо У
у —ЬУи2111у..у—и у, у.
(1-1) и 1*1+3 (р-и)
где и € 11,2
буквы, становятся суффиксами 1-го рода. Следовательно, при удалении в алфавитном порядке с! слов [1 б И) количество появившихся суффиксов 1-го рода Б(б) удовлетворяет равенству
б 1 Г б 1 Г (і
1 + I2 + . + . г(ї-1)
Э(б)
Легко видеть, что:
(к-Ы-3)
а) при 0 б < X выполнено Б (б) > ае*б - (7-1);
(к-7 *1-3)
б) при 6=1 и (к-1*7-3) > (7-1) выполнено
Б (б) = ае-б.
Следовательно, при переходе от слов указанного вида с одними значениями параметров 1,3 и г к словам с другими значениями этих параметров, "накопления погрешности" не происходит,