§ 7.6. Существуют ли нерегулярные (непредставимые) события?

Мы доказали выше, что всякое регулярное событие представимо в конечном автомате (§ 7.4) и что только оно и может быть представимо (§ 7.5). Но, может быть, любые события регулярны и, следовательно, представимы? Это предположение неверно. Нерегулярные, т. е. непредставимые в автомате события существуют.

Чтобы доказать это, мы здесь рассмотрим примеры нерегулярных событий. Более того, мы выделим целый класс заведомо нерегулярных событий.

Предположим, что задана какая-либо конкретная бесконечная последовательность символов , например

Назовем ее последовательностью . Последовательность назовем «в конечном счете периодической», если, начиная с некоторого символа (считая слева направо), последовательность состоит из периодически повторяющегося отрезка конечной длины.

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

Теорема. Заданная бесконечная последовательность входных символов представима в конечном автомате тогда и только тогда, когда является конечном счете периодической последовательностью».

Доказательство. Докажем сначала, что всякая «в конечном счете периодическая» последовательность представима.

Пусть эта последовательность состоит из «начального отрезка» А конечной длины h и периодически повторяющегося затем «отрезка» В, также конечной длины Т.

Рассмотрим все начальные куски В и отрезка содержит только один первый символ отрезка — два первых символа и т. д.) и начальные куски отрезка . Тогда сформулированное выше событие состоит в том, что входная последовательность должна содержать в качестве начального отрезка отрезок А, затем повторенный произвольное число раз отрезок В, а в конце последовательности должен появиться один из отрезков . Поэтому для указанного события может быть записано регулярное выражение

Значит, согласно первой теореме Клини, это событие представимо в конечном автомате.

Докажем теперь обратное утверждение, что всякая представимая последовательность является «в конечном счете периодической».

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

Составим последовательность , которая отличается от тем, что из нее выброшен отрезок от до , и подадим эту последовательность на вход того же самого автомата. Так, например, если при для последовательности мы имели ленту (табл. которой , то для последовательности лента имеет вид табл. 7.6.

Таблица 7.5

Таблица 7.6

Последовательность символов в первой ленте, начиная с момента (в нашем примере с такта) и далее, точно совпадает с последовательностью , начиная с (в нашем примере с такта) и далее во второй ленте, так как, начиная с этих моментов, при одинаковом исходном состоянии подаются одинаковые входные последовательности. Поэтому из того факта, что последовательность представляется в автомате, следует, что последовательность также представляется в этом автомате. Но это не противоречит определению термина «последовательность представляется в автомате», только если последовательности и совпадают. Две бесконечные последовательности символов, из которых вторая отличается от первой удалением всех символов, расположенных между t и , могут совпадать, только если , начиная от t, состоит из периодически повторяющегося отрезка, расположенного между . Теорема доказана.

Доказанная теорема позволяет построить неограниченное число примеров непредставимых событий. Приведем два таких примера.

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

Пример 2. Событие наступает, если во входной последовательности число символов между двумя не стоящими подряд символами все время удваивается. Так, событие имеет место, если последовательность имеет вид

и не имеет места при последовательности

В обоих этих примерах событие непредставимо, так как соответствующая последовательность не является «в конечном счете периодической».

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

Так, например, при входном алфавите , состоящем из двух символов , событие, заключающееся в том, что к моменту число символов 1 во входной последовательности равно числу символов 0, не относится к рассмотренному выше классу (поскольку наступление этого события определяется не одной конкретной входной последовательностью, а целым их классом), но вместе с тем является непредставимым. Докажем это.

Пусть задан произвольный конечный автомат А. Подадим на его вход последовательность, состоящую из одних нулей. При этом хотя бы одно состояние х автомата должно раньше или позже повториться. Пусть состояние х появилось в моменты и . Рассмотрим следующие две входные последовательности: 1) последовательность состоящую из нулей, за которыми следует единиц, и 2) последовательность состоящую из нулей, за которыми следует единиц. Рассмотрим ленты автомата А при входных последовательностях и (табл. 7.7 и 7.8 соответственно).

Таблица 7.7

Таблица 7.8

Последовательность состояний автомата в ленте, соответствующей , начинающаяся от и кончающаяся при , совпадает с последовательностью состояний в ленте, , начинающейся в и кончающейся при , поскольку исходные состояния (в моменты и соответственно) и входные последовательности единиц подряд) совпадают. Поэтому в моменты времени при входной ленте автомат придет в состояние , совпадающее с состоянием, наступающим в момент при входной ленте . Но при появлении входной последовательности событие наступает (число единиц равно числу нулей), а при входной последовательности не наступает (число единиц больше числа нулей), в то время как состояния автомата в этих случаях окажутся одинаковыми. Это означает, что автомат А не может представить рассматриваемое событие, что и требовалось доказать.

Легко усмотреть причину, из-за которой невозможно представление событий в этих примерах; Она состоит в том, что конечный автомат в силу самого определения (число состояний конечно!) обладает «конечной памятью».

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

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