Пусть алгоритм остановился на k-м шаге и q и q0 принадлежат одному классу Cki из разбиения полученного на этом шаге. По условию остановки алгоритма для любого aδ(q, a) и δ(q0, a) принадлежат одному классу Ckj; следовательно, это верно для любого слова α. Но состояния q и q0 одного класса заведомо принадлежат одному классу C1L, поэтому λ(q, a) = λ(q0, a), откуда, учитывая !!! (7-3), получаем, что S(q, α) = S(q0, α) для любого α, то есть состояния эквивалентны.

Пусть теперь q и q0 принадлежат разным классам Cri и Crj, начиная с некоторого r 6 k. Тогда по построению найдется такое a, что δ(q, a) и δ(q0, a) принадлежат разным классам Cr−1,i, Cr−1,j; для них, в свою очередь, найдется такое a00, что δ(δ(q, a), a00) и δ(δ(q0, a), a00) принадлежат разным классам Cr−2,i, Cr−2,j; продолжив по индукции, получим, что для некоторого слова α длины rδ(q, α) и δ(q0, α) принадлежат разным классам C1i, C1j, а это означает, что λ(q, α) 6= λ(q0, α) и, следовательно, q и q0 не эквивалентны.

Частичные автоматы и их минимизация

Автомат S называется частичным или не полностью определенным, если хотя бы одна из его двух функций не полностью определена, то есть для некоторых пар состояние — вход значения функций δ и λ не определены. В автоматной таблице — прочерки. В графе частичного автомата в вершинах, где δ

не определено, нарушено условие полноты. Знак : A B означает, что A и B либо одновременно не

= =

определены, либо определены и равны. Функция δ(qi, α):

а) (qi, aj) задана таблицей автомата S;

б) если δ(q	, α) определена, то δ(q	, αa	) =	δ(δ(q	, α), a	);
i	i	j		i	j

в) если δ(qi, α) не определена, то δ(qi, αaj) не определена для всех aj.

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

Функция λ(q	, α) : λ(q	, αa	) =	λ(δ(q	, α), a	).
i	i	j		i	j

Автоматное отображение S(qi, α):

а) S(qi, aj) = λ(qi, aj)(еслиλ(qi, aj) не определена, то значение S(qi, aj) считается равным прочерку).

б) если δ(qi, α) определена, то

S(qi, αaj) = S(qi, α)λ(δ(qi, α), aj)

(если λ(δ(qi, α), aj) не определена, то слово S(qi, αaj) получено из слова

S(qi, α) приписыванием прочерка);

в) если δ(qi, α) не определена, то и S(qi, α, aj) не определено.

Входное слово α, для которого S(qi, α) определено, называется допустимым для qi.

Из этих определений видно, что функции δ и λ неравноправны, если δ не определена на слове α, то она не определена и на всех его продолжениях; для λ это не обязательно. Поэтому если δ определено на α, а λ не определена на некоторых начальных отрезках α, отображение S(qi, α) «определено, но не совсем»: оно представляет собой слово, содержащее прочерки. Это интерпретируется и на графе. Понятие неотличимости для частичных автоматов также изменяется: состояния qi автомата S и rj автомата

Tназывается псевдонеотличимыми, если для любого αS(q , α) T (r , α).

i = j

Автоматы S и T псевдонеотличимы, если для любого состояния S найдется псевдонеотличимое от него состояние T и наоборот. Достоинство этого определения в том, что для полностью определенных автоматов оно совпадает с обычным; кроме того, отношение псевдонеотличимости является отношением эквивалентности. Нетрудно показать, что если прочерк в функции δ рассматривать как символ нового состояния (переходящего по любому входу только в себя), а в функции λ — как новую выходную

букву, то отношение S(q , α) T (r , α) переходит в обычное отношение равенства,

i = j

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

S(qi, α) = T (rj, α) и, следовательно, применение к частичному автомату S изложенного ранее алгоритма Мили даст минимальный автомат, псевдонеотличимый от S.

Пример 6.

	a1	a2	a3	Псевдонеотличимых состояний здесь просто нет. Рассмотрим состоя-
1	2,0	–	3,–	ния 2 и 3 (q2, q3). Область определения для q2, то есть для отображения
2	–	1,–	3,0	S(q2, α), содержится в области определения для q3; кроме того, на всей
3	2,1	1,–	3,0	области определения q2

S(q2, α) = S(q3, α) для любого α, так как при любой входной букве λ(q2, α) λ(q3, α) и δ(q2, α)

= =

δ(q3, α). Поэтому ясно, что если в Sq2заменить на q3 (то есть вычеркнуть строку 2, а переходы из других состояний в q2 заменить на переходы в q3), то получим автомат S0, который делает больше, чем S00. Это соображение приводит к понятию покрытия для состояний и автоматов. Состояние qi автомата S покрывает состояние rjавтомата T , если для любого α, из того, что T (rj, α) определено, следует, что S(qi, α) определено и S(qi, α) = T (rj, α). Автомат S покрывает автомат T , если для любого состояния T найдется покрывающее его состояние S. В частности, состояние, строка которого не содержит прочерков, покрывает все состояния, строки которых получаются из нее заменой некоторых символов прочерками. В примере q3 покрывает q2, а автомат S0 покрывает S. Рассмотрим теперь состояния q1 и q2 в примере. Можно представить себе состояние, которое покрывает q1 и q2. Например: 2,0; 1,–; 3,0 — это называется объединением строк. Состояния qi автомата S и rj автомата T называются совместимыми, если существует состояние pk (какого-то автомата W ), покрывающее qi и rj. Автоматы S и T совместимы, если существует автомат W , покрывающий S и T .

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

Назовем систему классов совместимости C1, . . . , Ci полной, если C1 . . . Ci = Q, и замкнутой, если

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

из того, что состояния q и q0 находятся в одном классе Ci, следует, что состояния δ(q, α) и δ(q0, α) также находятся в одном классе Cj всякий раз, когда δ(q, α) и δ(q0, α) определены.

Теорема (Полла - Ангера). Если для частичного автомата S имеется полная и замкнутая система классов совместимости C1, . . . , Ci, то существует автомат S0, покрывающий S.

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

1.Различные доопределения частичного автомата S приводят, вообще говоря, к неэквивалентным

между собой полным автоматам S1, . . . , SN ; соответствующие минимальные автоматы S10, . . . , SN0 могут иметь разное число состояний и также не эквивалентны между собой.

Пример. Рассмотрим три доопределения клетки (2, a1) : (2, 0)(2, 1)(1, 1)

В первом случае получим автомат S1, где состояния 1 и 2 эквивалентны; во втором случае получим автомат S2, где 1 и 2 не эквивалентны, а эквивалентны 2 и 3; минимальные для них автоматы S10 и S20 имеют по 2 состояния, но могут оказаться неизоморфными, если для S2 доопределить δ(1, a2) = 3. Наконец, третье доопределение дает неминимизируемый автомат S3. Поэтому, во-первых, результат минимизации может сильно зависеть от выбранного доопределения, а вовторых этот результат является тупиковым — его нельзя улучшить эквивалентными преобразованиями и надо пробовать другой вариант доопределения. Число же этих вариантов очень велико: если |Qs| = n, |V s| = k, δS не определено в p клетках, а λS — в r клетках, то это число равно npkr.

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

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель

	Пример Полла - Ангера.
		a1	a2	Этот автомат S можно доопределить двумя способами
	1	1,–	2,0	1)	λ(1, a1) = 0
	2	3,0	1,0
	3	2,1	1,0	2)	λ(1, a1) = 1

Можно проверить, что при любом из этих доопределений полученный автомат не имеет эквивалентных состояний и, следовательно, не минимизируется. Однако для частичного автомата S это означает всего лишь, что он не имеет нетривиальной замкнутой системы непересекающихся классов совместимости. В то же время для S существует замкнутая система пересекающихся классов: C1 = {1, 2}, C2 = {1, 3}, которая по теореме приводит к автомату S0 с двумя состояниями покрывающему S.

	a1	a2
C1	C2, 0	C1, 0
C2	C1, 1	C1, 0

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

дача состоит в нахождении всех n(n−1) совместимых пар состояний. Решение этой задачи основано на

2

том, что пара состояний q и q’ несовместима, если либо λ(q, ai) 6= λ(q0, ai), либо пара δ(q, aj) и δ(q0, aj) несовместима для некоторых ai, aj. Это дает простой индуктивный процесс (в некотором смысле дополнительный к алгоритму Мили): на 1-м шаге несовместимыми объявляются все пары q, q0, для которых λ(q, ai) 6= λ(q0, ai); на (i + 1) шаге несовместимыми объявляются все пары q, q0, для которых δ(q, aj) и δ(q0, aj) уже были определены как несовместимые на предыдущих шагах. Процесс останавливается, когда не появляется новых несовместимых пар; все остальные пары являются совместимыми. Далее из

•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель