Тогда для М

Zv~fziXy, giXy i, Ху 2.....•-v-ц •v-l" .....•v-n)) -

f (Ху Xy i.....•v-ц v-l" .....

(6.17)

Следовательно, no определению, M является автоматом с максимальной памятью [I.

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

Теорема 6.1. Пусть М - минимальный автомат с памятью ц и числом состояний п. Тогда

а<4«(«-1)- (6.18)

Доказательство. Если автомат М является минимальным и имеет память ц, то должно существовать два пути, которые пересекаются не раньше, чем в своих конечных состояниях, как показано на рис. 6.3. Пусть а , ojj, } является

1-й парой состояний, а (о. , о ] является (/-f Л)-й парой

состояний (i + «<n) этих путей. Предположим, что совпадают (являются одними и теми же состояниями) о. с о.

а такл(е о. с о. . Тогда два пути, начинающихся в о, и

"l "i+h

о, каждый из которых описывает последовательность вход-

выход {bfiKiJljJ---{liJliJ представляют

собой замкнутые пути, которые являются (lii/j{liiJj[y--

ii+h-Jh+h-i) •"едовательно, пути бесконечной длины, которые описывают одну и ту же после-

довательность вход-выход, но не пересекаются, (рис. 6.4). По лемме 6.1 такие пути .не могут существовать в автомате с конечной памятью. Теперь предположим, что о совпадает

а о со.

"l+h

Тогда на-

чинающиеся каждый

Oj, и о.

пути,

из которых описывает последовательность вход-выход [Itjl, (biJtjiJ •

представля-ют собой замкнутые пути, которые являются ibfili)ibiJZjiJ ...

ми, и, следовательно, пути бесконечной длины, которые описывают

одну и ту же последовательность вход-выход, но не пересекаются (рис. 6.5). Снова, по лемме 6.1, такие пути не могут существовать. Таким образом, неупорядоченная 1-я пара а, о

Рис. 6.4. Иллюстрация доказательства теоремы 6.1.

О---

Рис. 6.5. Иллюстрация доказательства теоремы 6.1.

и неупорядоченная (/-)-/г)-я пара {Oft , о не могут

I i+h

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

=!«(«-!). (6.19)

Отсюда следует соотношение (6.18).

6.4. Определение памяти автомата

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

Рассмотрим автомат М с множеством состояний {Oj, 02.....а„). Пусть Q обозначает множество всех последовательностей вход-выход, описываемых путями длины k, которые заканчиваются в состоянии о,. По лемме 6.1, если М является автоматом с памятью ц, то

Qu-i П Q\i-i Ф О для некоторых / и ;Ф I, (6.20) QunQl/O для всех / и J Ф 1. (6.21)

По теореме 6.1, если М не является автоматом с конечной памятью, то

Qn\n-i)i2 П QMn-i)/2 Ф О ДЛЯ некоторых I тл j Ф1. (6.22)

Следовательно, для определения памяти автомата можно сформулировать следующий алгоритм.

Алгоритм 6.1. Задан автомат М с множеством состояний {Oi, 02.....а„); требуется найти память автомата М.

(1) Полагаем k=\. (2) Составляем последовательность

С§.....Qt\ (3) (а) Если Qf {\Qi ф О для некоторых /

и j ф I, то переходим к (4). (б) Если Q* П Qa* = О для всех I и j Ф I, то ft является памятью М. (4) (а) Если ft<«(«-1)/2, то увеличиваем ft на , 1 и возвращаемся к (2). (б) Если k = n(n-1)/2, то М не является автоматом с конечной памятью.

Выполнение алгоритма 6.1 облегчается при использовании матриц переходов высокого порядка, введенных в главе 2. В клетке (/, j) матрицы переходов ft-ro порядка [Mf записаны все пути длины ft, ведущие из состояния о, в состояние Oj. Поэтому клетки у-го столбца матрицы [Mf представляют все пути длины ft, заканчивающиеся в состоянии Оу. Таким образом, последовательности вход-выход, представленные путями, перечисленными в столбце матрицы [Mf,