(0/0)

(r/V

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

В общем случае автомат, полученный описанным способом, не минимальный. Однако, минимальная форма всегда может быть определена любым из методов минимизации, описанных в главе 3. Минимальная форма автомата Л27 показана на рис. 6.2, где состояния 1, 2, 3 и 4 представляют эквивалентные классы {(1, 0. 0). (1.1. 1)), {(О, 0. 1), (О, 1, 0)). {(О, о, 0), (0. 1. 1)) и {(1. о, 1). (1, 1, 0)} соответственно.

(0/V

(О/О)

Рис. 6.2. Автомат ATI.

6.8. Свойства автоматов с конечной памятью

Конечный автомат, представляющий систему с конечной памятью, будем называть автоматом с конечной памятью. Таким образом, автомат с конечной памятью М, является автоматом, в котором

Zv=f(Xv. Jfv-l.....>v-n,. Z-i, Zv-2. .... v-nJ, (6.10)

где любой из аргументов (за исключением одного из Xi) может быть несущественной переменной. Числа [г, и jij называются соответственно памятью х и памятью z автомата М. Целое число

li=max(iii, lij)

(6.11)

называется максимальной памятью М. Если в дополнение к (6.10) имеет место

/(•"v" -"v-l • • •> -"v-n" v-l v-2> • • v-ji)

¥=f(Xy, Xy i, .... АГу + 1, Zy 2.....Zy i), (6.12)

ТО будем говорить, что автомат М имеет память \i. Таким образом, II является памятью автомата в том случае, если предсказание выходной реакции, по крайней мере, на одно входное воздействие в момент времени требует знания входного воздействия и (или) выходной реакции в момент времени (и, возможно, входных воздействий и выходных реакций, которые возникают в более поздние моменты времени), но не требует знания каких-либо входных воздействий и выходных реакций в моменты времени более ранние, чем

В дальнейшем (tjliiji {bjiji) будем называть последовательностью вход-выход, если входная последовательность lili • заставляет автомат генерировать выходную последовательность СуСу • Су- Будем говорить,

что путь в диаграмме переходов описывает последовательность вход-выхол (lijljy(lijt,jy .-{lijlji) если его/г-яветвь

для ft =1, 2.....I обозначена парой вход-выход (bJJ)

(и, возможно, другими парами вход-выход). Пути будем называть (l,lJt,j{l,iJl,j...(l,iJl,jj)-coвnaдaюuuмu, если каждый из них описывает последовательность вход-выход

Лемма 6.1. В минимальном автомате с памятью ц

s = g{Xy y, Ху 2.....лг-ц. v-v .....(6-13)

Доказательство. Предположим обратное. Тогда автомат должен содержать по крайней мере два пути, которые являются {bJJi){bJJ2) • (г/Су-совпадающими для некоторой последовательности вход-выход (ijjiiji • ... (lijij и которые оканчиваются двумя различимыми состояниями. Пусть начальные состояния этих путей будут о, и о! и конечные состояния - Oj, и ol ; пусть минимальная

и ц

диагностическая последовательность для и о есть

"и *и

и+1и+2 • • " одинаковые

выходные реакции на . -Il+i- -i+r-i "° различные

Рис. 6.3. (,.JSy)(,JC/S;J-совпадающие пути.

последовательности вход-выход. Лемма 6.1 означает, что диаграмма переходов автомата с памятью р. должна обладать следующими свойствами. Пути, которые являются (bJZj\) X X (liJZj) • • • (bf),/ji)-((Ti],mii, должны пересекаться в своих конечных состояниях. Кроме того, должна быть, по крайней мере, одна пара {bjjbjj,) -•• -(/ц/С/-совпа-

дающих путей, которые пересекаются в своих конечных состояниях, но не имеют других пересечений. Такая пара путей показана на рис. 6.3.

Лемма 6.2. Если в заданном автомате М

*v = S"(v-l v-2.....v-n> z-i. z 2.....•v-n). (6-15)

mo M является автоматом с максимальной памятью р.. Доказательство. Для любого конечного автомата

v = A(v. Sv)- (6-16)

реакции на ЬЬ - • - Ь,.- Однако это невозможно,

так как по предположению автомат имеет память ц и, следовательно,

Zy = fiX. АГ 1.....х . z 2.....z ). (6.14)

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

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