ГЛАВА VII. ПРЕДСТАВЛЕНИЕ СОБЫТИЙ В КОНЕЧНОМ АВТОМАТЕ И ПОСЛЕДОВАТЕЛЬНОСТНОЙ МАШИНЕ

§ 7.1. Постановка задачи

В гл. III было введено понятие о лентах конечного автомата (-лента, табл. 7.1) и последовательностной машины ( -лента, табл. 7.2).

Таблица 7.1

Таблица 7.2

Лента отражает работу конечного автомата (или Я-машины) в том случае, когда задана входная последовательность символов и начальное состояние .

Если рассматривать последовательности символов от до любого такта, то такая последовательность конечна; но поскольку время работы автомата неограниченно, длина каждой последовательности хотя и конечна, но может быть любой, а число возможных последовательностей бесконечно. Автомат (П-машина), находившийся в некотором начальном состоянии ставит в соответствие каждой последовательности символов определенную последовательность символов к (соответственно символов ), т. е. перерабатывает последовательность символов из одного алфавита в последовательность иных символов из иного алфавита.

Каковы общие законы этой переработки последовательностей конечным автоматом или П-машиной?

Пусть К — множество всех возможных последовательностей символов , а Е — множество всех возможных последовательностей символов . Эти множества имеют одинаковую мощность. Значит, каждой последовательности из К можно поставить в соответствие последовательность из Е. Установим это соответствие каким-либо произвольным образом. Можно ли создать конечный автомат, который бы реализовал это соответствие? Или же могут быть указаны такие соответствия между последовательностями, которые можно реализовать в конечном автомате, и такие соответствия, которые конечным автоматом реализовать нельзя? Если существуют соответствия, которые не могут быть реализованы конечным автоматом, то, естественно, возникает задача об отделении соответствий между последовательностями, которые реализуются конечным автоматом, от соответствий, которые не могут быть реализованы никаким конечным автоматом. Аналогичные задачи возникают применительно к последовательностной машине.

Эти же задачи могут быть сформулированы в иных терминах. Рассмотрим -ленту конечного автомата с фиксированным начальным символом . Выделим какой-либо символ . Просматривая ленту, отметим все такты, когда появлялся символ . вательности символов (начиная с такта), которые приводили к появлению символа .

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

Чтобы ответить на эти вопросы, нам придется сначала сформулировать точнее задачу и с этой целью ввести новый термин «событие» и классифицировать события.