§ 7.4. Представимость регулярных событий

Мы можем теперь сформулировать и доказать следующие основные теоремы.

Первая теорема Клини. Любое регулярное событие представимо в конечном автомате с выходным преобразователем появлением единицы на выходе преобразователя при подходящем выборе начального состояния автомата.

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

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

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

1) в момент t на дополнительной нитке входа явился символ и

2) появившаяся между моментами последовательность символов принадлежит .

Пусть, например, заданное множество входных последовательностей R включает, три последовательности

Тогда для входной ленты нашего вспомогательного автомата (табл. 7.4) событие наступает в такты 3, 5, 7, 14 и 18 и не наступает во все остальные такты.

Условимся говорить, что вспомогательный автомат - событие появлением 1 на выходе, если на выходе - его преобразователя появляется 1 тогда и только тогда, когда на входе вспомогательного автомата наступает событие .

Таблица 7.4

Представим себе теперь, что имеется автономный автомат с выходным алфавитом и что выход этого автомата отождествлен с ниткой а вспомогательного автомата (рис. 7.1). Полученная сеть в целом является автоматом с единственным входом .

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

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

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

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

Рис. 7.1.

Покажем сначала, как может быть представлено любое регулярное - событие, для которого регулярное выражение R имеет глубину нуль. Затем мы покажем, что если может быть представлено регулярное событие, определяемое регулярным выражением R произвольной глубины , то может быть представлено и любое регулярное -событие, определяемое регулярным выражением R глубины .

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

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

Рис. 7.2.

Теперь построим автомат, представляющий -событие, когда множество R содержит только одну входную последовательность конечной длины . Он состоит (рис. 7.3) из двух линий задержки (каждая линия содержит q элементов задержки) и преобразователя символов. Первая (основная) линия задержки работает в алфавите , вторая двоичном алфавите . На выходе преобразователя символов появляется единица тогда и только тогда, когда символы на выходах всех элементов задержки главной линии формируют заданную последовательность длины q, считая от конца линии задержки к началу.

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

Ясно, что единица на выходе появится тогда и только тогда, когда: 1) q тактов назад на входе а была единица (и поэтому в рассматриваемый момент единица появится на выходе вспомогательной линии задержки) и 2) в течение последних q тактов появилась заданная последовательность символов (и поэтому в рассматриваемый момент появилась единица на выходе преобразователя).

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

В соответствии с рис. 7.3 может быть построен автомат, представляющий -событие, для которого R — любое регулярное выражение глубины нуль.

Рис. 7.3.

Индукция. Покажем теперь, что если существуют вспомогательные автоматы, представляющие -тия, определяемые любыми регулярными выражениями глубины , то можно построить автомат, представляющий - событие, определяемое любым регулярным выражением глубины .

Из определения понятия «глубина регулярного выражения» что любое регулярное выражение глубины получается из одного или двух регулярных выражений глубины v путем однократного применения одной из операций: объединения, умножения или итерации.

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

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

Объединение. Автомат, представляющий объединение

получается из автоматов, представляющих порознь, подводом их выходов к элементу дизъюнкции и объединением их соответствующих входов (рис. 7.4).

Умножение. Автомат, представляющий произведение

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

Для построенного так автомата вспомогательной ниткой входа служит вспомогательная нитка входа автомата а выходом — выход автомата .

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

Рис. 7.4.

Рис. 7.5.

Следовательно, автомат в целом представляет -событие: «непосредственно после события наступило событие , т. е. произведение .

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

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

Этим заканчивается проведение индукции по глубине регулярного выражения и, следовательно, доказательство теоремы.

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

Рис. 7.6.

Второе замечание. Представление события ER отличается от представления события R только способом использования вспомогательной нитки входа автомата, представляющего - событие. Именно, для представления события R эта нитка входа соединяется с пусковым автономным автоматом, подающим единицу только в рервый такт, а для представления события ER к этой нитке подводится выход автомата, представляющего событие Е (рис. 7.2), т. е. подводится единица во все такты.

Это относится, в частности, к представлению определенного события .