§ 7.2. Событие. Представление событий

В ленте автомата (или последовательностной машины) рассмотрим лишь ее верхнюю часть, т. е. только последовательность символов . Назовем ее входной лентой (пример — табл. 7.3).

Таблица 7.3

При фиксированном значении или входная лента конечна. Но может, принимать любое значение, и в этом смысле длина входной ленты не ограничена.

Пусть G — множество всех мыслимых входных лент данного автомата. Пусть далее указан какой-либо признак (критерий), позволяющий выделить из множества G входных лент подмножество . Каков бы ни был этот признак, условимся говорить, что наступило событие всякий раз (т. е. во всякий момент ), когда входная лента автомата, рассмотренная на длине от до такта, относится к выделенному подмножеству .

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

Пример 1. Событие наступает, если в два последних такта работы автомата на входе появлялись последовательно символы .

Событие в момент наступает, например, при появлении входных лент и не наступает, например, при входных лентах

При ленте

событие наступает в моменты и не наступает при всех остальных значениях .

Пример 2. Событие наступает, если в прошедшей части входной ленты хотя бы один раз после символа следовал символ . В этом - случае все ленты, кроме шестой, рассмотренные в предыдущем примере при любом , начиная с некоторого такта, принадлежат множеству . Эта принадлежность множеству имеет место: для ленты 2 при для ленты 3 — при , для ленты 4 — при и т. д.

Приведем теперь несколько формулировок событий без дополнительных пояснений и иллюстраций.

Пример 3. Последние шесть тактов входной ленты содержат последовательность

Пример 4. За последние три такта появилась хотя бы одна из следующих трех последовательностей:

Пример 5. В течение последних трех тактов не встречается символ .

Пример 6. В течение последних пяти тактов, если и встречается символ , то только после символа .

Пример 7. Хотя бы один раз ранее, до момента , встречался символ .

Пример 8. Хотя бы один раз ранее, до момента , после символа , следовал символ .

Пример 9. Ни разу за время работы автомата (т. е. начиная с такта) не встречался символ .

Пример 10. Ни разу после символа с четным индексом не появлялись три раза подряд символы с нечетными индексами.

Пример 11. В третий такт было .

Пример 12. В пятый такт появился какой-либо один из трех символов:

Пример 13. В такты третий, седьмой и девятый появлялись символы с нечетным индексом.

Пример 14. В каждый такт, номер которого кратен трем, появляется символ .

Пример 15. Наступил такт.

Примечание. Множеством в этом случае служит множество всех лент длиной .

Пример 16. Во всех тактах, номера которых совпадают с квадратами целых чисел (), появляется символ с четным индексом.

Пример 17. Всегда, когда номер такта — простое число (2, 3, 5, 7, 11 и т. д.), появляется символ или .

Для того чтобы разумным образом классифициро-. вать события, нам придется предварительно подробнее рассмотреть способы образования множеств входных лент. Этому вопросу посвящен § 7.3.

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

Возникает вопрос: может ли эту же работу выполнить конечный автомат или П-машина? Для того чтобы точно сформулировать этот вопрос, введем понятие о представлении событий автоматом и последовательностной машиной.

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

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

Аналогично последовательностная машина представляет событие появлением символа на выходе, если этот символ появляется в момент тогда и только тогда, когда на входе к моменту происходит событие.

Будем говорить, что событие представимо в конечном автомате, если существует такой конечный автомат А, который представляет событие .

Очевидно, что из представимости событий состояниями из множеств М следует представимость событий появлением единицы на наличии преобразователя, и наоборот. Более того, справедливо и следующее утверждение: из факта представимости (непредставимости) события автоматом следует представимость (непредставимость) его последовательностной машиной, и наоборот.

Это следует из общей теоремы, которая доказана в § 4.3.

Поэтому при решении задачи о представлении событий мы будем рассматривать лишь конечные автоматы.