Дискретная математика & математическая логика
..pdfАвтомат В:
Рис. 5.2. Некоторый автомат В
В то же время оказывается, что их реакции на входную цепочку aabbabb одинаковы:
ψ* (y , aabbabb) = ψ* (y , aabbabb) = 0001001.
A 0A B 0B
Однако перебрать все входные цепочки невозможно – их бесконечно много, поэтому проблема эквивалентности автоматов нетривиальна.
Существует метод решения этой проблемы. Он основан на понятии прямого произведения автоматов.
Прямое произведение автоматов [11]
Определение. Прямым произведением автоматов
A= < X A , YA , Z A , y0A , φA , ψA >,
B= < X B , YB , Z B , y0B , φB , ψB >
содинаковым входным алфавитом Х называется автомат А В
A B = < X , YA YB , Z A ZB , (y0A , y0B ), φA B , ψA B >,
171
где
1) ( y |
Y )( y |
B |
Y )( x X )[φ |
A B |
((y |
A |
, y= ), x) |
A |
A |
B |
|
B |
|||
(φA (yA , x), φB (yB , x))]; |
|
|
|
|
2) ( y |
Y )( y |
B |
Y )( x X )[ψ |
A B |
((y |
A |
, y= ), ξ) |
A |
A |
B |
|
B |
(ψA (yA , x), ψB (yB , x))],
т.е. в качестве состояний автомата А · В получаем пары состояний (yA , yB ), начальное состояние – пара состояний (y0A , y0B ), выходной
алфавит – множество пар выходных символов [(ψA (yA , x), ψΒ (yB , x)].
Получаем параллельно работающие на одном входе автоматы
(рис. 5.3):
Рис. 5.3. Прямое произведение автоматов А и В = А · В
Теорема Мура. Два конечных автомата
A = < X A , YA , Z A , y0A , φΑ , ψA >,
B= < X B , YB , ZB , y0B , φB , ψB >
содинаковым входным алфавитом эквивалентны тогда и только тогда, когда для любого достижимого состояния (yA , yB ) в их пря-
мом произведении А · В функции выходов одинаковы:
172
( x X )[ψ(yA , x=) ψ(yB , x)].
Умножим автомат А на автомат В. Получаем вначале 6 вершины (рис. 5.4):
Рис. 5.4. Вершины автомата А · В
Если есть петли в обеих вершинах – она остаётся и в вершине графа произведения автоматов (b/1,1) – вверху, в числителе – входной символ, в знаменателе – выходные через запятую.
Дуги проводим так же (рис. 5.5):
Рис. 5.5. Начало получения дуг А · В
173
В результате получаем граф переходов А · В (рис. 5.6):
Рис. 5.6. Граф прямого произведения автоматов А и В – автомат А · В
Удалим недостижимые состояния (рис. 5.7):
Рис. 5.7. Прямое произведение А · В с исключёнными недостижимыми состояниями
174
Видно, что для каждого состояния выполняется выдача пар одинаковых выходных сигналов. Следовательно, автоматы А и В эквивалентны.
5.2. МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ
Итак, разные автоматы могут функционировать одинаково, даже если у них разное число состояний.
Важной задачей теории автоматов является нахождение минимального автомата, реализующего заданное автоматное отображение.
Эквивалентные состояния [11]
Два состояния называются эквивалентными тогда и только тогда, когда их нельзя различить никакими входными последовательностями (экспериментами).
Два состояния p и q конечного автомата A = < X , Y , Z , y0 , φ, ψ > называются эквивалентными (будем обозначать p ≈ q ) тогда и только тогда, когда
( α X * )[ψ* (p, α=) ψ* (q,α)].
Пусть даны два автомата, рассмотренных нами далее – произведение А × В (см. рис. 5.7). Состояния q0 и q2 эквивалентны: любая входная цепочка, поданная на автомат, находящийся в состоянии q0, даст такую же реакцию и в случае, когда автомат находился вначале в состоянии q2.
Эти два состояния можно объединить в одно (рис. 5.8):
175
Рис. 5.8. Объединение двух эквивалентных состояний
водно – получаем автомат с двумя состояниями
Врезультате получим автомат, имеющий два состояния –
рис. 5.9:
Рис. 5.9. Автомат, эквивалентный автомату на рис. 5.8
176
Эквивалентные состояния объединяются в классы, эти классы и являются состояниями нового автомата. Если определить на множестве состояний автомата минимально возможное разбиение (меньше двух у автомата с памятью не бывает), то получим минимальный автомат, эквивалентный исходному.
Мы не сможем перебрать все возможные цепочки, как и в случае выяснения эквивалентности двух автоматов. Но существует алгоритм последовательного разбиения состояний автомата на классы и определения максимального отношения эквивалентности.
Разбиение состояний автомата на классы эквивалентности
Алгоритм состоит в последовательном построении на множестве состояний автомата разбиений π0, π1, …, π∞, таких, что в один класс попадают k-эквивалентные состояния, т.е. те, которые неразличимы входными цепочками длиной k [11].
Такиесостояниябудемсчитатьвотношенииэквивалентности ≈ k .
Вслучае ¬(p ≈k |
q) |
состояния p иq называютсяk-различимыми. |
Таким образом, |
|
|
(p ≈ k q)↔ |
( |
α X≤ * , α k)[ψ* =(p, α) ψ* (q, α)]. |
Очевидно, что в любом автомате все состояния 0-эквива- лентны, поскольку при подаче пустой цепочки на вход автомата (цепочки длины 0) выходом является также пустая цепочка, независимо от того, в каком состоянии находится автомат.
Разбиения π0, содержащее один-единственный блок и π1, в каждом блоке которого объединены состояния, не различимые входными сигналами, являются исходными при построении последовательности разбиений π0, π1, …, π∞.
177
Как же строить следующее разбиение начиная с π1?
Теорема. Пусть p ≈ k q, k> 1.
Для выполнения p ≈ k +1 q необходимо и достаточно, чтобы
( x X )[φ(p, x≈ ) k φ(q, x)],
т.е. k-эквивалентные состояния под воздействием входных сигналов переходили бы в состояния, также являющиеся k-экви- валентными.
Действительно, для того чтобы цепочка длиной k + 1, например x0 , x1 , x2 , ..., xk +1 , не различала состояния p и q, нужно, чтобы из
этих состояний под воздействием сигнала x0 был переход в такие состояния, которые не различимы цепочкой x1 , x2 , ..., xk , т.е. чтобы φ(p, x) и φ(q, x) были k-неразличимы (рис. 5.10):
Рис. 5.10. Пояснение теоремы о k + 1 эквивалентности: x1, x2, …, xk – цепочка длиной k,
x0, x1, x2, …, xk – цепочка длиной k + 1
Пример минимизации автомата [11]
Дана таблица переходов-выходов в форме обобщённой таблицы (табл. 5.1):
178
Таблица 5 . 1
Переходы-выходы минимизируемого автомата с девятью состояниями, с двумя входными символами (сигналами) – а, b
№ y(t) π0 |
|
Функции переходов и выходов |
|
|
|
|
||||||||
|
ϕ y(t + 1) |
|
|
ψ z(t) |
|
|
|
|
||||||
|
а |
|
b |
|
а |
|
|
|
b |
|
π1 |
|||
1 |
3 |
|
6 |
1 |
|
|
0 |
|
|
А1 |
|
|||
2 |
4 |
|
8 |
0 |
|
1 |
|
|
В1 |
|
||||
3 |
1 |
|
4 |
1 |
|
|
0 |
|
|
А1 |
|
|||
4 |
7 |
|
9 |
0 |
|
1 |
|
|
В1 |
|
||||
5 |
9 |
|
1 |
|
1 |
|
|
|
0 |
|
|
А1 |
|
|
6 |
3 |
|
5 |
|
1 |
|
|
|
0 |
|
|
А1 |
|
|
|
|
|
|
|
|
|
|
|
||||||
7 |
4 |
|
3 |
0 |
|
1 |
|
|
В1 |
|
|
|||
8 |
4 |
|
2 |
1 |
|
|
0 |
|
|
А1 |
|
|||
9 |
5 |
|
7 |
1 |
|
|
0 |
|
|
А1 |
|
|||
|
|
|
|
|
|
Начальное разбиение – это один блок, включающий все состояния, поскольку входные цепочки длиной 0 (пустая цепочка ε) не различают состояний. Независимо от того, в каком состоянии находился автомат, при подаче пустой цепочки ε выходом также будет пустая цепочка ε.
π0 = {А0 = <1, 2, 3, 4, 5, 6, 7, 8, 9>}.
Строим π1 – те состояния, которые не различаются цепочкой длины 1, т.е. символом либо а, либо b.
Видим, что состояния разбиваются на два блока – в первом реакции 1,0, во втором – 0,1:
π1 = {А1 = <1, 3, 5, 6, 8, 9>; В2 = <2, 4, 7>}.
Добавим к таблице переходов-выходов столбец для π1. Теперь смотрим, в какие блоки переходит автомат из блоков
π1 под воздействием символов а, либо b.
Строим таблицу переходов из блоков разбиения π1 (табл. 5.2).
179
Итак, в первой строчке под воздействием а осуществляется переход в состояние 3 – это блок А1, под воздействием b осуществляется переход в состояние 6, это тоже блок А1. Так и записываем.
Во второй строчке под воздействием а осуществляется переход в состояние 4 – это блок В1, под воздействием b осуществляется переход в состояние 6 – это блок А1.
Втретьей строчке под воздействием а осуществляется переход в состояние 1 – это блок А1, под воздействием b осуществляется переход в состояние 4 – это блок В1.
Вчетвёртой строчке под воздействием а осуществляется переход в состояние 7 – это блок В1, под воздействием b осуществляется переход в состояние 9 – это блок А1.
Действуя аналогично, получаем всю таблицу:
|
|
|
|
|
|
|
|
Таблица |
5 . 2 |
||||||||
|
Таблица переходов из разбиения π1 |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№ y(t) |
Функции переходов и выходов |
|
|
|
π1 |
|
|
|
|||||||||
ϕ y(t + 1) |
|
ψ z(t) |
|
|
ϕ y(t + 1) |
|
|
|
|
|
|||||||
|
а |
|
b |
а |
|
b |
|
а |
|
|
b |
|
|
π 2 |
|
||
1 |
3 |
|
6 |
1 |
|
0 |
|
А1 |
|
|
А1 |
|
|
А2 |
|
||
2 |
4 |
|
8 |
0 |
|
1 |
|
В1 |
|
|
А1 |
|
|
В2 |
|
||
3 |
1 |
|
4 |
1 |
|
0 |
|
А1 |
|
|
В1 |
|
|
С2 |
|
||
4 |
7 |
|
9 |
0 |
|
1 |
|
В1 |
|
|
А1 |
|
|
В2 |
|
||
5 |
9 |
|
1 |
1 |
|
0 |
|
А1 |
|
|
А1 |
|
|
|
А2 |
|
|
6 |
3 |
|
5 |
1 |
|
0 |
|
А1 |
|
|
А1 |
|
|
|
А2 |
|
|
7 |
4 |
|
3 |
0 |
|
1 |
|
В1 |
|
|
А1 |
|
|
В2 |
|
||
8 |
4 |
|
2 |
1 |
|
0 |
|
В1 |
|
|
В1 |
|
|
|
D2 |
|
|
9 |
5 |
|
7 |
1 |
|
0 |
|
А1 |
|
|
В1 |
|
|
|
С2 |
|
|
Выделяем в табл. 5.2 эквивалентные состояния. |
|
|
|
||||||||||||||
Получаем разбиение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
π2 = {А2 = <1, 5, 6>; |
В2 = <2, 4, 7>; С2 = <3, 9>; |
|
D2 = <8>}. |
Строим таблицу переходов из разбиения π3. При его построении уже не нужно анализировать, в какой блок π2 переходит авто-
180