Файл: Методические указания к решению задач по дисциплине Теория автоматов и алгоритмические языки.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 122
Скачиваний: 13
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
23
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Автомат Мили
, в котором выделено одно состояние, с которого он всегда начинает работу, называется инициальным автоматом.
Если алфавит выхода автомата (детерминированного или нет) состоит из единственной буквы, то такой автомат называется автоматом без выхода.
В автомате Мили
функции
и
можно рассматривать как бинарные многосортные алгебраические бинарные операции с сигнатурой
и
, соответственно.
Следовательно, в этом случае для
a
A
и
v V
можно использовать обозначения:
( , )
;
( , )
a v
a v
a v
a v
(1)
Кроме того, для обозначения автомата Мили
можно использовать выражение
( , , , , )
A B V
В рамках обозначений (1) работу автомата Мили
( , , , , )
A B V
можно описать следующим образом. Эта работа осуществляется потактово. Если в начальный такт работы автомат
находился в состоянии
(0)
v
V
и на его вход поступила буква
(0)
b
A
, то он переходит в состояние
(1)
(0)
(0)
v
a
v
и на его выходе появляется буква
(1)
(0)
(0)
b
a
v
. Если автомат
на текущем такте
t
находился в состоянии
( )
v t
V
и на его вход поступила буква
( )
a t
A
, то он переходит в состояние
(
1)
( )
( )
v t
a t
v t
и на его выходе появляется буква b(t +1)= a(t)• v(t) . Такая потактовая работа автомата
описывается уравнениями:
(
1)
(t)
(t);
( )
( ).
v t
b
v
b(t +1) b t
v t
(2)
Уравнения (2) называются каноническими уравнениями автомата
. Таким образом, если автомат
в начале работы находился в состоянии
(0)
v
V
и на его вход последовательно поступали буквы
(0), (1),..., (
1)
b
b
b t
A
, то он переходит в состояние
( )
v t
V
и на его выходе последовательно появляются буквы
(1),..., ( )
c
c t
B
. Поэтому функции
и
(операции
и
) можно расширить до отображений
: A
V
V
и
: A
V
B
, полагая, что для слова
(0) (1)... (
1)
x
b
b
b t
A
и состояния
(0)
v
v
V
справедливы равенства:
( , )
( )
x v
x v v t
и
( , )
(1)... ( )
x v
x v c
c t
. Такое определение можно описать следующим индуктивным образом.
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
Определение 4.1. В автомате Мили
( , , , , )
( , , , , )
A B V
A B V
для любого его состояния
v V
и пустого слова
, по определению, полагается, что
( , )
v
v v
и
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
24
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
( , )
v
v
. Если для слова x A
и состояния
v V
уже определены значения
( , )
x v
x v
и
( , )
x v
x v
, то, по определению, для буквы
a
A
полагается, что:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
a v
x
a
v
a
x v
a
x v
x
a v
x
a
v
x v
a
x v
x v
a
x v
►
(3)
Для определѐнных в (3) отображений
: A
V
V
и
: A
V
B
(операций
и
) справедлив следующий результат, легко выводимый из соотношений (3).
Теорема 4.1. Для любого состояния
v V
автомата Мили
( , , , , )
( , , , , )
A B V
A B V
и слов ,
x y
A
справедливы равенства:
(
, )
(
)
( ,
( , ))
(
);
(
, )
(
)
( , )
( ,
( , ))
(
)
(
(
)).
x
y v
x
y
v
y
x v
y
x v
x
y v
x
y
v
x v
y
x v
x v
y
x v
►
4.1. Способы задания конечных автоматов Мили
Для использования в компьютерной практике автоматов необходимо предложить способы их задания, которые были бы удобны для их теоретического анализа и реализации на компьютере. Такие способы задания и рассматриваются в настоящем разделе на соответствующих наглядных примерах.
Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечный автомат Мили
( , , , , )
A B V
, где
1 2
,
V
v v
– словарь его состояний,
, ,
A
a b c
и
0,1
B
– алфавиты его входа и выхода, соответственно. Его функции перехода по состояниям
: A V
V
и выхода
: A V
B
имеют вид:
1 2
1 1
1 2
2 1
2 2
2 1
1 1
1 2
2 2
( , )
, ( , )
, ( , )
, ( ,
)
, ( ,
)
, ( ,
)
;
( , ) 1, ( , ) 1, ( , ) 1, ( ,
)
0, ( ,
)
0, ( ,
)
0.
a v
v
b v
v
c v
v
a v
v
b v
v
c v
v
a v
b v
c v
a v
b v
c v
Работа такого автомата Мили
( , , , , )
A B V
определяется таблицей:
a
b
c
1
v
2
,1
v
1
, 1
v
2
, 0
v
2
v
1
, 0
v
2
, 0
v
1
,1
v
25
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такая таблица удобна для еѐ использования в компьютерной программе.►
Пример 4.2 (графический способ представление автомата его диаграммой).
Работа автомата Мили
( , , , , )
A B V
из примера 4.1 наглядно представляется в виде его диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она является диаграммой мульти-орграфа, который можно задавать с помощью набора матриц смежности, индуцирующих соответствующий набор его бинарных отношений.►
Рис.10 Рис.11
Пример 4.3. На рис. 11 представлена диаграмма конечного автомата Мили
( , , , , )
A B V
, реализующего
двоичный
сумматор, в котором:
0 0 1 1
, , ,
, B
0,1 , V=
0 1 0 1
A
. Протокол работы этого автомата на входное слово
0 1 0 1 1 0 1 0 1 1 0 1 0 1
имеет вид:
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 0
1 1
0 0
0
состояния
вход
выход
.►
4.2. Минимизация конечного автомата Мили по состояниям
В силу
определения
4.1, каждое состояние
v V
автомата
Мили
( , , , , )
( , , , , )
A B V
A B V
индуцирует отображение
:
v
A
B
, для которого:
( , )
( )
v
x v
x v
x
, если
x A
(4)
26
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Такое отображение
:
v
A
B
называется
автоматным
отображением, индуцированным состоянием
v V
автомата
Определение 4.2 (автоматно-эквивалентных состояний, приведѐнного автомата). Пусть
( , ,
, , )
( , ,
, , )
A B W
A B W
– ещѐ один автомат Мили с той же сигнатурой алгебраических операций, что и автомат Мили
. Для этого автомата не исключается и ситуация, когда
. Как и для автомата
, для автомата
, его состояния
w W
и буквы
a
A
используются обозначения:
( , )
;
( , )
a w
a w
a w
a w
(5)
Если состояния
v V
и
w W
автоматов
и
таковы, что автоматные отображения
:
v
A
B
и
:
w
A
B
совпадают, т.е.
v
w
, то состояния
v V
и
w W
называются автоматно-эквивалентными состояниями и используется обозначение:
a
v
w
. Если в автомате
для каждого его состояния нет других состояний, ему автоматно-эквивалентных, то автомат
называется приведѐнным автоматом.►
Лемма 4.1. В автомате
отношение автоматной эквивалентности на совокупности его состояний является бинарным отношением эквивалентности, разбивающее совокупность его состояний на непересекающиеся классы автоматно-эквивалентных состояний.►
Замечание 4.1(об автоматной эквивалентности). Минимизировать автомат
по состояниям это значит создать такой приведенный автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, что для каждого состояния автомата
в автомате
есть автоматно-эквивалентное ему состояние и, наоборот. Следовательно, такой приведѐнный автомат
имеет тот же набор автоматных отображений, что и автомат
, т.е.
:
:
w
v
w W
v V
, но в автомате
нет автоматно-эквивалентных состояний.►
Лемма 4.2(о конгруэнтности автоматной эквивалентности). Если состояния
1 2
,
v v
V
автомата
автоматно-эквивалентны, т.е.
1 2
a
v
v
, то для любой любого слова x A
состояния
1 1
( , )
x v
x v
и
2 2
( ,
)
x v
x v
также автоматно-эвивалентны, т.е.
1 2
a
x v
x v
.►
27
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состояния автомата
переходят в автоматно-эквивалентные. Следовательно, можно корректно определить автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
, в котором совокупность состояний
a
W
V
состоит из классов автоматной эквивалентности состояний автомата
и функции
и
для входной буквы
a
A
и состояния
a
a
v
W
V
(
a
v – класс автоматной эквивалентности с представителем v V
) принимают значения:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Такой автомат
( , ,
, , )
( , ,
, , )
A B W
A B W
будет приведенным, для него используется обозначение:
a
, и он называется фактор-автоматом для автомата
относительно автоматной эквивалентности состояний автомата
. Поскольку такой фактор-автомат
a
является приведѐнным, этот автомат можно рассматривать в качестве результата решения задачи минимизации автомата
по состояниям.►
4.3 Алгоритм минимизации конечного автомата Мили по состояниям
Для конечного автомата
( , , , , )
( , , , , )
A B V
A B V
алгоритм его минимизации формулируется следующим образом.
Первый шаг. На совокупности состояний
V
вводим автомата
отношение эквивалентности
e
, полагая, что
1 2
1 2
(
(
))
e
v
v
a
A
a v
a v
. Это отношение индуцирует разбиение
совокупности состояний
V
на классы
e
-эквивалентности вида:
1
( )
(
,...,
)
k
Второй шаг. Для компоненты
j
, где
1, ( )
j
k
, вводим отношение эквивалентности , полагая, что состояния
1 2
,
j
v v
-эквивалентны только в том случае, когда для любой буквы a A
состояния
1
a v
и
2
a v
принадлежат некоторой одной компоненте разбиения
, зависящей от буквы a A
. Тем самым индуцируется разбиение
( )
j
компоненты
j
на классы
-эквивалентности. В результате образуется разбиение
(1)
( ( ))
(
,...,
)
k
совокупности
V
28
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Третий шаг. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим ко второму шагу алгоритма. Если
, то присваиваем разбиению
значение разбиения
(
:
) и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
Замечание 4.3. Поскольку автомат
конечен, описанный выше алгоритм результативен.►
Пример 4.4. Конечный автомат Мили
(
, ,
,
, ,
, 1, 2,3, 4,5, 6, 7,8 , , )
A B C
A B C
задан
таблицей 1. В этом автомате входной и выходной алфавиты совпадают и имеют вид:
, ,
A B C
. Кроме того,
1, 2,3, 4,5, 6, 7,8
V
– словарь его состояний.
Таблица 1
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Далее для минимизации рассматриваемого автомата
по состояниям применяется указанный выше алгоритм минимизации.
Первый шаг. Отношение эквивалентности
e
индуцирует разбиение
1 2
(
,
)
совокупность состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
на классы
e
-эквивалентности
1 1, 2, 4,5
и
2 3, 6, 7,8
, в каждом из которых буква выхода автомата определяется входной буквой, не зависящей от состояния автомата из рассматриваемого класса эквивалентности. Таблица 2 иллюстрирует полученное разбиение
1 2
(
,
)
29
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Таблица 2
A
B
C
1 3
B
4
C
7
A
1
2 3
B
5
C
6
A
4 6
B
1
C
7
A
5 3
B
5
C
8
A
3 1
A
2
B
5
C
2
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Второй шаг. Отношение эквивалентности индуцирует разбиения
(1)
1
(
)
и
(2)
2 3
(
,
)
на каждом из классов
1 1, 2, 4,5
и
2 3, 6, 7,8
, соответственно, где в каждом из классов
1 1, 2, 4,5
,
2 3, 6
и
3 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
, или
2
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 3
A
B
C
П
1
2
1
2
П
1 2
2
1
2 4
2
1
2 5
2
1
2 3
1
1
1
П
2 6
1
1
1 7
1
2
1
П
3 8
1
2
1
Таким образом, на втором шаге алгоритмы индуцируется разбиение
2 2
3
(
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3
(
,
,
)
. Следовательно, полагаем, что
1 2
3
( ,
,
)
, где
1 1
,
2 2
и
3 3
, и повторяем второй шаг алгоритма.
Второй
шаг.
Отношение эквивалентности
индуцирует разбиения
(1)
1 2
(
,
)
,
(2)
3
(
)
и
(3)
4
(
)
на каждом классов
1 1, 2, 4,5
,
2 3, 6
и
30
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
или
3
, зависящего только от этой входной буквы. Таблица 4 иллюстрирует эти переходы.
Таблица 4.
А
В
С
П
2
2
1
2
П
1 1
2
1
3
П
2 4
2
1
3 5
2
1
3 3
1
1
1
П
3 6
1
1
1 7
1
2
1
П
4 8
1
2
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Третий шаг. Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
Следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и повторяем
1 2 3 4 5 6
второй шаг алгоритма.
Второй шаг. Отношение эквивалентности
индуцирует разбиения
(1)
1
(
)
,
(2)
2
(
)
,
(3)
3
(
)
и
(4)
4
(
)
на каждом классов
1 2
,
2 1, 4,5
,
3 3, 6
и
4 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
,
3
или
4
, зависящего только от этой входной буквы. Таблица 5 иллюстрирует эти переходы.
Таблица 5.
А
В
С
П
2
3
2
3
П
1 1
3
2
4
П
2 4
3
2
4
31
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5
3
2
4 3
2
1
2
П
3 6
2
1
2 7
2
3
1
П
4 8
2
3
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
, следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
(
1, 4
j
) из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
, работу которого иллюстрирует Таблица 6.
Таблица 6
A
B
C
1
3
B
2
C
3
A
2
3
B
2
C
4
A
3
2
A
1
B
2
C
4
2
A
3
B
1
C
Согласно таблицам 1 и 6, иллюстрирующим работу автоматов
и
a
настоящего примера, соответственно, на входное слово
AABCCABBC
эти автоматы, начиная с начальных состояний
1 V
и
2
(
2 1
и
2 1, 4, 5
a
), отвечают одинаковым выходным словом
BACACBBCA
. Аналогично подтверждается автоматная эквивалентность и других состояний автоматов
и
a
(
1 2
a
,
3 3, 6
a
и
4 7,8
a
).►
32
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5. Дискретные преобразователи
К одним из простейших конечных детерминированных автоматов относятся дискретные преобразователи, т.е. конечные автоматы Мили с одним состоянием. Анализу и синтезу таких дискретных преобразователей и посвящѐн настоящий раздел. Важность дискретных преобразователей обусловлена тем, что на их основе разрабатываются принципы синтеза конечных детерминированных автоматов. К типу дискретных преобразователей относятся логические схемы из функциональных элементов и контактные (переключательные) схемы.
Диаграммы логических схем из функциональных элементов и контактных
(переключательных) схем строятся на основе орграфов, называемых логическими и контактными сетями, соответственно. Кроме того, анализ контактной схемы осуществляется на основе специального орграфа, называемого деревом анализа контактной схемы. Краткое изложение теории графов, необходимое для описания логических и контактных сетей приведено в разделе 3.
5.1. Логические схемы из функциональных элементов
Логическая схема из функциональных элементов реализует дискретный преобразователь, поскольку она является автоматом с одним состоянием. Входным алфавитом такой логической схемы является словарь
n -мерных булевых кортежей
2 1
1 2
,...,
:
,...,
0,1 }
n
n
n
A
, где
2
( 0,1 ,
, , , 0,1 )
– стандартная булева алгебра (булев 1-куб). Алфавит еѐ выхода
2
B
Диаграммой логической схемы представляется в виде логической сети (см.
определение 3.3) с n источниками и одним стоком. Каждый из n источников логической сети помечен одной из булевых переменных
1
,....,
n
x
x так, что эти пометки попарно различны для разных источников. Каждая из остальных вершин этой сети помечена одним из логических функциональных знаков:
,
,
,
. При этом вершины, помеченные знаком дизъюнкции
(конъюнкции
), имеют позитивную валентность, равную двум; вершины, помеченные знаком логического отрицания
(равенства
), имеют единичную позитивную валентность. Пометки вершин диаграммы логической схемы, иллюстрируют работу этой схемы. На первом такте работы схемы на еѐ вход подаѐтся булев n -мерный кортеж
1 2
,...,
n
n
и булевым переменным, помечающим источники сети
33
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев логической схемы, присваиваются значения:
1 1
,....,
n
n
x
x
. Пометки других вершин диаграммы иллюстрируют работу функциональных элементов логической схемы: дизъюнктора (помечен знаком
), конъюнктора (помечен знаком
), инвертора (помечен знаком
) и дублятора-задержки (помечен знаком
).
С помощью диаграммы логической схемы описывается еѐ работа по реализации булевой функции
1 2
2
( ,....,
) :
n
n
f
f x
x
, называемой пропускной способностью этой логической схемы.
На рис. 12 для логической схемы с тремя источниками на примере еѐ диаграммы проиллюстрирована потактовая работа этой схемы, реализующей булеву функцию
1 2
2 3
(
)
f
x
x
x x
Рис.12
Замечание 5.1. Логическая схема из функциональных элементов, диаграмма которой приведена на рис. 12, работает потактово. Для соблюдения этого требования на этой диаграмме указан дублятор, иллюстрирующий задержку на один такт работы в этом функциональном элементе схемы. Кроме того, диаграмма на рис. 12 иллюстрирует методы анализа и синтеза логической схемы из функциональных элементов.►
Пример 5.1. В настоящем примере демонстрируется описание канонических уравнений конечного автомата Мили на основе булевых функций, с помощью которых работу автомата возможно реализовать логическими схемами из функциональных элементов. Для этого рассмотрим автомат
( , , , , )
A B V
, в котором
1 2
3 4
,
, ,
V
v v v v
– словарь его состояний и, кроме того, алфавиты входа и выхода совпадают и имеют вид:
,
A
a b
B
Работу этого автомата описывает таблица 7.
Таблица 7
34
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
a
b
1
v
3
v
a
4
v
b
2
v
1
v
b
2
v
a
3
v
1
v
a
1
v
b
4
v
2
v
b
3
v
a
Сменим обозначения состояний и букв алфавита входа и выхода автомата
( , , , , )
A B V
следующим образом. Буквы a и
b
заменим на символы
0
и
1, соответственно, получив в качестве алфавитов входа и выхода алфавиты
1 1
,
A
a b
B
Словарь
1 2
3 4
,
, ,
V
v v v v
состояний автомата
( , , , , )
A B V
заменим на соответствующий словарь
1
(0, 0), (0,1), (1, 0), (1,1)
V
. В результате получится автомат
1 1
1 1
(
,
, , , )
A B V
, фактически, реализующий автомат
( , , , , )
A B V
, если работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается, в соответствии с таблицей 7, таблицей 8.
Таблица 8
1
A
1
V
1
x
2
x
3
x
1
2
0 0
0 1
0 0
0 0
1 0
0 1
0 1
0 0
0 0
0 1
1 0
1 1
1 0
0 1
1 1
1 0
1 0
1 0
1 1
0 0
0 1
1 1
1 1
0 0
Таким образом, работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается двумерной булевой функцией перехода по состояниям
1 2
3 1
1 2
3 2
1 2
3
( ,
,
)
( ( ,
,
),
( ,
,
))
x x x
x x x
x x x
и булевой функцией
1 2
3
( ,
,
)
x x x
, которые определены таблицей 8. Из таблицы 8 получаем:
1 1 2 3 1 2 3 1 2 3 1 2 3 2 3
x x x
x x x
x x x
x x x
x x
,
2 1 2 3 1 2 3 1 2 3 1 2 1 2 3
x x x
x x x
x x x
x x
x x x
,
1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 3
x x x
x x x
x x x
x x x
x x
x x
35
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Следовательно, автомат
( , , , , )
A B V
с помощью автомата
1 1
1 1
(
,
, , , )
A B V
можно синтезировать, используя логические схемы из функциональных элементов.►
Упражнение 5.1. Синтезировать работу автомата
1 1
1 1
(
,
, , , )
A B V
из примера 5.1 с помощью логических схем из функциональных элементов, построив для этого соответствующие диаграммы логических схем.►
5.2. Контактные схемы
Пусть
( ;
, )
Gr V
q e
– контактная сеть (см. определение 3.4) и
1 1
2 2
( , ,
,
,...,
,
)
n
n
x x x x
x x
– список булевых переменных и их отрицаний. Как и ранее,
( ; )
R V
– совокупность рѐбер сети
( ;
, )
Gr V
q e
и задано отображение
: ( , )
R V
. Тогда говорят, что определена
контактная (переключательная) схема
( ;
, )
Gr V
q e
Рассмотрим совокупность путей
( ; )
q e
в сети
( ;
, )
Gr V
q e
с началом во входной вершине
q V
и с окончанием в заключительной вершине e V
. Путь
( , )
q e
представляем в виде списка его последовательных ребер:
1 1
2 2
1 1
({ , },{ , },...,{
,
},{
, })
k
k
k
q v
v v
v
v
v
e
Такому пути
поставим в соответствие конъюнкцию:
1 1
2 1
2 1
2
( )
({ , }) ({ , })... ({
, })
[ ,
,...,
]
k
n
q v
v v
v
e
x x
x
, где
2 1
[ ,...,
]
n
x
x – булева алгебра булевых функций от
n булевых переменных
1
,...,
n
x
x
Тем самым, отображение
расширяется до отображения
2 1
2
:
( , )
[ ,
,...,
]
n
q e
x x
x
Определение 5.1 Пропускной способностью контактной схемы
( ;
, )
Gr V
q e
называется булева функция
2 1
[ ,...,
]
n
f
x
x
вида
( , )
( )
q e
f
.►
Но, для того чтобы, согласно определению 5.1, вычислить пропускную способность
( , )
( )
q e
f
контактной схемы
( ;
, )
Gr V
q e
, необходимо рассмотреть бесконечную совокупность путей
( , )
q e
. Оказывается, что для вычисления этой пропускной способности достаточно ограничиться подсовокупностью
0
( , )
q e
– простых путей
36
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
(путей, не содержащих циклы) среди путей совокупности
( , )
q e
. Совокупность
0
( , )
q e
, вследствие конечности контактной схемы, также является конечной и допускает, как будет показано далее, алгоритм еѐ перебора без повторений.
Теорема 5.1 (о вычислении пропускной способности контактной схемы). Пропускная способность контактной схемы
( ;
, )
Gr V
q e
вычисляется согласно формуле:
0
( , )
( )
q e
f
.►
На практике возникает и другая задача. По заданной пропускной способности создать контактную схему, еѐ реализующую. Такая задача называется задачей синтеза
контактной схемы.
Пример 5.2 (плоско-параллельной контактной схемы). Требуется синтезировать контактную схему с пропускной способностью
1 2
3 1
2 3
1 2
3 2
1 2
3
[ ,
,
]
f
x x x
x x x
x x x
x x x
На рис. 13 показана диаграмма контактной схемы с такой пропускной способностью. Эта схема называется плоско-параллельной.►
Рис.13
Рис.14
Для любой булевой функции, представленной еѐ дизъюнктивной нормальной формой
(ДНФ), в частности, – совершенной дизъюнктивной нормальной формой (СДНФ), плоско- параллельная контактная схема легко конструируется. Однако, такая контактная схема, как правило, не является оптимальной с точки зрения минимизации количества еѐ вершин и рѐбер. Более оптимальным синтезом контактной схемы является метод каскадов, изложению которого посвящѐн следующий раздел.
37
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5.2.1. Синтез контактной схемы методом каскадов
Метод каскадов для синтеза неизвестной контактной схемы с заданной пропускной способности осуществляется индуктивно.
Пусть
2 1
[ ,...,
]
n
f
x
x
– пропускная способность неизвестной контактной схемы
( ;
, )
Gr V
q e
, которую необходимо построить.
Далее предполагается, что функция
f
представлена полиномом Жегалкина, зависящим от всех булевых переменных
1
x ,
2
x , …,
n
x . Тогда алгоритм метода каскадов для синтеза неизвестной контактной схемы
( ;
, )
Gr V
q e
имеет следующий вид.
Первый шаг. Создаем входную вершину
q V
и две другие различные вершины
1 2
,
v v
V
. Новому ребру
1
{ , }
( , )
q v
R V
ставим в соответствие перемененную
1
x , новому ребру
2
{ , }
( , )
q v
R V
– переменную
1
x
. После этого вершину
1
v
помечаем полиномом
Жегалкина функции
1 2
2 1
( ,...,
)
(1,
,...,
)
n
n
f x
x
f
x
x
p
, вершину
2
v – полиномом Жегалкина функции
0 2
2 2
( ,...,
)
(0,
,...,
)
n
n
f x
x
f
x
x
p
. Если
1 0
p
(
2 0
p
), то вершину
1
v
(
2
v ) и входящее в неѐ новое ребро уничтожаем. Если
1 1
p
(
2 1
p
), то вершину
1
v
(
2
v ) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
v
e
(
2
v
e
).
…………………………………………………………………………………………
Текущий шаг. Пусть для переменных
1 1
1 1
,
,...,
,
k
k
x x
x
x
, построена часть схемы
( ;
, )
Gr V
q e
, в которой есть вершина v V
, помеченная полиномом Жегалкина
p
от переменных
,...,
k
n
x
x
и зависящим от переменной
k
x – существенно. Тогда для вершины
v создаем две новые вершины
1 2
,
w w
V
. Новое ребро
1
{ ,
}
( ; )
v w
R v
помечаем переменной
k
x , новое ребро
2
{ ,
}
v w – переменной
k
x . Кроме того, вершину
1
w (
2
w
) помечаем полиномом
1
p (
2
p
), полученным подстановкой в переменную
k
x полинома
p
числа
1
(числа
0
). Если оказалось, что
1 0
p
(
2 0
p
), то вершину
1
w (
2
w
) и входящее в неѐ новое ребро уничтожаем. Если же
1 1
p
(
2 1
p
), то вершину
1
w (
2
w
) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
w
e
(
2
w
e
). Кроме того, если среди уже ранее построенных вершин есть такая вершина w , что
1
p
q
(
2
p
q
), где q –
38
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев полином, помечающий вершину w , то в этом случае вершину
1
w (
2
w
) отождествляем вершиной w , т.е. полагаем
1
w
w
(
2
w
w
).
…………………………………………………………………………………………
1 2 3 4 5 6
второй шаг алгоритма.
Второй шаг. Отношение эквивалентности
индуцирует разбиения
(1)
1
(
)
,
(2)
2
(
)
,
(3)
3
(
)
и
(4)
4
(
)
на каждом классов
1 2
,
2 1, 4,5
,
3 3, 6
и
4 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
,
3
или
4
, зависящего только от этой входной буквы. Таблица 5 иллюстрирует эти переходы.
Таблица 5.
А
В
С
П
2
3
2
3
П
1 1
3
2
4
П
2 4
3
2
4
31
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5
3
2
4 3
2
1
2
П
3 6
2
1
2 7
2
3
1
П
4 8
2
3
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
, следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
(
1, 4
j
) из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
, работу которого иллюстрирует Таблица 6.
Таблица 6
A
B
C
1
3
B
2
C
3
A
2
3
B
2
C
4
A
3
2
A
1
B
2
C
4
2
A
3
B
1
C
Согласно таблицам 1 и 6, иллюстрирующим работу автоматов
и
a
настоящего примера, соответственно, на входное слово
AABCCABBC
эти автоматы, начиная с начальных состояний
1 V
и
2
(
2 1
и
2 1, 4, 5
a
), отвечают одинаковым выходным словом
BACACBBCA
. Аналогично подтверждается автоматная эквивалентность и других состояний автоматов
и
a
(
1 2
a
,
3 3, 6
a
и
4 7,8
a
).►
32
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5. Дискретные преобразователи
К одним из простейших конечных детерминированных автоматов относятся дискретные преобразователи, т.е. конечные автоматы Мили с одним состоянием. Анализу и синтезу таких дискретных преобразователей и посвящѐн настоящий раздел. Важность дискретных преобразователей обусловлена тем, что на их основе разрабатываются принципы синтеза конечных детерминированных автоматов. К типу дискретных преобразователей относятся логические схемы из функциональных элементов и контактные (переключательные) схемы.
Диаграммы логических схем из функциональных элементов и контактных
(переключательных) схем строятся на основе орграфов, называемых логическими и контактными сетями, соответственно. Кроме того, анализ контактной схемы осуществляется на основе специального орграфа, называемого деревом анализа контактной схемы. Краткое изложение теории графов, необходимое для описания логических и контактных сетей приведено в разделе 3.
5.1. Логические схемы из функциональных элементов
Логическая схема из функциональных элементов реализует дискретный преобразователь, поскольку она является автоматом с одним состоянием. Входным алфавитом такой логической схемы является словарь
n -мерных булевых кортежей
2 1
1 2
,...,
:
,...,
0,1 }
n
n
n
A
, где
2
( 0,1 ,
, , , 0,1 )
– стандартная булева алгебра (булев 1-куб). Алфавит еѐ выхода
2
B
Диаграммой логической схемы представляется в виде логической сети (см.
определение 3.3) с n источниками и одним стоком. Каждый из n источников логической сети помечен одной из булевых переменных
1
,....,
n
x
x так, что эти пометки попарно различны для разных источников. Каждая из остальных вершин этой сети помечена одним из логических функциональных знаков:
,
,
,
. При этом вершины, помеченные знаком дизъюнкции
(конъюнкции
), имеют позитивную валентность, равную двум; вершины, помеченные знаком логического отрицания
(равенства
), имеют единичную позитивную валентность. Пометки вершин диаграммы логической схемы, иллюстрируют работу этой схемы. На первом такте работы схемы на еѐ вход подаѐтся булев n -мерный кортеж
1 2
,...,
n
n
и булевым переменным, помечающим источники сети
33
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев логической схемы, присваиваются значения:
1 1
,....,
n
n
x
x
. Пометки других вершин диаграммы иллюстрируют работу функциональных элементов логической схемы: дизъюнктора (помечен знаком
), конъюнктора (помечен знаком
), инвертора (помечен знаком
) и дублятора-задержки (помечен знаком
).
С помощью диаграммы логической схемы описывается еѐ работа по реализации булевой функции
1 2
2
( ,....,
) :
n
n
f
f x
x
, называемой пропускной способностью этой логической схемы.
На рис. 12 для логической схемы с тремя источниками на примере еѐ диаграммы проиллюстрирована потактовая работа этой схемы, реализующей булеву функцию
1 2
2 3
(
)
f
x
x
x x
Рис.12
Замечание 5.1. Логическая схема из функциональных элементов, диаграмма которой приведена на рис. 12, работает потактово. Для соблюдения этого требования на этой диаграмме указан дублятор, иллюстрирующий задержку на один такт работы в этом функциональном элементе схемы. Кроме того, диаграмма на рис. 12 иллюстрирует методы анализа и синтеза логической схемы из функциональных элементов.►
Пример 5.1. В настоящем примере демонстрируется описание канонических уравнений конечного автомата Мили на основе булевых функций, с помощью которых работу автомата возможно реализовать логическими схемами из функциональных элементов. Для этого рассмотрим автомат
( , , , , )
A B V
, в котором
1 2
3 4
,
, ,
V
v v v v
– словарь его состояний и, кроме того, алфавиты входа и выхода совпадают и имеют вид:
,
A
a b
B
Работу этого автомата описывает таблица 7.
Таблица 7
34
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
a
b
1
v
3
v
a
4
v
b
2
v
1
v
b
2
v
a
3
v
1
v
a
1
v
b
4
v
2
v
b
3
v
a
Сменим обозначения состояний и букв алфавита входа и выхода автомата
( , , , , )
A B V
следующим образом. Буквы a и
b
заменим на символы
0
и
1, соответственно, получив в качестве алфавитов входа и выхода алфавиты
1 1
,
A
a b
B
Словарь
1 2
3 4
,
, ,
V
v v v v
состояний автомата
( , , , , )
A B V
заменим на соответствующий словарь
1
(0, 0), (0,1), (1, 0), (1,1)
V
. В результате получится автомат
1 1
1 1
(
,
, , , )
A B V
, фактически, реализующий автомат
( , , , , )
A B V
, если работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается, в соответствии с таблицей 7, таблицей 8.
Таблица 8
1
A
1
V
1
x
2
x
3
x
1
2
0 0
0 1
0 0
0 0
1 0
0 1
0 1
0 0
0 0
0 1
1 0
1 1
1 0
0 1
1 1
1 0
1 0
1 0
1 1
0 0
0 1
1 1
1 1
0 0
Таким образом, работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается двумерной булевой функцией перехода по состояниям
1 2
3 1
1 2
3 2
1 2
3
( ,
,
)
( ( ,
,
),
( ,
,
))
x x x
x x x
x x x
и булевой функцией
1 2
3
( ,
,
)
x x x
, которые определены таблицей 8. Из таблицы 8 получаем:
1 1 2 3 1 2 3 1 2 3 1 2 3 2 3
x x x
x x x
x x x
x x x
x x
,
2 1 2 3 1 2 3 1 2 3 1 2 1 2 3
x x x
x x x
x x x
x x
x x x
,
1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 3
x x x
x x x
x x x
x x x
x x
x x
35
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Следовательно, автомат
( , , , , )
A B V
с помощью автомата
1 1
1 1
(
,
, , , )
A B V
можно синтезировать, используя логические схемы из функциональных элементов.►
Упражнение 5.1. Синтезировать работу автомата
1 1
1 1
(
,
, , , )
A B V
из примера 5.1 с помощью логических схем из функциональных элементов, построив для этого соответствующие диаграммы логических схем.►
5.2. Контактные схемы
Пусть
( ;
, )
Gr V
q e
– контактная сеть (см. определение 3.4) и
1 1
2 2
( , ,
,
,...,
,
)
n
n
x x x x
x x
– список булевых переменных и их отрицаний. Как и ранее,
( ; )
R V
– совокупность рѐбер сети
( ;
, )
Gr V
q e
и задано отображение
: ( , )
R V
. Тогда говорят, что определена
контактная (переключательная) схема
( ;
, )
Gr V
q e
Рассмотрим совокупность путей
( ; )
q e
в сети
( ;
, )
Gr V
q e
с началом во входной вершине
q V
и с окончанием в заключительной вершине e V
. Путь
( , )
q e
представляем в виде списка его последовательных ребер:
1 1
2 2
1 1
({ , },{ , },...,{
,
},{
, })
k
k
k
q v
v v
v
v
v
e
Такому пути
поставим в соответствие конъюнкцию:
1 1
2 1
2 1
2
( )
({ , }) ({ , })... ({
, })
[ ,
,...,
]
k
n
q v
v v
v
e
x x
x
, где
2 1
[ ,...,
]
n
x
x – булева алгебра булевых функций от
n булевых переменных
1
,...,
n
x
x
Тем самым, отображение
расширяется до отображения
2 1
2
:
( , )
[ ,
,...,
]
n
q e
x x
x
Определение 5.1 Пропускной способностью контактной схемы
( ;
, )
Gr V
q e
называется булева функция
2 1
[ ,...,
]
n
f
x
x
вида
( , )
( )
q e
f
.►
Но, для того чтобы, согласно определению 5.1, вычислить пропускную способность
( , )
( )
q e
f
контактной схемы
( ;
, )
Gr V
q e
, необходимо рассмотреть бесконечную совокупность путей
( , )
q e
. Оказывается, что для вычисления этой пропускной способности достаточно ограничиться подсовокупностью
0
( , )
q e
– простых путей
36
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
(путей, не содержащих циклы) среди путей совокупности
( , )
q e
. Совокупность
0
( , )
q e
, вследствие конечности контактной схемы, также является конечной и допускает, как будет показано далее, алгоритм еѐ перебора без повторений.
Теорема 5.1 (о вычислении пропускной способности контактной схемы). Пропускная способность контактной схемы
( ;
, )
Gr V
q e
вычисляется согласно формуле:
0
( , )
( )
q e
f
.►
На практике возникает и другая задача. По заданной пропускной способности создать контактную схему, еѐ реализующую. Такая задача называется задачей синтеза
контактной схемы.
Пример 5.2 (плоско-параллельной контактной схемы). Требуется синтезировать контактную схему с пропускной способностью
1 2
3 1
2 3
1 2
3 2
1 2
3
[ ,
,
]
f
x x x
x x x
x x x
x x x
На рис. 13 показана диаграмма контактной схемы с такой пропускной способностью. Эта схема называется плоско-параллельной.►
Рис.13
Рис.14
Для любой булевой функции, представленной еѐ дизъюнктивной нормальной формой
(ДНФ), в частности, – совершенной дизъюнктивной нормальной формой (СДНФ), плоско- параллельная контактная схема легко конструируется. Однако, такая контактная схема, как правило, не является оптимальной с точки зрения минимизации количества еѐ вершин и рѐбер. Более оптимальным синтезом контактной схемы является метод каскадов, изложению которого посвящѐн следующий раздел.
37
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5.2.1. Синтез контактной схемы методом каскадов
Метод каскадов для синтеза неизвестной контактной схемы с заданной пропускной способности осуществляется индуктивно.
Пусть
2 1
[ ,...,
]
n
f
x
x
– пропускная способность неизвестной контактной схемы
( ;
, )
Gr V
q e
, которую необходимо построить.
Далее предполагается, что функция
f
представлена полиномом Жегалкина, зависящим от всех булевых переменных
1
x ,
2
x , …,
n
x . Тогда алгоритм метода каскадов для синтеза неизвестной контактной схемы
( ;
, )
Gr V
q e
имеет следующий вид.
Первый шаг. Создаем входную вершину
q V
и две другие различные вершины
1 2
,
v v
V
. Новому ребру
1
{ , }
( , )
q v
R V
ставим в соответствие перемененную
1
x , новому ребру
2
{ , }
( , )
q v
R V
– переменную
1
x
. После этого вершину
1
v
помечаем полиномом
Жегалкина функции
1 2
2 1
( ,...,
)
(1,
,...,
)
n
n
f x
x
f
x
x
p
, вершину
2
v – полиномом Жегалкина функции
0 2
2 2
( ,...,
)
(0,
,...,
)
n
n
f x
x
f
x
x
p
. Если
1 0
p
(
2 0
p
), то вершину
1
v
(
2
v ) и входящее в неѐ новое ребро уничтожаем. Если
1 1
p
(
2 1
p
), то вершину
1
v
(
2
v ) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
v
e
(
2
v
e
).
…………………………………………………………………………………………
Текущий шаг. Пусть для переменных
1 1
1 1
,
,...,
,
k
k
x x
x
x
, построена часть схемы
( ;
, )
Gr V
q e
, в которой есть вершина v V
, помеченная полиномом Жегалкина
p
от переменных
,...,
k
n
x
x
и зависящим от переменной
k
x – существенно. Тогда для вершины
v создаем две новые вершины
1 2
,
w w
V
. Новое ребро
1
{ ,
}
( ; )
v w
R v
помечаем переменной
k
x , новое ребро
2
{ ,
}
v w – переменной
k
x . Кроме того, вершину
1
w (
2
w
) помечаем полиномом
1
p (
2
p
), полученным подстановкой в переменную
k
x полинома
p
числа
1
(числа
0
). Если оказалось, что
1 0
p
(
2 0
p
), то вершину
1
w (
2
w
) и входящее в неѐ новое ребро уничтожаем. Если же
1 1
p
(
2 1
p
), то вершину
1
w (
2
w
) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
w
e
(
2
w
e
). Кроме того, если среди уже ранее построенных вершин есть такая вершина w , что
1
p
q
(
2
p
q
), где q –
38
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев полином, помечающий вершину w , то в этом случае вершину
1
w (
2
w
) отождествляем вершиной w , т.е. полагаем
1
w
w
(
2
w
w
).
…………………………………………………………………………………………
1 2 3 4 5 6
второй шаг алгоритма.
Второй шаг. Отношение эквивалентности
индуцирует разбиения
(1)
1
(
)
,
(2)
2
(
)
,
(3)
3
(
)
и
(4)
4
(
)
на каждом классов
1 2
,
2 1, 4,5
,
3 3, 6
и
4 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
,
3
или
4
, зависящего только от этой входной буквы. Таблица 5 иллюстрирует эти переходы.
Таблица 5.
А
В
С
П
2
3
2
3
П
1 1
3
2
4
П
2 4
3
2
4
31
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5
3
2
4 3
2
1
2
П
3 6
2
1
2 7
2
3
1
П
4 8
2
3
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
, следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
(
1, 4
j
) из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
, работу которого иллюстрирует Таблица 6.
Таблица 6
A
B
C
1
3
B
2
C
3
A
2
3
B
2
C
4
A
3
2
A
1
B
2
C
4
2
A
3
B
1
C
Согласно таблицам 1 и 6, иллюстрирующим работу автоматов
и
a
настоящего примера, соответственно, на входное слово
AABCCABBC
эти автоматы, начиная с начальных состояний
1 V
и
2
(
2 1
и
2 1, 4, 5
a
), отвечают одинаковым выходным словом
BACACBBCA
. Аналогично подтверждается автоматная эквивалентность и других состояний автоматов
и
a
(
1 2
a
,
3 3, 6
a
и
4 7,8
a
).►
32
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5. Дискретные преобразователи
К одним из простейших конечных детерминированных автоматов относятся дискретные преобразователи, т.е. конечные автоматы Мили с одним состоянием. Анализу и синтезу таких дискретных преобразователей и посвящѐн настоящий раздел. Важность дискретных преобразователей обусловлена тем, что на их основе разрабатываются принципы синтеза конечных детерминированных автоматов. К типу дискретных преобразователей относятся логические схемы из функциональных элементов и контактные (переключательные) схемы.
Диаграммы логических схем из функциональных элементов и контактных
(переключательных) схем строятся на основе орграфов, называемых логическими и контактными сетями, соответственно. Кроме того, анализ контактной схемы осуществляется на основе специального орграфа, называемого деревом анализа контактной схемы. Краткое изложение теории графов, необходимое для описания логических и контактных сетей приведено в разделе 3.
5.1. Логические схемы из функциональных элементов
Логическая схема из функциональных элементов реализует дискретный преобразователь, поскольку она является автоматом с одним состоянием. Входным алфавитом такой логической схемы является словарь
n -мерных булевых кортежей
2 1
1 2
,...,
:
,...,
0,1 }
n
n
n
A
, где
2
( 0,1 ,
, , , 0,1 )
– стандартная булева алгебра (булев 1-куб). Алфавит еѐ выхода
2
B
Диаграммой логической схемы представляется в виде логической сети (см.
определение 3.3) с n источниками и одним стоком. Каждый из n источников логической сети помечен одной из булевых переменных
1
,....,
n
x
x так, что эти пометки попарно различны для разных источников. Каждая из остальных вершин этой сети помечена одним из логических функциональных знаков:
,
,
,
. При этом вершины, помеченные знаком дизъюнкции
(конъюнкции
), имеют позитивную валентность, равную двум; вершины, помеченные знаком логического отрицания
(равенства
), имеют единичную позитивную валентность. Пометки вершин диаграммы логической схемы, иллюстрируют работу этой схемы. На первом такте работы схемы на еѐ вход подаѐтся булев n -мерный кортеж
1 2
,...,
n
n
и булевым переменным, помечающим источники сети
33
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев логической схемы, присваиваются значения:
1 1
,....,
n
n
x
x
. Пометки других вершин диаграммы иллюстрируют работу функциональных элементов логической схемы: дизъюнктора (помечен знаком
), конъюнктора (помечен знаком
), инвертора (помечен знаком
) и дублятора-задержки (помечен знаком
).
С помощью диаграммы логической схемы описывается еѐ работа по реализации булевой функции
1 2
2
( ,....,
) :
n
n
f
f x
x
, называемой пропускной способностью этой логической схемы.
На рис. 12 для логической схемы с тремя источниками на примере еѐ диаграммы проиллюстрирована потактовая работа этой схемы, реализующей булеву функцию
1 2
2 3
(
)
f
x
x
x x
Рис.12
Замечание 5.1. Логическая схема из функциональных элементов, диаграмма которой приведена на рис. 12, работает потактово. Для соблюдения этого требования на этой диаграмме указан дублятор, иллюстрирующий задержку на один такт работы в этом функциональном элементе схемы. Кроме того, диаграмма на рис. 12 иллюстрирует методы анализа и синтеза логической схемы из функциональных элементов.►
Пример 5.1. В настоящем примере демонстрируется описание канонических уравнений конечного автомата Мили на основе булевых функций, с помощью которых работу автомата возможно реализовать логическими схемами из функциональных элементов. Для этого рассмотрим автомат
( , , , , )
A B V
, в котором
1 2
3 4
,
, ,
V
v v v v
– словарь его состояний и, кроме того, алфавиты входа и выхода совпадают и имеют вид:
,
A
a b
B
Работу этого автомата описывает таблица 7.
Таблица 7
34
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
a
b
1
v
3
v
a
4
v
b
2
v
1
v
b
2
v
a
3
v
1
v
a
1
v
b
4
v
2
v
b
3
v
a
Сменим обозначения состояний и букв алфавита входа и выхода автомата
( , , , , )
A B V
следующим образом. Буквы a и
b
заменим на символы
0
и
1, соответственно, получив в качестве алфавитов входа и выхода алфавиты
1 1
,
A
a b
B
Словарь
1 2
3 4
,
, ,
V
v v v v
состояний автомата
( , , , , )
A B V
заменим на соответствующий словарь
1
(0, 0), (0,1), (1, 0), (1,1)
V
. В результате получится автомат
1 1
1 1
(
,
, , , )
A B V
, фактически, реализующий автомат
( , , , , )
A B V
, если работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается, в соответствии с таблицей 7, таблицей 8.
Таблица 8
1
A
1
V
1
x
2
x
3
x
1
2
0 0
0 1
0 0
0 0
1 0
0 1
0 1
0 0
0 0
0 1
1 0
1 1
1 0
0 1
1 1
1 0
1 0
1 0
1 1
0 0
0 1
1 1
1 1
0 0
Таким образом, работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается двумерной булевой функцией перехода по состояниям
1 2
3 1
1 2
3 2
1 2
3
( ,
,
)
( ( ,
,
),
( ,
,
))
x x x
x x x
x x x
и булевой функцией
1 2
3
( ,
,
)
x x x
, которые определены таблицей 8. Из таблицы 8 получаем:
1 1 2 3 1 2 3 1 2 3 1 2 3 2 3
x x x
x x x
x x x
x x x
x x
,
2 1 2 3 1 2 3 1 2 3 1 2 1 2 3
x x x
x x x
x x x
x x
x x x
,
1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 3
x x x
x x x
x x x
x x x
x x
x x
35
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Следовательно, автомат
( , , , , )
A B V
с помощью автомата
1 1
1 1
(
,
, , , )
A B V
можно синтезировать, используя логические схемы из функциональных элементов.►
Упражнение 5.1. Синтезировать работу автомата
1 1
1 1
(
,
, , , )
A B V
из примера 5.1 с помощью логических схем из функциональных элементов, построив для этого соответствующие диаграммы логических схем.►
5.2. Контактные схемы
Пусть
( ;
, )
Gr V
q e
– контактная сеть (см. определение 3.4) и
1 1
2 2
( , ,
,
,...,
,
)
n
n
x x x x
x x
– список булевых переменных и их отрицаний. Как и ранее,
( ; )
R V
– совокупность рѐбер сети
( ;
, )
Gr V
q e
и задано отображение
: ( , )
R V
. Тогда говорят, что определена
контактная (переключательная) схема
( ;
, )
Gr V
q e
Рассмотрим совокупность путей
( ; )
q e
в сети
( ;
, )
Gr V
q e
с началом во входной вершине
q V
и с окончанием в заключительной вершине e V
. Путь
( , )
q e
представляем в виде списка его последовательных ребер:
1 1
2 2
1 1
({ , },{ , },...,{
,
},{
, })
k
k
k
q v
v v
v
v
v
e
Такому пути
поставим в соответствие конъюнкцию:
1 1
2 1
2 1
2
( )
({ , }) ({ , })... ({
, })
[ ,
,...,
]
k
n
q v
v v
v
e
x x
x
, где
2 1
[ ,...,
]
n
x
x – булева алгебра булевых функций от
n булевых переменных
1
,...,
n
x
x
Тем самым, отображение
расширяется до отображения
2 1
2
:
( , )
[ ,
,...,
]
n
q e
x x
x
Определение 5.1 Пропускной способностью контактной схемы
( ;
, )
Gr V
q e
называется булева функция
2 1
[ ,...,
]
n
f
x
x
вида
( , )
( )
q e
f
.►
Но, для того чтобы, согласно определению 5.1, вычислить пропускную способность
( , )
( )
q e
f
контактной схемы
( ;
, )
Gr V
q e
, необходимо рассмотреть бесконечную совокупность путей
( , )
q e
. Оказывается, что для вычисления этой пропускной способности достаточно ограничиться подсовокупностью
0
( , )
q e
– простых путей
36
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
(путей, не содержащих циклы) среди путей совокупности
( , )
q e
. Совокупность
0
( , )
q e
, вследствие конечности контактной схемы, также является конечной и допускает, как будет показано далее, алгоритм еѐ перебора без повторений.
Теорема 5.1 (о вычислении пропускной способности контактной схемы). Пропускная способность контактной схемы
( ;
, )
Gr V
q e
вычисляется согласно формуле:
0
( , )
( )
q e
f
.►
На практике возникает и другая задача. По заданной пропускной способности создать контактную схему, еѐ реализующую. Такая задача называется задачей синтеза
контактной схемы.
Пример 5.2 (плоско-параллельной контактной схемы). Требуется синтезировать контактную схему с пропускной способностью
1 2
3 1
2 3
1 2
3 2
1 2
3
[ ,
,
]
f
x x x
x x x
x x x
x x x
На рис. 13 показана диаграмма контактной схемы с такой пропускной способностью. Эта схема называется плоско-параллельной.►
Рис.13
Рис.14
Для любой булевой функции, представленной еѐ дизъюнктивной нормальной формой
(ДНФ), в частности, – совершенной дизъюнктивной нормальной формой (СДНФ), плоско- параллельная контактная схема легко конструируется. Однако, такая контактная схема, как правило, не является оптимальной с точки зрения минимизации количества еѐ вершин и рѐбер. Более оптимальным синтезом контактной схемы является метод каскадов, изложению которого посвящѐн следующий раздел.
37
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5.2.1. Синтез контактной схемы методом каскадов
Метод каскадов для синтеза неизвестной контактной схемы с заданной пропускной способности осуществляется индуктивно.
Пусть
2 1
[ ,...,
]
n
f
x
x
– пропускная способность неизвестной контактной схемы
( ;
, )
Gr V
q e
, которую необходимо построить.
Далее предполагается, что функция
f
представлена полиномом Жегалкина, зависящим от всех булевых переменных
1
x ,
2
x , …,
n
x . Тогда алгоритм метода каскадов для синтеза неизвестной контактной схемы
( ;
, )
Gr V
q e
имеет следующий вид.
Первый шаг. Создаем входную вершину
q V
и две другие различные вершины
1 2
,
v v
V
. Новому ребру
1
{ , }
( , )
q v
R V
ставим в соответствие перемененную
1
x , новому ребру
2
{ , }
( , )
q v
R V
– переменную
1
x
. После этого вершину
1
v
помечаем полиномом
Жегалкина функции
1 2
2 1
( ,...,
)
(1,
,...,
)
n
n
f x
x
f
x
x
p
, вершину
2
v – полиномом Жегалкина функции
0 2
2 2
( ,...,
)
(0,
,...,
)
n
n
f x
x
f
x
x
p
. Если
1 0
p
(
2 0
p
), то вершину
1
v
(
2
v ) и входящее в неѐ новое ребро уничтожаем. Если
1 1
p
(
2 1
p
), то вершину
1
v
(
2
v ) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
v
e
(
2
v
e
).
…………………………………………………………………………………………
Текущий шаг. Пусть для переменных
1 1
1 1
,
,...,
,
k
k
x x
x
x
, построена часть схемы
( ;
, )
Gr V
q e
, в которой есть вершина v V
, помеченная полиномом Жегалкина
p
от переменных
,...,
k
n
x
x
и зависящим от переменной
k
x – существенно. Тогда для вершины
v создаем две новые вершины
1 2
,
w w
V
. Новое ребро
1
{ ,
}
( ; )
v w
R v
помечаем переменной
k
x , новое ребро
2
{ ,
}
v w – переменной
k
x . Кроме того, вершину
1
w (
2
w
) помечаем полиномом
1
p (
2
p
), полученным подстановкой в переменную
k
x полинома
p
числа
1
(числа
0
). Если оказалось, что
1 0
p
(
2 0
p
), то вершину
1
w (
2
w
) и входящее в неѐ новое ребро уничтожаем. Если же
1 1
p
(
2 1
p
), то вершину
1
w (
2
w
) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
w
e
(
2
w
e
). Кроме того, если среди уже ранее построенных вершин есть такая вершина w , что
1
p
q
(
2
p
q
), где q –
38
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев полином, помечающий вершину w , то в этом случае вершину
1
w (
2
w
) отождествляем вершиной w , т.е. полагаем
1
w
w
(
2
w
w
).
…………………………………………………………………………………………
1 2 3 4 5 6
второй шаг алгоритма.
Второй шаг. Отношение эквивалентности
индуцирует разбиения
(1)
1
(
)
,
(2)
2
(
)
,
(3)
3
(
)
и
(4)
4
(
)
на каждом классов
1 2
,
2 1, 4,5
,
3 3, 6
и
4 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
,
3
или
4
, зависящего только от этой входной буквы. Таблица 5 иллюстрирует эти переходы.
Таблица 5.
А
В
С
П
2
3
2
3
П
1 1
3
2
4
П
2 4
3
2
4
31
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5
3
2
4 3
2
1
2
П
3 6
2
1
2 7
2
3
1
П
4 8
2
3
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
, следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
(
1, 4
j
) из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
, работу которого иллюстрирует Таблица 6.
Таблица 6
A
B
C
1
3
B
2
C
3
A
2
3
B
2
C
4
A
3
2
A
1
B
2
C
4
2
A
3
B
1
C
Согласно таблицам 1 и 6, иллюстрирующим работу автоматов
и
a
настоящего примера, соответственно, на входное слово
AABCCABBC
эти автоматы, начиная с начальных состояний
1 V
и
2
(
2 1
и
2 1, 4, 5
a
), отвечают одинаковым выходным словом
BACACBBCA
. Аналогично подтверждается автоматная эквивалентность и других состояний автоматов
и
a
(
1 2
a
,
3 3, 6
a
и
4 7,8
a
).►
32
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5. Дискретные преобразователи
К одним из простейших конечных детерминированных автоматов относятся дискретные преобразователи, т.е. конечные автоматы Мили с одним состоянием. Анализу и синтезу таких дискретных преобразователей и посвящѐн настоящий раздел. Важность дискретных преобразователей обусловлена тем, что на их основе разрабатываются принципы синтеза конечных детерминированных автоматов. К типу дискретных преобразователей относятся логические схемы из функциональных элементов и контактные (переключательные) схемы.
Диаграммы логических схем из функциональных элементов и контактных
(переключательных) схем строятся на основе орграфов, называемых логическими и контактными сетями, соответственно. Кроме того, анализ контактной схемы осуществляется на основе специального орграфа, называемого деревом анализа контактной схемы. Краткое изложение теории графов, необходимое для описания логических и контактных сетей приведено в разделе 3.
5.1. Логические схемы из функциональных элементов
Логическая схема из функциональных элементов реализует дискретный преобразователь, поскольку она является автоматом с одним состоянием. Входным алфавитом такой логической схемы является словарь
n -мерных булевых кортежей
2 1
1 2
,...,
:
,...,
0,1 }
n
n
n
A
, где
2
( 0,1 ,
, , , 0,1 )
– стандартная булева алгебра (булев 1-куб). Алфавит еѐ выхода
2
B
Диаграммой логической схемы представляется в виде логической сети (см.
определение 3.3) с n источниками и одним стоком. Каждый из n источников логической сети помечен одной из булевых переменных
1
,....,
n
x
x так, что эти пометки попарно различны для разных источников. Каждая из остальных вершин этой сети помечена одним из логических функциональных знаков:
,
,
,
. При этом вершины, помеченные знаком дизъюнкции
(конъюнкции
), имеют позитивную валентность, равную двум; вершины, помеченные знаком логического отрицания
(равенства
), имеют единичную позитивную валентность. Пометки вершин диаграммы логической схемы, иллюстрируют работу этой схемы. На первом такте работы схемы на еѐ вход подаѐтся булев n -мерный кортеж
1 2
,...,
n
n
и булевым переменным, помечающим источники сети
33
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев логической схемы, присваиваются значения:
1 1
,....,
n
n
x
x
. Пометки других вершин диаграммы иллюстрируют работу функциональных элементов логической схемы: дизъюнктора (помечен знаком
), конъюнктора (помечен знаком
), инвертора (помечен знаком
) и дублятора-задержки (помечен знаком
).
С помощью диаграммы логической схемы описывается еѐ работа по реализации булевой функции
1 2
2
( ,....,
) :
n
n
f
f x
x
, называемой пропускной способностью этой логической схемы.
На рис. 12 для логической схемы с тремя источниками на примере еѐ диаграммы проиллюстрирована потактовая работа этой схемы, реализующей булеву функцию
1 2
2 3
(
)
f
x
x
x x
Рис.12
Замечание 5.1. Логическая схема из функциональных элементов, диаграмма которой приведена на рис. 12, работает потактово. Для соблюдения этого требования на этой диаграмме указан дублятор, иллюстрирующий задержку на один такт работы в этом функциональном элементе схемы. Кроме того, диаграмма на рис. 12 иллюстрирует методы анализа и синтеза логической схемы из функциональных элементов.►
Пример 5.1. В настоящем примере демонстрируется описание канонических уравнений конечного автомата Мили на основе булевых функций, с помощью которых работу автомата возможно реализовать логическими схемами из функциональных элементов. Для этого рассмотрим автомат
( , , , , )
A B V
, в котором
1 2
3 4
,
, ,
V
v v v v
– словарь его состояний и, кроме того, алфавиты входа и выхода совпадают и имеют вид:
,
A
a b
B
Работу этого автомата описывает таблица 7.
Таблица 7
34
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
a
b
1
v
3
v
a
4
v
b
2
v
1
v
b
2
v
a
3
v
1
v
a
1
v
b
4
v
2
v
b
3
v
a
Сменим обозначения состояний и букв алфавита входа и выхода автомата
( , , , , )
A B V
следующим образом. Буквы a и
b
заменим на символы
0
и
1, соответственно, получив в качестве алфавитов входа и выхода алфавиты
1 1
,
A
a b
B
Словарь
1 2
3 4
,
, ,
V
v v v v
состояний автомата
( , , , , )
A B V
заменим на соответствующий словарь
1
(0, 0), (0,1), (1, 0), (1,1)
V
. В результате получится автомат
1 1
1 1
(
,
, , , )
A B V
, фактически, реализующий автомат
( , , , , )
A B V
, если работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается, в соответствии с таблицей 7, таблицей 8.
Таблица 8
1
A
1
V
1
x
2
x
3
x
1
2
0 0
0 1
0 0
0 0
1 0
0 1
0 1
0 0
0 0
0 1
1 0
1 1
1 0
0 1
1 1
1 0
1 0
1 0
1 1
0 0
0 1
1 1
1 1
0 0
Таким образом, работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается двумерной булевой функцией перехода по состояниям
1 2
3 1
1 2
3 2
1 2
3
( ,
,
)
( ( ,
,
),
( ,
,
))
x x x
x x x
x x x
и булевой функцией
1 2
3
( ,
,
)
x x x
, которые определены таблицей 8. Из таблицы 8 получаем:
1 1 2 3 1 2 3 1 2 3 1 2 3 2 3
x x x
x x x
x x x
x x x
x x
,
2 1 2 3 1 2 3 1 2 3 1 2 1 2 3
x x x
x x x
x x x
x x
x x x
,
1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 3
x x x
x x x
x x x
x x x
x x
x x
35
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Следовательно, автомат
( , , , , )
A B V
с помощью автомата
1 1
1 1
(
,
, , , )
A B V
можно синтезировать, используя логические схемы из функциональных элементов.►
Упражнение 5.1. Синтезировать работу автомата
1 1
1 1
(
,
, , , )
A B V
из примера 5.1 с помощью логических схем из функциональных элементов, построив для этого соответствующие диаграммы логических схем.►
5.2. Контактные схемы
Пусть
( ;
, )
Gr V
q e
– контактная сеть (см. определение 3.4) и
1 1
2 2
( , ,
,
,...,
,
)
n
n
x x x x
x x
– список булевых переменных и их отрицаний. Как и ранее,
( ; )
R V
– совокупность рѐбер сети
( ;
, )
Gr V
q e
и задано отображение
: ( , )
R V
. Тогда говорят, что определена
контактная (переключательная) схема
( ;
, )
Gr V
q e
Рассмотрим совокупность путей
( ; )
q e
в сети
( ;
, )
Gr V
q e
с началом во входной вершине
q V
и с окончанием в заключительной вершине e V
. Путь
( , )
q e
представляем в виде списка его последовательных ребер:
1 1
2 2
1 1
({ , },{ , },...,{
,
},{
, })
k
k
k
q v
v v
v
v
v
e
Такому пути
поставим в соответствие конъюнкцию:
1 1
2 1
2 1
2
( )
({ , }) ({ , })... ({
, })
[ ,
,...,
]
k
n
q v
v v
v
e
x x
x
, где
2 1
[ ,...,
]
n
x
x – булева алгебра булевых функций от
n булевых переменных
1
,...,
n
x
x
Тем самым, отображение
расширяется до отображения
2 1
2
:
( , )
[ ,
,...,
]
n
q e
x x
x
Определение 5.1 Пропускной способностью контактной схемы
( ;
, )
Gr V
q e
называется булева функция
2 1
[ ,...,
]
n
f
x
x
вида
( , )
( )
q e
f
.►
Но, для того чтобы, согласно определению 5.1, вычислить пропускную способность
( , )
( )
q e
f
контактной схемы
( ;
, )
Gr V
q e
, необходимо рассмотреть бесконечную совокупность путей
( , )
q e
. Оказывается, что для вычисления этой пропускной способности достаточно ограничиться подсовокупностью
0
( , )
q e
– простых путей
36
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
(путей, не содержащих циклы) среди путей совокупности
( , )
q e
. Совокупность
0
( , )
q e
, вследствие конечности контактной схемы, также является конечной и допускает, как будет показано далее, алгоритм еѐ перебора без повторений.
Теорема 5.1 (о вычислении пропускной способности контактной схемы). Пропускная способность контактной схемы
( ;
, )
Gr V
q e
вычисляется согласно формуле:
0
( , )
( )
q e
f
.►
На практике возникает и другая задача. По заданной пропускной способности создать контактную схему, еѐ реализующую. Такая задача называется задачей синтеза
контактной схемы.
Пример 5.2 (плоско-параллельной контактной схемы). Требуется синтезировать контактную схему с пропускной способностью
1 2
3 1
2 3
1 2
3 2
1 2
3
[ ,
,
]
f
x x x
x x x
x x x
x x x
На рис. 13 показана диаграмма контактной схемы с такой пропускной способностью. Эта схема называется плоско-параллельной.►
Рис.13
Рис.14
Для любой булевой функции, представленной еѐ дизъюнктивной нормальной формой
(ДНФ), в частности, – совершенной дизъюнктивной нормальной формой (СДНФ), плоско- параллельная контактная схема легко конструируется. Однако, такая контактная схема, как правило, не является оптимальной с точки зрения минимизации количества еѐ вершин и рѐбер. Более оптимальным синтезом контактной схемы является метод каскадов, изложению которого посвящѐн следующий раздел.
37
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5.2.1. Синтез контактной схемы методом каскадов
Метод каскадов для синтеза неизвестной контактной схемы с заданной пропускной способности осуществляется индуктивно.
Пусть
2 1
[ ,...,
]
n
f
x
x
– пропускная способность неизвестной контактной схемы
( ;
, )
Gr V
q e
, которую необходимо построить.
Далее предполагается, что функция
f
представлена полиномом Жегалкина, зависящим от всех булевых переменных
1
x ,
2
x , …,
n
x . Тогда алгоритм метода каскадов для синтеза неизвестной контактной схемы
( ;
, )
Gr V
q e
имеет следующий вид.
Первый шаг. Создаем входную вершину
q V
и две другие различные вершины
1 2
,
v v
V
. Новому ребру
1
{ , }
( , )
q v
R V
ставим в соответствие перемененную
1
x , новому ребру
2
{ , }
( , )
q v
R V
– переменную
1
x
. После этого вершину
1
v
помечаем полиномом
Жегалкина функции
1 2
2 1
( ,...,
)
(1,
,...,
)
n
n
f x
x
f
x
x
p
, вершину
2
v – полиномом Жегалкина функции
0 2
2 2
( ,...,
)
(0,
,...,
)
n
n
f x
x
f
x
x
p
. Если
1 0
p
(
2 0
p
), то вершину
1
v
(
2
v ) и входящее в неѐ новое ребро уничтожаем. Если
1 1
p
(
2 1
p
), то вершину
1
v
(
2
v ) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
v
e
(
2
v
e
).
…………………………………………………………………………………………
Текущий шаг. Пусть для переменных
1 1
1 1
,
,...,
,
k
k
x x
x
x
, построена часть схемы
( ;
, )
Gr V
q e
, в которой есть вершина v V
, помеченная полиномом Жегалкина
p
от переменных
,...,
k
n
x
x
и зависящим от переменной
k
x – существенно. Тогда для вершины
v создаем две новые вершины
1 2
,
w w
V
. Новое ребро
1
{ ,
}
( ; )
v w
R v
помечаем переменной
k
x , новое ребро
2
{ ,
}
v w – переменной
k
x . Кроме того, вершину
1
w (
2
w
) помечаем полиномом
1
p (
2
p
), полученным подстановкой в переменную
k
x полинома
p
числа
1
(числа
0
). Если оказалось, что
1 0
p
(
2 0
p
), то вершину
1
w (
2
w
) и входящее в неѐ новое ребро уничтожаем. Если же
1 1
p
(
2 1
p
), то вершину
1
w (
2
w
) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
w
e
(
2
w
e
). Кроме того, если среди уже ранее построенных вершин есть такая вершина w , что
1
p
q
(
2
p
q
), где q –
38
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев полином, помечающий вершину w , то в этом случае вершину
1
w (
2
w
) отождествляем вершиной w , т.е. полагаем
1
w
w
(
2
w
w
).
…………………………………………………………………………………………
1 2 3 4 5 6
второй шаг алгоритма.
Второй шаг. Отношение эквивалентности
индуцирует разбиения (1)
1
(
)
,
(2)
2
(
)
,
(3)
3
(
)
и
(4)
4
(
)
на каждом классов
1 2
,
2 1, 4,5
,
3 3, 6
и
4 7,8
, соответственно, где в каждом из классов
1 2
,
1 1, 4,5
,
3 3, 6
и
4 7,8
буква входа автомата переводит состояние автомата из этого класса в состояние одного из этих классов
1
,
2
,
3
или
4
, зависящего только от этой входной буквы. Таблица 5 иллюстрирует эти переходы.
Таблица 5.
А
В
С
П
2
3
2
3
П
1 1
3
2
4
П
2 4
3
2
4
31
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5
3
2
4 3
2
1
2
П
3 6
2
1
2 7
2
3
1
П
4 8
2
3
1
Таким образом, на этом втором шаге алгоритмы индуцируется разбиение
2 2
3 4
(
,
,
,
)
совокупности состояний
1, 2,3, 4,5, 6, 7,8
V
автомата
Поскольку
, то, согласно алгоритму, присваиваем символу
значение разбиения
2 2
3 4
(
,
,
,
)
, следовательно, полагаем, что
1 2
3 4
(
,
,
,
)
, где
1 1
,
2 2
,
3 3
и
4 4
, и переходим к четвѐртому шагу алгоритма.
Четвёртый шаг. Создаѐм автомат
( , , , , )
( , , , , )
a
A B
A B
, где для состояния
j
v
(
1, 4
j
) из компоненты
j
:
( ,
)
( , );
( ,
)
( , ).
a
a
a
a
a v
a v
a v
a v
a v
a v
Пятый шаг. Выходим из алгоритма с результатом в виде приведѐнного автомата
a
, работу которого иллюстрирует Таблица 6.
Таблица 6
A
B
C
1
3
B
2
C
3
A
2
3
B
2
C
4
A
3
2
A
1
B
2
C
4
2
A
3
B
1
C
Согласно таблицам 1 и 6, иллюстрирующим работу автоматов
и
a
настоящего примера, соответственно, на входное слово
AABCCABBC
эти автоматы, начиная с начальных состояний
1 V
и
2
(
2 1
и
2 1, 4, 5
a
), отвечают одинаковым выходным словом
BACACBBCA
. Аналогично подтверждается автоматная эквивалентность и других состояний автоматов
и
a
(
1 2
a
,
3 3, 6
a
и
4 7,8
a
).►
32
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5. Дискретные преобразователи
К одним из простейших конечных детерминированных автоматов относятся дискретные преобразователи, т.е. конечные автоматы Мили с одним состоянием. Анализу и синтезу таких дискретных преобразователей и посвящѐн настоящий раздел. Важность дискретных преобразователей обусловлена тем, что на их основе разрабатываются принципы синтеза конечных детерминированных автоматов. К типу дискретных преобразователей относятся логические схемы из функциональных элементов и контактные (переключательные) схемы.
Диаграммы логических схем из функциональных элементов и контактных
(переключательных) схем строятся на основе орграфов, называемых логическими и контактными сетями, соответственно. Кроме того, анализ контактной схемы осуществляется на основе специального орграфа, называемого деревом анализа контактной схемы. Краткое изложение теории графов, необходимое для описания логических и контактных сетей приведено в разделе 3.
5.1. Логические схемы из функциональных элементов
Логическая схема из функциональных элементов реализует дискретный преобразователь, поскольку она является автоматом с одним состоянием. Входным алфавитом такой логической схемы является словарь
n -мерных булевых кортежей
2 1
1 2
,...,
:
,...,
0,1 }
n
n
n
A
, где
2
( 0,1 ,
, , , 0,1 )
– стандартная булева алгебра (булев 1-куб). Алфавит еѐ выхода
2
B
Диаграммой логической схемы представляется в виде логической сети (см.
определение 3.3) с n источниками и одним стоком. Каждый из n источников логической сети помечен одной из булевых переменных
1
,....,
n
x
x так, что эти пометки попарно различны для разных источников. Каждая из остальных вершин этой сети помечена одним из логических функциональных знаков:
,
,
,
. При этом вершины, помеченные знаком дизъюнкции
(конъюнкции
), имеют позитивную валентность, равную двум; вершины, помеченные знаком логического отрицания
(равенства
), имеют единичную позитивную валентность. Пометки вершин диаграммы логической схемы, иллюстрируют работу этой схемы. На первом такте работы схемы на еѐ вход подаѐтся булев n -мерный кортеж
1 2
,...,
n
n
и булевым переменным, помечающим источники сети
33
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев логической схемы, присваиваются значения:
1 1
,....,
n
n
x
x
. Пометки других вершин диаграммы иллюстрируют работу функциональных элементов логической схемы: дизъюнктора (помечен знаком
), конъюнктора (помечен знаком
), инвертора (помечен знаком
) и дублятора-задержки (помечен знаком
).
С помощью диаграммы логической схемы описывается еѐ работа по реализации булевой функции
1 2
2
( ,....,
) :
n
n
f
f x
x
, называемой пропускной способностью этой логической схемы.
На рис. 12 для логической схемы с тремя источниками на примере еѐ диаграммы проиллюстрирована потактовая работа этой схемы, реализующей булеву функцию
1 2
2 3
(
)
f
x
x
x x
Рис.12
Замечание 5.1. Логическая схема из функциональных элементов, диаграмма которой приведена на рис. 12, работает потактово. Для соблюдения этого требования на этой диаграмме указан дублятор, иллюстрирующий задержку на один такт работы в этом функциональном элементе схемы. Кроме того, диаграмма на рис. 12 иллюстрирует методы анализа и синтеза логической схемы из функциональных элементов.►
Пример 5.1. В настоящем примере демонстрируется описание канонических уравнений конечного автомата Мили на основе булевых функций, с помощью которых работу автомата возможно реализовать логическими схемами из функциональных элементов. Для этого рассмотрим автомат
( , , , , )
A B V
, в котором
1 2
3 4
,
, ,
V
v v v v
– словарь его состояний и, кроме того, алфавиты входа и выхода совпадают и имеют вид:
,
A
a b
B
Работу этого автомата описывает таблица 7.
Таблица 7
34
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
a
b
1
v
3
v
a
4
v
b
2
v
1
v
b
2
v
a
3
v
1
v
a
1
v
b
4
v
2
v
b
3
v
a
Сменим обозначения состояний и букв алфавита входа и выхода автомата
( , , , , )
A B V
следующим образом. Буквы a и
b
заменим на символы
0
и
1, соответственно, получив в качестве алфавитов входа и выхода алфавиты
1 1
,
A
a b
B
Словарь
1 2
3 4
,
, ,
V
v v v v
состояний автомата
( , , , , )
A B V
заменим на соответствующий словарь
1
(0, 0), (0,1), (1, 0), (1,1)
V
. В результате получится автомат
1 1
1 1
(
,
, , , )
A B V
, фактически, реализующий автомат
( , , , , )
A B V
, если работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается, в соответствии с таблицей 7, таблицей 8.
Таблица 8
1
A
1
V
1
x
2
x
3
x
1
2
0 0
0 1
0 0
0 0
1 0
0 1
0 1
0 0
0 0
0 1
1 0
1 1
1 0
0 1
1 1
1 0
1 0
1 0
1 1
0 0
0 1
1 1
1 1
0 0
Таким образом, работа автомата
1 1
1 1
(
,
, , , )
A B V
описывается двумерной булевой функцией перехода по состояниям
1 2
3 1
1 2
3 2
1 2
3
( ,
,
)
( ( ,
,
),
( ,
,
))
x x x
x x x
x x x
и булевой функцией
1 2
3
( ,
,
)
x x x
, которые определены таблицей 8. Из таблицы 8 получаем:
1 1 2 3 1 2 3 1 2 3 1 2 3 2 3
x x x
x x x
x x x
x x x
x x
,
2 1 2 3 1 2 3 1 2 3 1 2 1 2 3
x x x
x x x
x x x
x x
x x x
,
1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 3
x x x
x x x
x x x
x x x
x x
x x
35
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Следовательно, автомат
( , , , , )
A B V
с помощью автомата
1 1
1 1
(
,
, , , )
A B V
можно синтезировать, используя логические схемы из функциональных элементов.►
Упражнение 5.1. Синтезировать работу автомата
1 1
1 1
(
,
, , , )
A B V
из примера 5.1 с помощью логических схем из функциональных элементов, построив для этого соответствующие диаграммы логических схем.►
5.2. Контактные схемы
Пусть
( ;
, )
Gr V
q e
– контактная сеть (см. определение 3.4) и
1 1
2 2
( , ,
,
,...,
,
)
n
n
x x x x
x x
– список булевых переменных и их отрицаний. Как и ранее,
( ; )
R V
– совокупность рѐбер сети
( ;
, )
Gr V
q e
и задано отображение
: ( , )
R V
. Тогда говорят, что определена
контактная (переключательная) схема
( ;
, )
Gr V
q e
Рассмотрим совокупность путей
( ; )
q e
в сети
( ;
, )
Gr V
q e
с началом во входной вершине
q V
и с окончанием в заключительной вершине e V
. Путь
( , )
q e
представляем в виде списка его последовательных ребер:
1 1
2 2
1 1
({ , },{ , },...,{
,
},{
, })
k
k
k
q v
v v
v
v
v
e
Такому пути
поставим в соответствие конъюнкцию:
1 1
2 1
2 1
2
( )
({ , }) ({ , })... ({
, })
[ ,
,...,
]
k
n
q v
v v
v
e
x x
x
, где
2 1
[ ,...,
]
n
x
x – булева алгебра булевых функций от
n булевых переменных
1
,...,
n
x
x
Тем самым, отображение
расширяется до отображения
2 1
2
:
( , )
[ ,
,...,
]
n
q e
x x
x
Определение 5.1 Пропускной способностью контактной схемы
( ;
, )
Gr V
q e
называется булева функция
2 1
[ ,...,
]
n
f
x
x
вида
( , )
( )
q e
f
.►
Но, для того чтобы, согласно определению 5.1, вычислить пропускную способность
( , )
( )
q e
f
контактной схемы
( ;
, )
Gr V
q e
, необходимо рассмотреть бесконечную совокупность путей
( , )
q e
. Оказывается, что для вычисления этой пропускной способности достаточно ограничиться подсовокупностью
0
( , )
q e
– простых путей
36
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
(путей, не содержащих циклы) среди путей совокупности
( , )
q e
. Совокупность
0
( , )
q e
, вследствие конечности контактной схемы, также является конечной и допускает, как будет показано далее, алгоритм еѐ перебора без повторений.
Теорема 5.1 (о вычислении пропускной способности контактной схемы). Пропускная способность контактной схемы
( ;
, )
Gr V
q e
вычисляется согласно формуле:
0
( , )
( )
q e
f
.►
На практике возникает и другая задача. По заданной пропускной способности создать контактную схему, еѐ реализующую. Такая задача называется задачей синтеза
контактной схемы.
Пример 5.2 (плоско-параллельной контактной схемы). Требуется синтезировать контактную схему с пропускной способностью
1 2
3 1
2 3
1 2
3 2
1 2
3
[ ,
,
]
f
x x x
x x x
x x x
x x x
На рис. 13 показана диаграмма контактной схемы с такой пропускной способностью. Эта схема называется плоско-параллельной.►
Рис.13
Рис.14
Для любой булевой функции, представленной еѐ дизъюнктивной нормальной формой
(ДНФ), в частности, – совершенной дизъюнктивной нормальной формой (СДНФ), плоско- параллельная контактная схема легко конструируется. Однако, такая контактная схема, как правило, не является оптимальной с точки зрения минимизации количества еѐ вершин и рѐбер. Более оптимальным синтезом контактной схемы является метод каскадов, изложению которого посвящѐн следующий раздел.
37
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
5.2.1. Синтез контактной схемы методом каскадов
Метод каскадов для синтеза неизвестной контактной схемы с заданной пропускной способности осуществляется индуктивно.
Пусть
2 1
[ ,...,
]
n
f
x
x
– пропускная способность неизвестной контактной схемы
( ;
, )
Gr V
q e
, которую необходимо построить.
Далее предполагается, что функция
f
представлена полиномом Жегалкина, зависящим от всех булевых переменных
1
x ,
2
x , …,
n
x . Тогда алгоритм метода каскадов для синтеза неизвестной контактной схемы
( ;
, )
Gr V
q e
имеет следующий вид.
Первый шаг. Создаем входную вершину
q V
и две другие различные вершины
1 2
,
v v
V
. Новому ребру
1
{ , }
( , )
q v
R V
ставим в соответствие перемененную
1
x , новому ребру
2
{ , }
( , )
q v
R V
– переменную
1
x
. После этого вершину
1
v
помечаем полиномом
Жегалкина функции
1 2
2 1
( ,...,
)
(1,
,...,
)
n
n
f x
x
f
x
x
p
, вершину
2
v – полиномом Жегалкина функции
0 2
2 2
( ,...,
)
(0,
,...,
)
n
n
f x
x
f
x
x
p
. Если
1 0
p
(
2 0
p
), то вершину
1
v
(
2
v ) и входящее в неѐ новое ребро уничтожаем. Если
1 1
p
(
2 1
p
), то вершину
1
v
(
2
v ) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
v
e
(
2
v
e
).
…………………………………………………………………………………………
Текущий шаг. Пусть для переменных
1 1
1 1
,
,...,
,
k
k
x x
x
x
, построена часть схемы
( ;
, )
Gr V
q e
, в которой есть вершина v V
, помеченная полиномом Жегалкина
p
от переменных
,...,
k
n
x
x
и зависящим от переменной
k
x – существенно. Тогда для вершины
v создаем две новые вершины
1 2
,
w w
V
. Новое ребро
1
{ ,
}
( ; )
v w
R v
помечаем переменной
k
x , новое ребро
2
{ ,
}
v w – переменной
k
x . Кроме того, вершину
1
w (
2
w
) помечаем полиномом
1
p (
2
p
), полученным подстановкой в переменную
k
x полинома
p
числа
1
(числа
0
). Если оказалось, что
1 0
p
(
2 0
p
), то вершину
1
w (
2
w
) и входящее в неѐ новое ребро уничтожаем. Если же
1 1
p
(
2 1
p
), то вершину
1
w (
2
w
) отождествляем с заключительной вершиной e V
, т.е. полагаем
1
w
e
(
2
w
e
). Кроме того, если среди уже ранее построенных вершин есть такая вершина w , что
1
p
q
(
2
p
q
), где q –
38
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев полином, помечающий вершину w , то в этом случае вершину
1
w (
2
w
) отождествляем вершиной w , т.е. полагаем
1
w
w
(
2
w
w
).
…………………………………………………………………………………………
1 2 3 4 5 6
Заключительный шаг. Процесс метода каскадов заканчивается тогда, когда становится невозможным построения новых вершин для синтезируемой контактной схемы.
Пример 5.3 (синтеза контактной схемы методом каскадов). Требуется синтезировать методом каскадов контактную схему с пропускной способностью f из примера 5.2.
Следовательно:
1 2
3 1
2 3
1 2
3 1
2 1
3 2
3 1
2 3
f
x x x
x x x
x x x
x x
x x
x x
x x x
, где
– знак операции сложения по модулю два. На рис. 14 проиллюстрирован процесс синтеза искомой контактной схемы методом каскадов. Сравнение диаграмм на рис. 13 и рис. 14 показывает, что метод каскадов является более оптимальным, чем синтез плоско- параллельной контактной схемы.►
5.2.2. Дерево анализа контактной схемы
В настоящем разделе рассматривается задача анализа заданной контактной схемы
( ;
, )
Gr V
q e
с неизвестной пропускной способностью
2 1
[ ,...,
]
n
f
x
x
, которую требуется вычислить. Решение этой задачи осуществляется на основе алгоритма построения дерева анализа контактной схемы, диаграмма которого позволяет перечислить все простые пути этой схемы, связывающие еѐ вход и выход и, следовательно, вычислить искомую пропускную способность заданной контактной схемы
( ;
, )
Gr V
q e
. Алгоритм построения такого дерева анализа описывается следующим образом.
Первый шаг. Создаѐм корень текущего дерева анализа
Drv
, помечая его вершину входной вершиной q схемы
( ;
, )
Gr V
q e
. Кроме того, из этого корня выпускаем ориентированные рѐбра
1 1
,...,
k
k
y
y
q
v
q
v
, где
1
,...,
k
v
v – список всех попарно различных вершин, смежных в схеме
( ;
, )
Gr V
q e
с еѐ входной вершиной q , и каждое ребро
{ , }
( , )
j
q v
R V
этой схемы для
1,
j
k
помечено булевой переменной
Пример 5.3 (синтеза контактной схемы методом каскадов). Требуется синтезировать методом каскадов контактную схему с пропускной способностью f из примера 5.2.
Следовательно:
1 2
3 1
2 3
1 2
3 1
2 1
3 2
3 1
2 3
f
x x x
x x x
x x x
x x
x x
x x
x x x
, где
– знак операции сложения по модулю два. На рис. 14 проиллюстрирован процесс синтеза искомой контактной схемы методом каскадов. Сравнение диаграмм на рис. 13 и рис. 14 показывает, что метод каскадов является более оптимальным, чем синтез плоско- параллельной контактной схемы.►
5.2.2. Дерево анализа контактной схемы
В настоящем разделе рассматривается задача анализа заданной контактной схемы
( ;
, )
Gr V
q e
с неизвестной пропускной способностью
2 1
[ ,...,
]
n
f
x
x
, которую требуется вычислить. Решение этой задачи осуществляется на основе алгоритма построения дерева анализа контактной схемы, диаграмма которого позволяет перечислить все простые пути этой схемы, связывающие еѐ вход и выход и, следовательно, вычислить искомую пропускную способность заданной контактной схемы
( ;
, )
Gr V
q e
. Алгоритм построения такого дерева анализа описывается следующим образом.
Первый шаг. Создаѐм корень текущего дерева анализа
Drv
, помечая его вершину входной вершиной q схемы
( ;
, )
Gr V
q e
. Кроме того, из этого корня выпускаем ориентированные рѐбра
1 1
,...,
k
k
y
y
q
v
q
v
, где
1
,...,
k
v
v – список всех попарно различных вершин, смежных в схеме
( ;
, )
Gr V
q e
с еѐ входной вершиной q , и каждое ребро
{ , }
( , )
j
q v
R V
этой схемы для
1,
j
k
помечено булевой переменной
39
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
1 1
( ,
,...,
,
)
j
n
n
y
X
x x
x x
Кроме того, окончанием ориентированного ребра
j
j
j
y
r
q
v
в создаваемом текущем дереве
Drv
является лист, помеченный вершиной
j
v
схемы
( ;
, )
Gr V
q e
для
1,
j
k
. Такой лист называется заключительным листом, если он помечен вершиной выхода e этой контактной схемы. Другие листы так построенного текущего дерева
Drv
анализа называются свободными.
Второй шаг. Если в текущем дереве анализа
Drv
нет свободных листов, то выходим из алгоритма с результатом в виде диаграммы этого текущего дерева. В противном случае переходим к следующему шагу алгоритма.
Третий шаг. Рассматривается свободный лист текущего дерева анализа
Drv
, помеченный вершиной v схемы
( ;
, )
Gr V
q e
. Из этого листа выпускаем новые ориентированные рѐбра
1 1
,...,
k
k
y
y
v
v
v
v
, где
1
,...,
k
v
v – список всех попарно различных вершин, смежных в схеме
( ;
, )
Gr V
q e
с рассматриваемым листом, и каждое ребро
{ , }
( , )
j
v v
R V
этой схемы для
1,
j
k
помечено булевой переменной
1 1
( ,
,...,
,
)
j
n
n
y
X
x x
x x
. Кроме того, для
1,
j
k
окончанием ориентированного ребра
j
j
j
y
r
q
v
в дополняемом текущем дереве
Drv
является новый лист, помеченный вершиной
j
v схемы
( ;
, )
Gr V
q e
. От корня дерева до этого нового листа существует единственный путь
1 1
2 2
1
,
,...,
)
(
j
m
u
u
u
q
w w
w
v
v
. Если конъюнкция
1 2
( )
0
m
u
u
u
или путь
1 2
1
,
,
,...,
, ,
)
(
m
j
q w w
w
v v
в схеме
( ;
, )
Gr V
q e
не является простым, т.е. содержит цикл, то этот новый лист называется запрещѐнным и на диаграмме дополненного текущего дерева фон кружочка этого листа затемняется. Если среди оставшихся новых листов есть листы, помеченные вершиной выхода e контактной схемы
( ;
, )
Gr V
q e
, то такие новые листы называются заключительными листами дополненного текущего дерева. Новый лист, не являющийся заключительным и запрещѐнным, называется свободным листом дополненного текущего дерева. После этого так дополненное дерево объявляется текущим деревом анализа
Drv
и происходит переход ко второму шагу алгоритма.
Пример 5.4 (анализа контактной схемы). На основе приведѐнного выше алгоритма для контактной схемы
( ;
, )
Gr V
q e
, диаграмма которой показана на рис. 14, построено
40
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев дерево анализа этой контактной схемы. Диаграмма этого дерева анализа показана на рис. 15.
Рис.15
На диаграмме дерева анализа, показанной на рис. 15, трѐм заключительным листам соответствуют три пути, связывающие корень дерева с этими листьями:
2 2
4 4
1 2
3 1
,
,
)
(
x
x
x
q
v v
v v
e
,
1 1
4 4
1 2
3 2
,
,
)
(
x
x
x
q
v v
v v
e
,
1 1
3 3
1 2
3 3
,
,
)
(
x
x
x
q
v v
v v
e
Эти пути можно интерпретировать и как пути в рассматриваемой контактной схеме
( ;
, )
Gr V
q e
. Тогда
0 1
2 3
( , ) { ,
,
}
q e
– совокупность всех простых путей в этой контактной схеме. Следовательно, согласно теореме 5.1, еѐ пропускная способность
1 2
3 1 2 3 1 2 3 1 2 3
(
)
(
)
(
)
f
x x x
x x x
x x x
и найдена правильно, согласно примеру
5.3.►
Упражнение 5.2. Для контактной схемы, показанной на рис. 16, построить дерево анализа и найти еѐ пропускную способность. Затем, используя метод каскадов синтезировать контактную схему с этой пропускной способностью, сравнив еѐ с заданной.►
41
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Рис.16
6. Вопросы для самоконтроля
1. Универсальный и позитивный языки алфавита. Понятие формального языка и его лексикографического словаря.
2. Вычисление номера слова в словаре позитивного языка и алгоритм определения слова по его номеру.
4. Понятие ориентированного графа и способы его задания, классификация вершин и путей в орграфе.
5. Классификация орграфов.
6. Деревья и логические сети.
7. Понятие неориентированного графа и способы его задания, классификация вершин и путей в орграфе.
8. Понятие контактной сети.
9. Понятия автоматов Мили и Мура. Классификация автоматов.
10. Способы представления конечных автоматов и описание их работы.
11. Понятия автоматного отображения и эквивалентности состояний для автоматов Мура.
12. Понятие приведѐнного автомата. Алгоритм минимизации конечного автомата Мура по состояниям.
13. Понятие логической схемы из функциональных элементов, еѐ анализ и синтез.
14. Понятия контактной схемы и еѐ пропускной способности.
15. Плоскопараллельные контактные схемы.
16. Алгоритм синтеза контактной схемы на основе метода каскадов.
17. Понятие анализа контактной схемы и вычисление еѐ пропускной способности только на основе простых путей, связывающих еѐ вход и выход.