О {ai) = F{ai); (б) М является сильиосвязиым, если ои имеет состояние Oi такое, что О (а) = F (а;) = S. [Определение О (а) даио в § 2.6; определение F (а) даио в задаче 2.10.]

5.10. Покажите, что если автомат М является сильиосвязиым,

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

5.11. Докажите следующее неравенство, использованное в выражении (5.13):

<ехр

п(п-1)

2{qn)P J-

5.12. Известно, что автомат М является сильиосвязиым (п, 2, 2)-автоматом. Покажите, что М всегда может быть распознай простым безусловным экспериментом длины I, где

1<

(2п)

2/1+1

П - 1!

Рис. 3 5.3.

Вычислите верхнее значение I /t при п = 5.

5.13. Известно, что автомат М является (п, р, д)-авю-матом и содержит полный контур. Найдите верхнее значение длины распознающего М эксперимента (можно предположить, что п ] 1).

5.14. Определите, является ли автомат А17, изображенный иа рис. 3 5.3, автоматом без потери информации.

5.15. Покажите, что автомат, представленный иа рис. 3 5.3, является автоматом без потери информации, и опишите распознавание входной последовательности аар, приложенной к этому автомату в состоянии 2.

5.16. Покажите, что автомат является сильиосвязиым, если он имеет любое из следующих свойств: (а) ни в одной строке подтаблицы ие содержится двух одинаковых выходных символов; (б) ИИ в одном столбце матрицы переходов ие имеется двух или более пар вход-выход с одинаковыми выходными символами.

ГЛАВА 6

АВТОМАТЫ С КОНЕЧНОЙ ПАМЯТЬЮ

6.1. Введение

Главное преимущество при использовании модели конечного автомата для представления заданной системы заключается в том, что предсказание выходной реакции системы не требует каких-либо данных относительно прошлого поведения системы. Для того чтобы предсказать выходную реакцию в любой заданный момент времени, достаточно знать входное воздействие и состояние в этот момент времени. Тогда, состояние автомата в настоящий момент времени можно рассматривать как особую «величину», которая в неявной форме объединяет все прошедшие события, относящиеся к определению выходной реакции в настоящий момент времени. Здесь может возникнуть следующий вопрос: всегда ли можно установить точное соотношение между выходной реакцией в настоящий момент времени и входным воздействием в настоящий момент времени и конечным числом входных воздействий и выходных реакций в предшествующие моменты времени? Отрицательный ответ на этот вопрос легко может

быть продемонстрирован на (a/WЩ/простом автомате/426, показан- "Xf) ) на рис. 6.1. В этом автома-

-- -""L те конечное состояние остается

(>W (a J неизвестным до тех пор, пока

Рис. 6.1. Автомат Л26. удет приложен вход а и

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

6.2] ПРЕДСТАВЛЕНИЕ СИСТЕМ с КОНЕЧНОЙ ПАМЯТЬЮ 211

В настоящий момент времени. Значит, в общем случае не существует явной зависимости, которая выражала бы выходную реакцию в настоящий момент времени как функцию входного воздействия в настоящий момент времени и входных воздействий и выходных реакций в предшествующие моменты времени. В связи с этим можно заключить, что состояние конечного автомата отражает его «бесконечную память» в том смысле, что пребывание автомата в этом состоянии является результатом события, которое происходило сколь угодно далеко в прошлом. Например, состояние, в которое приходит автомат А26 после приложения последовательности аррр ... р произвольной длины, однозначно определяется выходной реакцией на первый символ этой последовательности.

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

6.2. Представление систем с конечной памятью

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

) Материал этой главы основывается на работе Симона (J. М. Simon, А note on the Memory Aspects of sequence Transducers, IRE Trans., vol. CT-6, pp. 26-29, 1959) и Заде (L. A. Z a-deh, Unpublished notes on discrete - state systems and automata, University of California, Berkeley, 1960).

) Автоматы, у которых выходная реакция не зависит от входного воздействия, называются автономными. Автономные автоматы в книге не рассматриваются.