Лекции по теории экспериментов с конечными автоматами

Теория экспериментов с конечными автоматами

2-е издание, исправленное

Cперанский Д.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 519.713(076.6)
ББК 8
С71
Лекции по теории экспериментов с конечными автоматами / Сперанский Д.В. - M.: Национальный
Открытый Университет “ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 978-5-9963-0268-0

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

(c) ООО “ИНТУИТ.РУ”, 2010-2016
(c) Cперанский Д.В., 2010-2016

3

Эксперименты с автоматами, имеющими взвешенный входной
алфавит

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

Основные определения

Введем некоторые основные понятия теории автоматов, которые используются в
дальнейшем изложении.

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

Через 
 обозначим подмножество множества состояний 
, которое назовем

множеством допустимых начальных состояний автомата 
.

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

называются конечными).

Через 
 обозначим множество всех последовательностей (слов) конечной длины в

алфавите 
. Через  обозначим пустое слово (нулевой длины) в любом алфавите.

Полагаем, что 
. Распространим функции переходов и выходов автомата на

множество 
 следующим образом:

где 
. Последовательность выходов автомата 

получена с помощью операции конкатенации (приписывания) двух слов: 
 и 

.

Автомат Мили 
 может быть задан в виде таблиц переходов и выходов (иногда они

совмещаются в одну таблицу), с помощью матриц и, наконец, с помощью графа.
Форма представления автомата в виде графа является наиболее наглядной. В
дальнейшем изложении мы будем пользоваться в основном графовой и табличной
формами представления автомата, которые подробно описаны в [18]. Напомним, что
множеством вершин графа переходов автомата 
 являются состояния из 
, а

множество дуг есть совокупность четверок 
, где 
. Пара 

 называется отметкой дуги,  - ее началом,  - концом.

Пусть 
, тогда полагаем, что 
 и 
, где

объединение выполняется по всем 
.

4

Состояние  назовем достижимым из , если 
 для некоторого 
.

Автомат 
 назовем сильно связным, если его граф переходов сильно связен, т. е. из

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

не достижимо ни из одного состояния, отличного от . Состояние  называется
тупиковым в автомате 
, если из  не достижимо ни одно состояние, отличное от .

Каждому входному символу 
 из алфавита 
 автомата 
 поставим в соответствие

некоторое положительное число 
 и назовем его весом символа 
. Далее такой

алфавит будем называть взвешенным. Весом входной последовательности

 назовем число

Следуя традиции классической теории экспериментов с автоматами, будем различать
безусловные и условные эксперименты [18]. Безусловный эксперимент предполагает
подачу на вход автомата такой последовательности, которая определена заранее, т. е.
до начала эксперимента. При проведении условного эксперимента на вход автомата
подается две или более подпоследовательности, причем каждая последующая
подпоследовательность, кроме первой, формируется на основании реакций,
вызываемых предыдущими подпоследовательностями.

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

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

В дальнейшем изложении мы в основном будем иметь дело с простыми безусловными
экспериментами.

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

 его допустимых начальных состояний, т. е. истинное начальное (стартовое)

состояние. Это состояние есть одно из состояний множества 
. Диагностическая

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

Проведение установочных и диагностических экспериментов с автоматами требует

5

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

Дадим теперь формальные определения этих последовательностей. Входная
последовательность 
 называется установочной последовательностью

для автомата 
 и множества 
 его допустимых начальных состояний, если

(1.1)

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

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

Входная последовательность 
 называется диагностической

последовательностью для автомата 
 и множества 
 его допустимых начальных

состояний, если

(1.2)

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

всегда однозначно можно определить это начальное (стартовое) состояние.

Определим еще один тип последовательности, которую назовем синхронизирующей
(СП). Входная последовательность 
 называется синхронизирующей

последовательностью для автомата 
 и множества 
 его допустимых начальных

состояний, если

(1.3)

Содержательно это определение означает, что после подачи на автомат 
 СП этот

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

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

Ниже мы займемся разработкой методов построения СП, УП и ДП в предположении,
что автомат 
 имеет взвешенный входной алфавит 
. При этом нас будут

интересовать все три типа последовательностей с минимальным весом. Как уже было
упомянуто выше, известные ранее методы построения минимальных по длине
последовательностей, описанные в [18], в рассматриваемой ситуации оказываются
непригодными. Вместе с тем базисная конструкция дерева преемников,
использованная в [18] для синтеза УП и ДП, минимальных по длине, оказывается

6

вполне работоспособной и в нашем случае, однако она, что вполне естественно,
требует соответствующих изменений.

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

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

Заметим, что в этой лекции мы не касаемся вопросов существования упомянутых выше
трех типов последовательностей, поскольку для автоматов Мили они подробно
отражены в [18]. Легко сообразить, что “взвешенность” алфавита никак не влияет на
условия существования соответствующих последовательностей.

Синтез синхронизирующих последовательностей, минимальных по
весу

В основе построения СП, УП и ДП, минимальных по весу, лежит так называемое
дерево преемников, формируемое для автомата 
 и множества 
 его допустимых

начальных состояний. Оно незначительно отличается от аналогичной структуры,
определенной в [18]. Остановимся на способе его построения.

Под  -множеством автомата 
 понимается любая конечная совокупность состояний 

, не все из которых обязательно различны. Если  -множество содержит один

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

Назовем 
 -группой множество, состоящее из  -множеств, общее число элементов

которых равно 
. 
 -группа называется простой (однородной), если все  
множества в ней просты (однородны).

Пусть 
 есть 
 -группа, состоящая из -множеств 
 
преемник 
 есть другая 
-группа, построенная по следующим правилам:

1. 
 -множество 
 разбиваем на такие подмножества, каждое из которых

содержит все те состояния из 
, которые вырабатывают одинаковую реакцию на

входную последовательность 
. Каждое полученное подмножество

далее интерпретируется как  -множество, а совокупность всех таких
подмножеств интерпретируется как 
 -группа 
.

2. В  -множествах из 
 заменяем каждое состояние его преемником относительно

входной последовательности 
.

Получаемая в результате такого построения 
 -группа является 

преемником 
.

7

Определим теперь структуру, называемую деревом преемников для заданного автомата

 и множества допустимых начальных состояний 
. Она состоит из ветвей,

расположенных в последовательных уровнях, нумерация которых начинается с нуля.
Нулевой уровень дерева содержит единственную, называемую начальной, ветвь.
Условимся считать, что она связана с 
 -группой 
. Если входной алфавит 

 автомата 
 содержит  символов, то каждая ветвь в -м уровне 

 расщепляется на  ветвей, представляющих символы 

соответственно и являющихся ветвями 
 -го уровня. Ветвь 
 
 -го уровня

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

Из описанного метода построения вытекает, что дерево преемников является
бесконечной структурой. Для синтеза СП, УП и ДП нами будут из упомянутой
бесконечной структуры выделяться конечные деревья за счет введения специальных
правил обрыва ветвей. Каждая такая оборванная ветвь связана с вершиной дерева,
которую мы будем называть листом, следуя терминологии, принятой в теории графов.

Для построения минимальной по весу СП используем граф, который назовем
синхронизирующим деревом (СД). Основой для его построения является описанное
выше дерево преемников.

Вершинами СД являются 
 -группы дерева преемников. Корень СД представляет

собой 
 -группу 
 нулевого уровня. Вершиной 1-го уровня СД, связанной с 
 
ветвью, является 
 -группа 
, представляющая собой 
 -преемник 
 -группы 
,

при этом из вершины 
 в 
 проводится дуга, помеченная символом 
. Аналогично

строятся вершины СД всех последующих уровней и соединяющие их дуги. Каждой
вершине 
 в СД поставим в соответствие флажок (на рисунках он будет обозначаться

прямоугольником), в него будет вписано число, равное сумме весов входных символов
последовательности, которая соответствует пути по СД, ведущему из корня в вершину 

.

Условимся теперь об обозначениях вершин СД. Если вершине 
 СД соответствует 
 
группа 
, где 
 -  -множества, то для ее обозначения будем

использовать множество состояний автомата 
, равное

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

При построении СД автомата 
 с множеством 
 допустимых начальных состояний

вершина 
  -го уровня становится листом, если выполняется хотя бы одно из

следующих условий:

8

1. 
 ;

2. на уровнях, предшествующих  -му, имеется такая вершина 
, что 
, но

значение флажка вершины 
 больше значения флажка вершины 
 ;

3. на уровнях, предшествующих  -му, имеется такая вершина 
, что 
, а

значение флажка вершины 
 больше значения флажка вершины 
.

Проиллюстрируем процесс построения СД для автомата, заданного табл. 1.1, считая,
что 
. Этот граф приведен на рис. 1.1. В овале,

изображающем вершину, перечислены состояния множества, соответствующего этой
вершине.

Таблица 1.1.
Переходы
выходы
автомата

s\x
1
1/0 1/1 5/0

2
3/1 2/0 4/0

3
2/1 4/1 4/0

4
5/1 1/1 5/1

5
3/0 2/0 4/1

Так, вершина 
 первого уровня, две вершины 
 второго уровня, вершины 

 и 
 третьего уровня и т. д. являются листьями в силу пункта 2 правил

обрыва. Вершины 
 и 
 пятого уровня, вершина 
 третьего уровня являются

листьями в силу пункта 1 правил обрыва. Две вершины 
 четвертого уровня,

имеющие значение флажка 43, являются листьями в силу пункта 3 тех же правил.

Из способа построения СД вытекает, что последовательность входных символов,
соответствующая пути по СД из корня в одну из вершин 
, где 
, является СП

для заданного автомата.

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

минимальным значением флажка 
 и в СД находится путь в нее из корня дерева.

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

Так, в СД на рис1.1 имеется 4 таких вершины, из которых вершина 
 пятого уровня

имеет минимальное значение флажка, равное 27.

Поскольку пути из корня в эту вершину соответствует входная последовательность 

, то она и является минимальной по весу СП. Заметим, кстати, что минимальной

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

вершину 
 третьего уровня.

9

Приведенный пример показывает, что в общем случае СП для автомата может быть
минимальной по весу, но не являться минимальной по длине.

Рис. 1.1.  Синхронизирующее дерево

Синтез установочных последовательностей, минимальных по весу

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

точкой с запятой.

УД строится точно так же, как СД, а правила, по которым вершина 
  -го уровня

дерева преемников становится листом, таковы:

1. она является однородной;
2. она является простой;
3. на уровнях, предшествующих  -му, имеется такая вершина 
, что 
, но

значение флажка вершины 
 больше значения флажка вершины 
 ;

4. на уровнях, предшествующих  -му, имеется однородная или простая вершина 

, значение флажка которой меньше значения флажка вершины 
.

Заметим, что для превращения вершины 
 в лист достаточно выполнения одного из

четырех перечисленных пунктов.

Прокомментируем эти правила. Пункт 3 правил означает, что в УД уже имеется более
“легкий” по весу отрезок пути, приводящий к некоторой 
 -группе, чем путь,

приведший к вершине 
 с точно такой же 
 -группой. Понятно, что при продолжении

построения УД из вершины 
 принципиально возможно построить некоторую УП, но

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

10