ФИЛИАЛ МГУ имени М. В.

ЛОМОНОСОВА в городе БАКУ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ
РАБОТА БАКАЛАВРА

«О диагностике и восстановлении неисправностей автоматных

языков при алфавитном кодировании»

Студента IV курса группы №221

Алешкова Максима Романовича

Научный руководитель:

к.ф.-м.н., н.с.
Дергач Петр Сергеевич

Баку — 2025
 Содержание

1 Аннотация 2

2 Введение 3

3 Постановка задачи 6

4 Основные определения и формулировки 7

5 Вспомогательные утверждения 10

6 Описание реализованных алгоритмов 11

6.1 Проверка приведенности автомата . . . . . . . . . . . . . . . 11
6.2 Проверка автомата на однозначность . . . . . . . . . . . . . 14
6.3 Диагностика единичных неисправностей в автомате . . . . . 22
6.4 Тестирование автомата на наличие единичной неисправности 24

7 Апробация алгоритмов 27

8 Заключение 28

9 Листинг программ 30

Листинг программ 30
Проверка приведенности автомата . . . . . . . . . . . . . . . . . . 30
Проверка автомата на однозначность . . . . . . . . . . . . . . . . 31
Диагностика единичных неисправностей в автомате . . . . . . . . 37
Тестирование автомата на наличие единичной неисправности . . 38

1
 1 Аннотация

В данной работе рассматриваются алгоритмические методы диагности-

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

2
 2 Введение

Одним из актуальных направлений в области теории дискретных струк-

тур и автоматов является исследование задач, связанных с алфавитным
кодированием регулярных языков, а также с диагностикой и восстанов-
лением неисправностей, возникающих при этом кодировании. Эта область
находится на пересечении теории формальных языков, теории автоматов
и теории кодирования. Особый интерес представляют задачи анализа по-
ведения автоматов при кодировании и декодировании, а также выявления
и устранения сбоев в системах, основанных на конечных автоматах.
Актуальность темы определяется широким спектром ее применений: от
проектирования и тестирования цифровых схем до построения надежных
способов передачи информации в телекоммуникационных и вычислитель-
ных системах. В условиях возрастающих требований к надежности и отка-
зоустойчивости систем возрастает значимость теоретически обоснованных
методов диагностики и восстановления, основанных на моделях автоматов
и свойствах регулярных языков.
Видное место в теории кодирования занимает задача проверки одно-
значности алфавитного кодирования. Она имеет важное значение для кор-
ректности декодирования, так как неоднозначность может привести к ис-
кажению информации. Формальные критерии однозначности для случая
языка A∗ рассматриваются в работе [1].
Фундаментальные понятия, свойства автоматов и регулярных языков
рассматриваются в классических работах [1, 2, 3, 4], которые составляют
теоретическую базу для построения алгоритмов кодирования и декодиро-
вания, а также анализа их корректности.
Существенный вклад в развитие методов диагностики и восстановления
в автоматных моделях внесен в работе [5], представляющей систематиче-
ский обзор методов построения тестов для выявления неисправностей в
логических схемах и конечных автоматах. Подходы из этой работы приме-
нимы к задачам автоматного тестирования и анализа диагностируемости
автомата.
В работе [6] предложен автоматно-алгебраический подход к решению

3
задачи однозначности, включая алгоритмы, обладающие полиномиальной
сложностью для регулярных языков, не содержащих пустое слово и имею-
щих полиномиальную функцию роста. Это делает предложенные методы
эффективными для практического применения.
В работе [7] рассматривается дескриптивная сложность различных пре-
образований регулярных языков. Автор анализирует верхние и нижние
оценки сложности представления результатов этих преобразований в тер-
минах детерминированных и недетерминированных конечных автоматов.
Полученные результаты позволяют более точно оценивать вычислитель-
ные ресурсы, необходимые для обработки регулярных языков.
В работе [8] рассматриваются конечные автоматы с отказами (Failure
Deterministic Finite Automata, FDFAs), которые позволяют более компакт-
но представлять регулярные языки по сравнению с классическими детер-
минированными конечными автоматами (DFAs). Авторы проводят эмпи-
рическое исследование четырех алгоритмов преобразования произвольных
DFAs в языково-эквивалентные FDFAs. Три из них основаны на модифи-
кациях ранее предложенного абстрактного DFA-гомоморфного алгоритма
(DHA), а четвертый использует построение максимального остовного де-
рева для получения так называемого DFA с задержкой по входу (delayed
input DFA).
В исследовании [9] представлена классификация автоматов с двумя со-
стояниями по устойчивости к единичной неисправности на выходе. Авто-
маты разделены на частично устойчивые и неустойчивые, что позволяет
оценивать их надежность в условиях сбоев.
В работе [10] рассматриваются автоматы с тремя состояниями. Прове-
дено комбинаторное исследование, включающее подсчет корректных диа-
грамм переходов и допустимых алфавитных кодировок. Это позволяет оце-
нить пространство возможных конфигураций и выработать подходы к ди-
агностике и восстановлению при ошибках.
В курсовой работе [11] было доказано утверждение о том, что на любом
однозначном автомате может возникнуть такая единичная неисправность
по выходу, при которой полученный новый автомат становится неоднознач-
ным.

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

5
 3 Постановка задачи

Рассматривается конечный инициальный абстрактный автомат V с про-

извольным входным алфавитом A и выходным алфавитом B = {0, 1}. Так-
же задана функция побуквенного алфавитного кодирования f с теми же
входным и выходным алфавитами. Заданный автомат распознает по вы-
ходному символу 1 регулярный язык P .
Требуется разработать инструментарий для получения ответов на сле-
дующие вопросы:

1. Является ли заданный автомат приведенным?

2. Является ли схема кодирования однозначной для множества слов,

распознаваемых автоматом?

3. Пусть заданный автомат является приведенным и язык, распознава-

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

4. Предположим, что изначальный автомат был однозначным и приве-

денным. Произошла ли единичная неисправность в данном автомате?
Если да, то в каком месте?

6
 4 Основные определения и формулировки

По большой части, определения были взяты из классических работ [1,

2, 3, 4].
Пусть C — некоторое конечное множество, называемое алфавитом.
Элементы этого множества называются буквами. Если γ = c1 . . . cn — ко-
нечная последовательность букв алфавита C, то говорят, что γ — это слово
в алфавите C. Число n называется длиной слова γ и обозначается как |γ|.
Абстрактным конечным автоматом называется пятерка:

V = (A, Q, B, φ, ψ),

где A, Q, B — конечные множества, φ — функция переходов φ : Q×A → Q,

ψ — функция выходов ψ : Q × A → B. Множества A, Q, B называются
соответственно входным алфавитом, множеством состояний и выходным
алфавитом автомата V .
Пусть q0 ∈ Q. Тогда шестерка (A, Q, B, φ, ψ, q0 ) задает автомат V с на-
чальным состоянием q0 и называется инициальным конечным абстракт-
ным автоматом.
Функции φ и ψ можно доопределить на множестве Q × A∗ (оставляя те
же обозначения) следующим образом:

φ(q, αa) = φ(φ(q, α), a), ψ(q, αa) = ψ(φ(q, α), a),

где q ∈ Q, α ∈ A∗ , a ∈ A.
Автомат (A, Q, {0, 1}, φ, ψ, q0 ) допускает слово α, если последний сим-
вол выходного слова ψ(q, α) равен 1. Множество всех таких слов обознача-
ется через 1(V ) и называется распознаваемым языком автомата.
Будем называть состояние qi конечного инициального абстрактного ав-
томата V достижимым из начального состояния, если существует вход-
ное слово α ∈ {0, 1}∗ , такое что φ(q, α) = qi , где q0 — начальное состояние
автомата V .
Два состояния qi , qj конечного инициального автомата V называют-
ся отличимыми, если существует входное слово α ∈ {0, 1}∗ , такое что

7
ψ(qi , α) ̸= ψ(qj , α). В противном случае состояния qi , qj называются неот-
личимыми.
Диаграммой Мура автомата называется ориентированный граф G, вер-
шинами которого являются состояния q ∈ Q, а ребра соответствуют зна-
чениям функции φ. Если φ(q, a) = q ∗ , то в графе есть дуга из q в q ∗ , по-
меченная меткой (a, b), где b = ψ(q, a). Начальное состояние q помечается
звездочкой.
Для построения диаграммы Мура:

• каждому состоянию qi ∈ Q = {q1 , . . . , qn } соответствует вершина;

• для каждой пары (qi , aj ), где aj ∈ A = {0, 1}, проводится дуга от qi

к qk = φ(qi , aj ), помеченная (aj , ψ(qi , aj )).

Диаграмму Мура G будем называть приведенной, если любые два со-

стояния диаграммы отличимы и все ее состояния являются достижимыми
из начального состояния.
Пусть A = {a1 , . . . , ar } — конечный непустой алфавит. Для непустых
множеств слов P1 , P2 в алфавите A определим операции:

1. Объединение: P1 ∪ P2 = {α | α ∈ P1 или α ∈ P2 };

2. Итерация (замыкание Клини): P1∗ = {α1 . . . αk | αi ∈ P1 , k ≥ 0};

3. Конкатенация: P1 · P2 = {α1 α2 | α1 ∈ P1 , α2 ∈ P2 }.

Множество P называется регулярным в алфавите A, если его мож-

но получить из пустого множества и одноэлементных множеств {a}, где
a ∈ A, с помощью конечного числа применений операций объединения,
конкатенации и итерации. Формально:

1. ∅ — регулярное множество;

2. a, где a ∈ A — регулярное множество;

3. Если P1 , P2 — регулярные, то и P1 ∪ P2 , P1 · P2 , P1∗ — регулярные;

4. Регулярность произвольного множества устанавливается по пунктам

(1)–(3) за конечное число шагов.

8
 Отображение f : A → {0, 1}∗ называется схемой кодирования из алфа-
вита A в алфавит {0, 1}. Множество всех таких отображений обозначается
через F2 .
Доопределим отображение f ∈ F2 до отображения f˜ : A∗ → {0, 1}∗ по
правилу:
f˜(ai1 ai2 . . . ain ) = f (ai1 )f (ai2 ) . . . f (ain ).

Отображение f˜ называется алфавитным кодированием.

Кодирование f˜ называется взаимно однозначным на языке P ⊆ {0, 1}∗ ,
если любые два различных слова из P переходят в различные слова под
действием f˜. Также будем называть конечный инициальный автомат V
однозначным или однозначно декодируемым на данной схеме алфавитного
кодирования, если кодирование f˜ взаимно однозначно на регулярном языке
P , распознаваемом автоматом.
Пусть G — диаграмма Мура. Единичной неисправностью выхода (или
по выходу) называется замена выходного значения ψ(q, a) на противопо-
ложное (0 ↔ 1) на одном из ребер диаграммы.
Единичную неисправность по выходу, произошедшую в приведенной
и однозначной на схеме кодирования f диаграмме Мура G автомата V ,
будем называть диагностируемой, если после ее возникновения диаграмма
автомата становится неприведенной или неоднозначной на данной схеме
кодирования f ∈ F2 .
Пусть заданы конечный инициальный абстрактный автомат V и схе-
ма кодирования f . Также известно, что автомат V — однозначен на f и
приведенный. Предполагается, что в процессе работы могла произойти од-
на единичная неисправность по выходу, в результате которой был получен
некоторый автомат. Необходимо определить, произошла ли неисправность
и если неисправность произошла, то в каком месте. Такая задача называ-
ется задачей тестирования.

9
 5 Вспомогательные утверждения

Утверждение (теорема Мура). Состояния q1 и q2 конечного автомата V =

(A, Q, B, φ, ψ) неотличимы тогда и только тогда, когда они неотличимы
множеством A|Q|−1 .

Доказательство. Доказательство теоремы приведено в [2].

10
 6 Описание реализованных алгоритмов

В данной секции представлены описания реализованных алгоритмов.

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

6.1 Проверка приведенности автомата

Входные данные На вход алгоритму подается абстрактный конечный

инициальный автомат с произвольным входным алфавитом и множеством
состояний. Выходной алфавит поданного автомата должен являться мно-
жеством B = {0, 1}.

Выходные данные Результатом работы программы является True, если

автомат V приведен, и False — в противном случае.

Описание алгоритма

За основу был взят одноименный алгоритм Мура для проверки авто-

мата на приведенность. Его можно найти в [2].
Проверка приведенности автомата включает два основных этапа:

1. Проверка достижимости состояний автомата

Для определения приведенности автомата необходимо установить, до-

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

1.1. Обход начинается из начального состояния автомата.

1.2. На каждом шаге просматриваются все возможные переходы из теку-

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

11
 1.3. Обнаруженные состояния, в которые ранее не совершался переход,
добавляются в множество, рассматриваемое на следующих итераци-
ях. Этот процесс повторяется до тех пор, пока не будут исследованы
все достижимые состояния.

1.4. По завершении обхода осуществляется сравнение мощности множе-

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

Если обнаружены недостижимые состояния, автомат не является при-

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

Сложность:

• Временная сложность:

O(|Q| · |A|),

поскольку в худшем случае каждое состояние обрабатывается один

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

• Память:
O(|Q|)

— на хранение множества посещенных состояний и списка состояний,

рассматриваемых в будущем.

2. Проверка неотличимости состояний

Для установления приведенности автомата необходимо также опреде-

лить, существуют ли среди его состояний неотличимые. Один из классиче-
ских подходов к решению этой задачи — алгоритм Мура, основанный на
последовательном уточнении разбиения множества состояний. Алгоритм
работает следующим образом:

12
2.1. Изначально каждому состоянию сопоставляется набор выходных зна-
чений автомата при переходе из данного состояния по каждому сим-
волу входного алфавита. На основе этих наборов строится первичное
разбиение множества состояний на классы эквивалентности.

2.2. Далее начинается итерационный процесс уточнения классов. На каж-

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

2.3. Процесс повторяется до тех пор, пока новое разбиение не совпадет с

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

2.4. Если в результате работы алгоритма общее число полученных клас-

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

Сложность:

• Временная сложность:

O(|Q|3 · |A|)

— каждая итерация обработки всех состояний требует O(|Q|2 · |A|), а

число итераций не превышает |Q|.

• Память:
O(|Q|)

— требуется для хранения текущего и следующего разбиений состо-

яний.

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

Общая сложность:

• Временная сложность:

O(|Q| · |A|) + O(|Q|3 · |A|) = O(|Q|3 · |A|),

где первое слагаемое — сложность обхода в ширину при проверке

достижимости, второе — работа алгоритма Мура.

• Память:
O(|Q|) + O(|Q|) = O(|Q|),

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

и классов эквивалентности.

6.2 Проверка автомата на однозначность

Входные данные На вход алгоритму подается приведенный абстракт-

ный конечный инициальный автомат V с произвольным входным алфа-
витом и множеством состояний. Выходной алфавит поданного автомата
должен являться множеством B = {0, 1}. Также на вход подается схема
алфавитного кодирования f ∈ F2 .

Выходные данные Результатом работы программы является True, если

автомат V однозначен на схеме кодирования f , и False — в противном
случае. Если поданный автомат оказался неприведенным, то в этом случае
программа вернет None.

Описание алгоритма

За основу был взят одноименный алгоритм Маркова для проверки ре-

гулярного языка на однозначность. Его можно найти в [1].

14
 Для проверки того, является ли схема кодирования однозначной для
множества слов, распознаваемых автоматом, осуществляется построение
автомата, распознающего язык P × P , где P — язык, распознаваемый ав-
томатом V . Далее строится автомат, распознающий слова с одинаковыми
буквами. Так как такие слова нас не интересуют, производится операция
разности одного автомата с другим. Полученный автомат может распозна-
вать слова с одинаковым кодом. Этот автомат необходимо проверить на
достижимость такого ребра из начального состояния.
Таким образом, проверка автомата на однозначность состоит из четы-
рех основных этапов:

1. Построение автомата P × P .

Алгоритм строит диаграмму Мура нового автомата, распознающего

язык P × P . Здесь P — язык, распознаваемый автоматом V . Такой ав-
томат представляет поведение двух одинаковых автоматов при подаче на
них различных входных слов. Каждая вершина графа содержит:
! ! !
β λ λ
• остаток от склеек кодов (отставание): , или ;
λ β λ
!
qu
• текущие состояния автоматов: ;
qd
!
bu
• выходные значения автоматов: .
bd

Начальной вершиной в таком автомате является:

! ! !!
λ q0 λ
vstart = , , ,
λ q0 λ

где q0 — стартовое состояние автомата V .

Пусть vi — ! текущая
! вершина
! автомата, содержащая! один из видов
λ β λ qu
остатков: , или ; пару состояний и пару выходов
β λ λ qd

15
 !
bu
. Строим множество новых вершин, проводя к ним ребра из vi по
bd
следующему правилу:

1.1. Если в вершине vi содержится пустой остаток, то есть:

! ! !!
λ qu bu
, , ,
λ qd bd

то подача буквы из входного алфавита осуществляется в нижний

!
λ
автомат. Для каждой буквы a ∈ A формируем ребро с входом .
a
Далее создаем вершину vj , в которую записываются:

• остаток: !
λ
;
f (a)
• состояния: !
qu
;
φ(qd , a)
• выходы: !
bu
.
ψ(qd , a)

В случае, когда bu = 1 и ψ(qd , a) = 1, значение выхода по ребру,

соединяющему vi и vj , равняется 1. В противном случае — 0.

1.2. Если вершина vi не является пустой, то определяем, в какой части

содержится остаток:

• если βd ̸= λ, то подача происходит в верхний автомат;

• если βu ̸= λ, то подача происходит в нижний автомат.

1.3. Буква a ∈ A может быть подана в автомат только тогда, когда оста-
ток (обозначим как β) является префиксом кодового слова этой бук-
вы или кодовое слово является префиксом остатка. Формально:

f (a) = β ′ β ′′ , где β = β ′ или f (a) = β ′ , где β = β ′ β ′′ .

16
1.4. В новой вершине vj :

• Остаток в той части, где он был раньше, уменьшается — из него

удаляется общий префикс с кодом поданной буквы.

f (a) = β ′ , β = β ′γ ⇒ β = γ.

• Если оказалось, что код поданной буквы оказался больше остат-

ка, то остаток в той части зануляется: βu = λ или βd = λ, а в
противоположной части устанавливается новая строка:

β op = β ′′ , где f (a) = β ′ β ′′ .

• Состояние и выход той части, где был остаток, остаются преж-

ними;
• Состояние и выход противоположной части обновляются:

q op = φ(q, a), bop = ψ(q, a),

где q — состояние противоположной части до изменения.

1.5. Из вершины vi в вершину vj проводится ориентированное ребро с

входом и выходом соответственно:
! ! ! !
λ a
,b или ,b ,
a λ

в зависимости от того, в какую часть был подан символ a. В случае,

когда bu = 1 и ψ(q, a) = 1, выход b = 1, иначе — b = 0.

1.6. Если нет допустимых переходов по (a, λ) или (λ, a), то переход на-
правляется в специальное тупиковое состояние:
! ! !!
e e e
vend = , , ,
e e e

17
 из которого все входы ведут в него же, а выход всегда равен 0.

1.7. Алгоритм продолжается итеративно от каждой новой вершины по

тем же правилам.

Сложность алгоритма:

• Временная сложность:

O(L · |Q|2 · |A|),

где |Q| — количество состояний автомата V , |A| — мощность входного

алфавита, L — суммарная длина всех кодов. Каждая вершина может
иметь до |A| переходов.

• Память:
O(L · |Q|2 · |A|)

— на хранение всех вершин автомата (с остатками, состояниями, вы-

ходами) и всех возможных ребер.

2. Построение автомата для распознавания слов с одинаковыми

буквами

Алгоритм строит автомат Мура, который проверяет, представляет ли

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

2.1. Для каждой буквы a ∈ A с кодом f (a) создаются две вершины:

!! !!
f (a) λ
vi1 = , vi2 = .
λ f (a)

18
 !
λ
Из начальной вершины в вершины vi1 и vi2 ведут ребра:
λ
! ! ! !
a λ
,0 , ,0 ,
λ a

соответственно, где первый элемент в скобках — входной символ, а

второй — выход автомата на соответствующем переходе.

2.2. Из вершин vi1 и vi2 добавляются ребра обратно в начальную вершину

с выходом 1: ! ! ! !
λ a
,1 , ,1 .
a λ

2.3. Для каждой пары различных букв a ̸= a′ ∈ A добавляются ребра из

vi1 и vi2 в тупиковую вершину vend с выходом 0:
! ! ! !
′
λ a
,0 , ,0 .
a′ λ

Также из вершин vi1 и vi2 добавляются ребра в тупиковую вершину

при попытке завершить слово:
! ! ! !
λ a
,0 , ,0 .
a λ

2.4. Из вершины vend все переходы ведут в нее же при любом входе, при
этом выход всегда 0.

Таким образом, автомат проверяет, образуют ли верхний и нижний ря-

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

Сложность:

• Временная сложность:
O(|A|2 )

19
 — создаются всевозможные вершины и для каждой из них добавля-
ются ребра, соответствующие всем возможным сочетаниям символов.

• Память:
O(|A|) + O(|A|2 ) = O(|A|2 )

— на хранение всех состояний и ребер построенного автомата.

3. Построение разности автоматов

На основе автомата, распознающего язык P × P , где P — язык, распо-

знаваемый автоматом V , и автомата, распознающего пары слов с одинако-
выми буквами, строится разность этих двух автоматов:

3.1. Генерируются все возможные вершины — состояния нового автома-

та. Каждая вершина имеет вид (qP ×P , qdiag ), где qP ×P — состояние
автомата, распознающего язык P × P , а qdiag — состояние автомата,
распознающего пары слов с одинаковыми буквами. Начальным со-
стоянием такого автомата будет являться состояние q0P ×P , q0diag , где

q0P ×P — начальное состояние автомата, распознающего язык P × P ,

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

3.2. Из каждой вершины нового автомата проводятся ребра, входными

значениями которых являются всевозможные двухъярусные буквы.
Для каждой двухъярусной буквы (входного символа) на выходе по
ребру:

• Если в автомате P × P выход равен 1, а в автомате, распозна-

ющем одинаковые слова, выход равен 0, то на выходе результи-
рующего автомата устанавливается 1.
• Во всех остальных случаях на выходе устанавливается 0.

Сложность:

20
 • Временная сложность:

O(L · |Q|2 · |A|) + O(L · |Q|2 · |A|2 ) = O(L · |Q|2 · |A|2 ),

где первое слагаемое соответствует количеству вершин автомата, ре-

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

• Память
O(L · |Q|2 · |A|2 )

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

мата.

4. Проверка на достижимость принимающего ребра

Возможно, что в автомате, реализующего разность двух автоматов,

принимающие ребра (с выходом 1), окажутся недостижимыми из началь-
ного состояния. Для проверки достижимости запускается обход в ширину.
Если в процессе обхода не удалось достичь ни одного ребра с выходом 1,
то язык, распознаваемый автоматом V , является однозначным на схеме
кодирования f . В противном случае язык не является однозначным.

Сложность:

• Временная сложность:

O(L · |Q|2 · |A| + L · |Q|2 · |A|2 ) = O(L · |Q|2 · |A|2 ),

поскольку в худшем случае каждое состояние обрабатывается один

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

• Память
O(L · |Q|2 · |A|)

21
 — на хранение множества посещенных состояний и списка состояний,
рассматриваемых в будущем.

Общая сложность:

• Временная сложность:

O(L · |Q|2 · |A|) + O(|A|2 ) + O(L · |A|2 · |Q|2 )+

+ O(L · |A|2 · |Q|2 ) = O(L · |Q|2 · |A|2 )

где первое слагаемое — сложность построения автомата, распознаю-

щего язык P ×P , второе — сложность построения автомата, распозна-
ющего одинаковые слова, третье — сложность построения автомата,
реализующего разность двух других а четвертое — сложность обхода
в ширину автомата реализующего разность.

• Память:

O(L · |Q|2 · |A|) + O(|A|2 ) + O(L · |Q|2 · |A|2 )

+ O(L · |Q|2 · |A|) = O(L · |Q|2 · |A|2 )

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

P × P , автомата, распознающего одинаковые слова и автомата, реа-
лизующего разность и на хранения множества посещенных состояний
и списка состояний, рассматриваемых в будущем, в алгоритме обхода
в ширину.

6.3 Диагностика единичных неисправностей в автомате

Входные данные На вход алгоритму подается абстрактный конечный

инициальный автомат V с произвольным входным алфавитом и множе-
ством состояний. Выходной алфавит поданного автомата должен являться
множеством: B = {0, 1}. Также на вход подается схема алфавитного ко-
дирования f ∈ F2 . Обязательным условием является факт того, что по-

22
данный автомат является приведенным и однозначным на поданной схеме
кодирования. В противном случае диагностика не производится.

Выходные данные Результатом работы программы является число

успешно диагностируемых неисправностей. Если поданный автомат ока-
зался неприведенным или неоднозначным, то программа вернет 0.

Описание алгоритма

Опишем алгоритм для выявления количества диагностируемых едич-

ничных неисправностей в данном автомате на данной схеме кодирования,
при условии, что данный автомат приведен и однозначен на данной схеме
кодирования. В работе [11], был доказан факт того, что всегда существует
такая единичная неисправность, из-за которой автомат становится неод-
нозначным на данной схеме кодирования. По этой причине, количество
диагностируемых единичных неисправностей всегда ≥ 1.

1. Перебираются все ребра автомата. Для каждого ребра происходит

изменение выходного значения.

2. После каждого изменения создается копия автомата с новой выход-

ной функцией.

3. Выполняется проверка приведенности и однозначности автомата.

4. Если хотя бы одно из условий нарушается, единичная неисправность

считается диагностируемой.

5. Перебор продолжается до обработки всех возможных изменений вы-

ходных символов.

Сложность:

• Временная сложность:

(O(|Q|3 ·|A|)+O(L·|Q|2 ·|A|2 )))·|Q|·|A| = O(|Q|4 ·|A|2 +L·|Q|3 ·|A|3 ),

23
 Сложность складывается из:

– O(|Q| · |A|) — количество возможных изменений выходных сим-

волов: каждое из |Q|·|A| ребер проверяется на замену выходного
символа;
– O(|Q|3 · |A|) — проверка приведенности автомата;
– O(L · |Q|2 · |A|2 ) — проверка однозначности.

• Память

(O(|Q|) + O(L · |Q|2 · |A|2 )) · |Q| · |A| = O(L · |Q|3 · |A|3 )

Память используется для хранения:

– новой версии автомата с модифицированным выходом;

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

6.4 Тестирование автомата на наличие единичной

неисправности

Входные данные На вход алгоритму подается схема алфавитного ко-

дирования f ∈ F2 и абстрактный конечный инициальный автомат V с
произвольным входным алфавитом и множеством состояний, про который
известно, что он получен из изначально однозначного и приведеного авто-
мата применением не более чем одной единичной неисправности по выхо-
ду. Выходной алфавит поданного автомата должен являться множеством:
B = {0, 1}.

Выходные данные Результатом работы программы является True, ес-

ли на автомате V произошла единичная неисправность по выходу, и False
— в противном случае. Если мы не смогли определить произошла ли неис-
правность на поданном автомате, то в этом случае программа вернет None.
В случае, когда получилось определить, произошла ли единичная неис-
правность, может также получиться определить непосредственное место ее

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

Описание алгоритма

Опишем алгоритм тестирования, то есть определения факта наличия

единичной неисправности.

1. Выполняется проверка однозначности и приведености поданного ав-

томата.

2. Если автомат однозначен и приведен, то:

• перебираются все ребра автомата, для каждого производится из-

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

3. Если исходный автомат неприведен или неоднозначен, то:

• перебираются все ребра и изменяются выходные символы;

• после каждой модификации создается копия автомата;
• выполняется проверка однозначности модифицированных авто-
матов;
• если найден ровно один модифицированный автомат, ставший
однозначным, делается вывод: произошла единичная неисправ-
ность и можно определить точное место, в котором произо-
шла неисправность;

25
 • если найдено более одного однозначного автомата — произо-
шла единичная неисправность, но точного места возникнове-
ния неисправности указать не получается;
• если не найдено однозначного автомата, то поданный автомат
не удовлетворяет начальным условиям.

Сложность:

• Временная сложность:

(O(|Q|3 ·|A|)+O(L·|Q|2 ·|A|2 )))·|Q|·|A| = O(|Q|4 ·|A|2 +L·|Q|3 ·|A|3 ),

Сложность складывается из:

– O(|Q| · |A|) — количество возможных изменений выходных сим-

волов: каждое из |Q|·|A| ребер проверяется на замену выходного
символа;
– O(|Q|3 · |A|) — проверка приведенности автомата;
– O(L · |Q|2 · |A|2 ) — проверка однозначности.

• Память

(O(|Q|) + O(L · |Q|2 · |A|2 )) · |Q| · |A| = O(L · |Q|3 · |A|3 )

Память используется для хранения:

– новой версии автомата с модифицированным выходом;

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

26
 7 Апробация алгоритмов

Для проверки корректности и эффективности разработанных алгорит-

мов были использованы конечные автоматы, представленные в работах [9,
10]. В этих работах исследованы всевозможные автоматы с двумя и тремя
состояниями.
В работе [9] рассматриваются все автоматы с двумя состояниями. Эти
автоматы были разделены на классы частичной устойчивости и неустой-
чивости. Доказательства тех или иных свойств автоматов позволяют по-
лучить теоретическое обоснование для тестирования таких автоматов на
наличие единичной неисправности.
Особое внимание было уделено автоматам, представленным в исследо-
вании [10], в котором рассматриваются всевозможные автоматы с двумя и
тремя состояниями. Исследуется количество диагностируемых единичных
неисправностей в таких автоматах, что позволяет точно оценить работу
алгоритма на этих примерах.
Кроме того, была проведена проверка общего количества однозначных
и приведенных автоматов с двумя и тремя состояниями. Полученные ре-
зультаты полностью совпали с теоретическими данными, что подтверждает
корректность реализованных алгоритмов и полноту тестирования.
Таким образом, выбор автоматов из работ [9, 10] обеспечил как теорети-
ческую обоснованность, так и практическую полноту тестирования пред-
ложенных алгоритмов диагностики и тестирования.

27
 8 Заключение

В данной дипломной работе были реализованы алгоритмы проверки ко-

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

28
 Список литературы

[1] Марков А.А., "Введение в теорию кодирования."М.: Наука, 1985.

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

автоматов."М.: Наука, 1985.

[3] Яблонский С.В., "Введение в дискретную математику."М.: Наука, 1986.

[4] Хопкрофт Дж., Мотвани Р., Ульман Дж., "Введение в теорию автома-
тов, языков и вычислений."М.: Вильямс, 2002.

[5] Кудрявцев В.Б., Гасанов Э.Э., Долотова О.А., Погосян Г.Р., "Теория
тестирования логических устройств."Физматлит, Москва 2006.

[6] Дергач П.С., "Алфавитное кодирование регулярных языков с полино-

миальной функцией роста."Кандидатская диссертация, 2016.

[7] Поваров Г.А., "Дескриптивная сложность некоторых преобразований

регулярных языков"Кандидатская диссертация, 2010.

[8] Nxumalo M., Kourie D.G., Cleophas L., Watson B.W., "An Assessment
of Algorithms for Deriving Failure Deterministic Finite Automata South
African Computer Journal, Vol. 29(1), July 2017.

[9] Ткачук С.Д., "О единичных неисправностях диаграмм Мура и сохра-

нении однозначности декодирования"Дипломная работа, 2024.

[10] Гулиева Р.А., "Об автоматных и алфавитных неисправностях регуляр-

ных языков."Дипломная работа, 2025.

[11] Алешков М.Р., "Об автоматных неисправностях при алфавитном ко-

дировании"Курсовая работа, 2024.

29
 9 Листинг программ

В этом разделе приведены основные реализации алгоритмов, исполь-

зованных в дипломной работе. Каждый листинг сопровождается кратким
описанием его назначения.

Проверка приведенности автомата

Ниже представлены функции, выполняющие проверку приведенности

конечного автомата.
1 def any_unreachable_states ( phi , A , Q , q_start ) :
2 visited = set ()
3 to_check = [ q_start ]
4

5 while to_check :
6 state = to_check . pop ()
7 visited . add ( state )
8 for a in A :
9 to_check_state = phi [( state , a ) ]
10 if to_check_state not in visited :
11 visited . add ( to_check_state )
12 to_check . append ( to_check_state )
13

14 return len ( visited ) != len ( Q )

Листинг 1: Проверка наличия недостижимых состояний

1 def any_equivalent_states ( psi , phi , A , Q ) :

2 sigs = { q : tuple ( psi [( q , a ) ] for a in A ) for q in Q }
3 part = {}
4 for i , sig in enumerate ( sorted ( set ( sigs . values () ) ) ) :
5 for q in Q :
6 if sigs [ q ] == sig :
7 part [ q ] = i
8

9 for _ in range ( len ( Q ) - 1) :

10 sigs = { q : tuple (( part [ phi [( q , a ) ]] , psi [( q , a ) ]) for a
in A ) for q in Q }
11 new_part = {}

30
12 for i , sig in enumerate ( sorted ( set ( sigs . values () ) ) ) :
13 for q in Q :
14 if sigs [ q ] == sig :
15 new_part [ q ] = i
16 if new_part == part :
17 break
18 part = new_part
19

20 return len ( set ( part . values () ) ) != len ( Q ) # O (| Q |^3 * | A |)

Листинг 2: Проверка эквивалентных состояний

1 def is_minimized (Q , A , phi , psi , q_start ) :

2 if any_unreachable_states ( phi , A , Q , q_start ) :
3 return False
4 if any_equivalent_states ( psi , phi , A , Q ) :
5 return False
6 return True

Листинг 3: Проверка приведенности автомата

Проверка автомата на однозначность

Ниже представлены функции, выполняющие проверку однозначности

поданного конечного автомата на поданной схеме кодирования.
1 def build_P_P_automata ( schema_encoding , A , B , Q , phi , psi ,
q_start ) :
2 edges = defaultdict ( list )
3 empty_empty_vertex = (( ’ ’ , ’ ’) , ( q_start , q_start ) , ( ’ ’ , ’ ’
))
4 error_state = (( ’e ’ , ’e ’) , ( ’e ’ , ’e ’) , ( ’e ’ , ’e ’) )
5

6 start_vertex = empty_empty_vertex
7 vertexes = [ empty_empty_vertex ]
8 seen = set ()
9 seen . add ( empty_empty_vertex )
10

11 double_letters = [( a , ’ ’) for a in A ] + [( ’ ’ , a ) for a in A

]
12

31
13 for v in vertexes :
14 len_v0 = len ( v [0][0])
15 len_v1 = len ( v [0][1])
16 for a1 , a1_encoding in schema_encoding . items () :
17 a1_encoding_len = len ( a1_encoding )
18

19 if len_v0 > len_v1 and ( a1_encoding . startswith ( v

[0][0]) or v [0][0]. startswith ( a1_encoding ) ) :
20 new_v0_suffix = ’ ’ if a1_encoding . startswith ( v
[0][0]) else v [0][0][ a1_encoding_len :]
21 new_v1_suffix = a1_encoding [ len_v0 :] if
a1_encoding . startswith ( v [0][0]) else ’ ’
22 new_v_suffixes = ( new_v0_suffix , new_v1_suffix )
23

24 new_v0_state = v [1][0]
25 new_v1_state = phi [( v [1][1] , a1 ) ]
26 new_v_states = ( new_v0_state , new_v1_state )
27

28 new_v0_exit_value = v [2][0]
29 new_v1_exit_value = psi [( v [1][1] , a1 ) ]
30 new_v_exit_values = ( new_v0_exit_value ,
new_v1_exit_value )
31

32 new_v = ( new_v_suffixes , new_v_states ,

new_v_exit_values )
33

34 if new_v not in seen :

35 seen . add ( new_v )
36 vertexes . append ( new_v )
37

38 exit = ’1 ’ if new_v_suffixes == ( ’ ’ , ’ ’) and (

new_v0_exit_value , new_v1_exit_value ) == ( ’1
’ , ’1 ’) else ’0 ’
39 new_edge_weight = (( ’ ’ , a1 ) , exit )
40 edges [ v ]. append (( new_v , new_edge_weight ) )
41

42 elif ( len_v0 < len_v1 and ( a1_encoding . startswith ( v

[0][1]) or v [0][1]. startswith ( a1_encoding ) ) ) or
( len_v0 == 0 and len_v1 == 0) :
43 new_v1_suffix = ’ ’ if a1_encoding . startswith ( v

32
 [0][1]) else v [0][1][ a1_encoding_len :]
44 new_v0_suffix = a1_encoding [ len_v1 :] if
a1_encoding . startswith ( v [0][1]) else ’ ’
45 new_v_suffixes = ( new_v0_suffix , new_v1_suffix )
46

47 new_v1_state = v [1][1]
48 new_v0_state = phi [( v [1][0] , a1 ) ]
49 new_v_states = ( new_v0_state , new_v1_state )
50

51 new_v1_exit_value = v [2][1]
52 new_v0_exit_value = psi [( v [1][0] , a1 ) ]
53 new_v_exit_values = ( new_v0_exit_value ,
new_v1_exit_value )
54

55 new_v = ( new_v_suffixes , new_v_states ,

new_v_exit_values )
56

57 if new_v not in seen :

58 seen . add ( new_v )
59 vertexes . append ( new_v )
60

61 exit = ’1 ’ if new_v_suffixes == ( ’ ’ , ’ ’) and (

new_v0_exit_value , new_v1_exit_value ) == ( ’1
’ , ’1 ’) else ’0 ’
62 new_edge_weight = (( a1 , ’ ’) , exit )
63 edges [ v ]. append (( new_v , new_edge_weight ) )
64

65

66 if error_state not in seen :

67 seen . add ( error_state )
68 vertexes . append ( error_state )
69

70

71 for v in vertexes :
72 existing = set ( enter_exit for (_ , enter_exit ) in edges [
v ])
73 for letter in double_letters :
74 if letter not in existing :
75 edges [ v ]. append (( error_state , ( letter , ’0 ’) ) )
76

33
77

78 for letter in double_letters :

79 edges [ error_state ]. append (( error_state , ( letter , ’0 ’) ) )
80

81 return {
82 ’ vertexes ’: vertexes ,
83 ’ edges ’: edges ,
84 ’ start_vertex ’: start_vertex ,
85 }

Листинг 4: Построение автомата P × P

2 def build_diag_automata ( schema_encoding , A , B , Q , phi , psi ,

q_start ) :
3 start_vertex = ( ’ ’ , ’ ’)
4 end_vertex = ( ’e ’ , ’e ’)
5 vertexes = { start_vertex , end_vertex }
6 edges = defaultdict ( set )
7

8 for a1 , a1_encoding in schema_encoding . items () :

9 v1 = ( a1_encoding , ’ ’)
10 v2 = ( ’ ’ , a1_encoding )
11 vertexes . add ( v1 )
12 vertexes . add ( v2 )
13

14 edges [ start_vertex ]. add (( v1 , (( a1 , ’ ’) , ’0 ’) ) )

15 edges [ start_vertex ]. add (( v2 , (( ’ ’ , a1 ) , ’0 ’) ) )
16

17 for a1 , a1_encoding in schema_encoding . items () :

18 v1 = ( a1_encoding , ’ ’)
19 v2 = ( ’ ’ , a1_encoding )
20

21 edges [ v1 ]. add (( start_vertex , (( ’ ’ , a1 ) , ’1 ’) ) )

22 edges [ v2 ]. add (( start_vertex , (( a1 , ’ ’) , ’1 ’) ) )
23

24 for b1 , b1_encoding in schema_encoding . items () :

25 if b1 != a1 :
26 edges [ v1 ]. add (( end_vertex , (( ’ ’ , b1 ) , ’0 ’) ) )
27 edges [ v2 ]. add (( end_vertex , (( b1 , ’ ’) , ’0 ’) ) )
28

34
29 for a1 in schema_encoding :
30 edges [ end_vertex ]. add (( end_vertex , (( a1 , ’ ’) , ’0 ’) ) )
31 edges [ end_vertex ]. add (( end_vertex , (( ’ ’ , a1 ) , ’0 ’) ) )
32

33 return {
34 ’ vertexes ’: list ( vertexes ) ,
35 ’ edges ’: edges ,
36 ’ start_vertex ’: start_vertex ,
37 }

Листинг 5: Построение диагонального автомата

1 def build_intersected ( schema_encoding , A , B , Q , phi , psi ,

q_start ) :
2 if not is_minimized (Q , A , phi , psi , q_start ) :
3 print ( " The automata is not minimized " )
4 return None
5

6 p_p_automata = build_P_P_automata ( schema_encoding , A , B , Q ,

phi , psi , q_start )
7 diag_automata = build_diag_automata ( schema_encoding , A , B ,
Q , phi , psi , q_start )
8

9 start_vertex = ( p_p_automata [ ’ start_vertex ’] , diag_automata

[ ’ start_vertex ’ ])
10 vertexes = [( v1 , v2 ) for v1 in p_p_automata [ ’ vertexes ’] for
v2 in diag_automata [ ’ vertexes ’ ]]
11

12 edges = defaultdict ( list )

13

14

15 for from_p_p , edges_p_p in p_p_automata [ ’ edges ’ ]. items () :

16 for from_diag , edges_diag in diag_automata [ ’ edges ’ ].
items () :
17 for edge_p_p in edges_p_p :
18 for edge_diag in edges_diag :
19 if edge_p_p [1][0] == edge_diag [1][0]:
20

21 exit = ’1 ’ if ( edge_p_p [1][1] ,

edge_diag [1][1]) == ( ’1 ’ , ’0 ’) else
’0 ’

35
22 s = ( edge_p_p [0] , edge_diag [0])
23 in_exit = ( edge_p_p [1][0] , exit )
24 edges [( from_p_p , from_diag ) ]. append (( s ,
in_exit ) )
25

26

27

28 return {
29 ’ vertexes ’: vertexes ,
30 ’ edges ’: edges ,
31 ’ start_vertex ’: start_vertex ,
32 }

Листинг 6: Построение разности автоматов

2 def is_ambigous ( schema_encoding , A , B , Q , phi , psi , q_start ) :

3 automata = build_intersected ( schema_encoding , A , B , Q , phi ,
psi , q_start )
4

5 if not automata :
6 print ( " The automata is not minimized " )
7 return None
8

9 start = automata [ ’ start_vertex ’]

10 edges = automata [ ’ edges ’]
11

12 visited = set ()
13 queue = [ start ]
14

15 while queue :
16 current = queue . pop (0)
17 if current in visited :
18 continue
19 visited . add ( current )
20

21 for to , word_exit in edges . get ( current , []) :

22

23 exit = word_exit [1]

24 if exit == ’1 ’:
25 return True

36
26 queue . append ( to )
27

28 return False

Листинг 7: Проверка достижимости принимающего ребра

Диагностика единичных неисправностей в автомате

Ниже представлены функции, реализующие алгоритм для выявления

количества диагностируемых единичных неисправностей по выходу у по-
данного автомата и поданной функции кодирования.
1 def number_of_fault_diagnostics ( schema_encoding , A , B , Q , phi ,
psi , q_start ) :
2

3 if not is_minimized (Q , A , phi , psi , q_start ) or is_ambigous

( schema_encoding , A , B , Q , phi , psi , q_start ) :
4 print ( ’ initial automata is not minimized or ambiguous ’)
5 return 0
6

7 faults_count = 0
8 for key in psi :
9 copy_psi = psi . copy ()
10 copy_psi [ key ] = B [0] if copy_psi [ key ] == B [1] else B [1]
11

12 not_minimized = not is_minimized (Q , A , phi , copy_psi ,

q_start )
13 ambigious = is_ambigous ( schema_encoding , A , B , Q , phi ,
copy_psi , q_start )
14 if not_minimized or ambigious :
15 print ( " not_minimized = " , not_minimized , ’;
ambigious = ’ , ambigious , ’; key = ’ , key )
16 faults_count += 1
17

18 return faults_count

Листинг 8: Выявление количества неисправностей

37
 Тестирование автомата на наличие единичной неисправности

Ниже представлены функции, реализующие алгоритм тестирования ав-

томата на наличие единичной неисправности.
1 def is_fault_happened ( schema_encoding , A , B , Q , phi , psi ,
q_start ) :
2 is_initial_correct = is_minimized (Q , A , phi , psi , q_start )
or not is_ambigous ( schema_encoding , A , B , Q , phi , psi ,
q_start )
3 brake_to_create_correct = set ()
4 for key in psi :
5 copy_psi = psi . copy ()
6 copy_psi [ key ] = B [0] if copy_psi [ key ] == B [1] else B [1]
7

8 if is_minimized (Q , A , phi , copy_psi , q_start ) or not

is_ambigous ( schema_encoding , A , B , Q , phi , copy_psi ,
q_start ) :
9 brake_to_create_correct . add ( key )
10

11 brake_to_create_correct_len = len ( brake_to_create_correct )

12

13 if is_initial_correct :
14 if brake_to_create_correct_len == 0:
15 print ( ’ no fault happened ’)
16 return False
17 else :
18 print ( ’ as initial automata is correct and we found
broken automata those are also correct , we
cannot say if fault happened or not ’)
19 return None
20 else :
21 if brake_to_create_correct_len == 0:
22 print ( ’ invalid input automata ’)
23 return None
24 elif brake_to_create_correct_len == 1:
25 print ( ’ we can say that fault happened , and where it
is happened : ’ , brake_to_create_correct )
26 return True
27 else :
28 print ( ’ we can say that fault happened , but no

38
 information about where it could be ( more than 1
correct broken automata found ) : ’ ,
brake_to_create_correct )
29 return True

Листинг 9: Тестирование автомата

39