§ 7.7. Что «может делать» конечный автомат
В предыдущей главе мы выяснили, что «может делать» автономный автомат. Дополняя эти сведения теоремами о представлении событий, мы можем ответить на вопрос о том, что «может делать» неавтономный автомат.
Пусть мы имеем автомат А с выходным преобразователем или последовательностную машину, представляющую появлением некоторого символа (для конкретности — единицы) на выходе регулярное событие на входе. Пусть далее при появлении 1 на выходе автомата А этот автомат А останавливается и пускает в ход автономный автомат Б, который выдает на выходе заранее заданную последовательность М. Выход автомата Б отождествлен с входом автомата В, который представляет событие М.
Появление 1 на выходе автомата В используется для того, чтобы пустить в ход автомат А и остановить автомат Б. Это (рис. 7.10) делает автомат Ф, который служит для представления простого события: появления заданного входного символа. Поэтому вся описанная система в целом представляет собой конечный автомат. Такой конечный автомат реагирует на любое регулярное событие, выдавая на выходе любую заранее заданную конечную последовательность состояний (символов), и после этого вновь готов к восприятию внешнего воздействия, т. е. реагированию на событие.
Рис. 7.10.
При составлении автомата по схеме рис. 7.10 автомат не реагирует на часть входных символов 
, которая появляется в течение тех тактов, когда работает автономный автомат Б.
Если автомат Б работает в столь быстрой тактности, что вся периодическая последовательность на выходе автомата Б укладывается за время между двумя тактами автомата А, нет нужды включать автомат Ф, и выход автомата А может служить входом автомата Б. Так построенный автомат поддерживает на выходе любую заданную периодическую последовательность символов все время, пока представляется событие, и иную наперед заданную периодическую последовательность символов, когда событие не представляется.
Разумеется, возможны и иные сочетания автоматов. Но уже описанные два сочетания показывают, что автомат может реагировать на регулярное событие любым, наперед заданным циклом.
Может ли автомат сделать что-либо более этого? Что именно? Ответы на такие вопросы связаны с тем, на каком языке формулируются законы переработки последовательностей конечным автоматом. Теоремы Клини формулируют эти законы на языке представления событий. До сих пор не были предложены иные удобные языки, на которых можно было бы в терминах необходимых и достаточных условий описать, что может и что принципиально не может «делать» конечный автомат. В связи с этим возникает ряд новых проблем, которым посвящена следующая глава.
