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

6.1. Введение

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

Рис. 6.1. Автомат

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

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