ГЛАВА 2

Конечные автоматы

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

Как указывалось ранее, конечный автомат состоит из множества состояний и ‘^правления», переводящего из одного состояния в другое в зависимости от получаемых извне «входных данных». Классы автоматов существенно различаются по типу этого управления. Управление может быть «детерминированным» в том смысле, что автомат может находиться в каждый момент времени не более чем в одном состоянии, и «недетерминированным», т.е. автомат может одновременно находиться в нескольких со­стояниях. Мы выясним, что добавление недетерминизма не позволяет определять языки, которые нельзя было бы определить с помощью детерминированных конечных автома­тов. Тем не менее, недетерминированные автоматы оказываются весьма эффективными в приложениях. Именно недетерминизм позволяет нам «программировать» решение задач, используя языки высокого уровня. В этой главе рассматривается алгоритм «компиляции» недетерминированного конечного автомата в детерминированный, который затем может быть «выполнен» на обычной вычислительной машине.

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

Изучение регулярных языков продолжается в главе 3. Там представлен еще один важный способ их описания посредством такой алгебраической нотации, как регулярное выражение. Мы изучим регулярные выражения и покажем их эквивалентность конечным автоматам, чтобы в главе 4 использовать и те, и другие как инструменты для доказатель­ства некоторых важных свойств регулярных языков. Например, свойства «замкнутости», позволяющие утверждать, что некоторый язык является регулярным, на том основании, что один или несколько других языков регулярны. Еще один пример — «разрешимые» свойства, т.е. наличие алгоритмов, позволяющих ответить на вопросы, касающиеся ав­томата или регулярного выражения, например, представляют ли два различных автомата или регулярных выражения один и тот же язык.

2.1. Неформальное знакомство с конечными автоматами

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

Невозможность подделки файла должна быть гарантирована банком и стратегией шифрования. Таким образом, третий участник, банк, должен выпускать и шифровать «денежные» файлы так, чтобы исключить возможность подделки. Но у банка есть и дру­гая важная задача: хранить в своей базе данных информацию о всех выданных им день­гах, годных к платежу. Это нужно для того, чтобы банк мог подтвердить, что получен­ный магазином файл представляет реальные деньги и может быть переведен на счет ма­газина. Мы не будем останавливаться на криптографическом аспекте проблемы, а также на том, каким образом банк может хранить и обрабатывать биллионы «электронных де­нежных счетов». Весьма маловероятно, чтобы эти проблемы привели к каким-нибудь долговременным затруднениям в концепции электронных денег, тем более что они ис­пользуются в относительно небольших масштабах с конца 1990-х годов.

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

2.1.1. Основные правила

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

1. Клиент может совершить оплату (pay) товара, т.е. переслать денежный файл в магазин.
2. Клиент может выполнить отмену (cancel) денег. Они отправляются в банк вместе с сообщением о том, что их сумму следует добавить к банковскому счету клиента.
3. Магазин может произвести доставку {ship) товара клиенту.
4. Магазин может совершить выкуп (redeem) денег. Они отправляются в банк вместе с требованием передать их сумму магазину.
5. Банк может выполнить перевод (transfer) денег, создав новый, надлежащим образом зашифрованный, файл и переслав его магазину.

2.1.2. Протокол

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

Банк должен вести себя ответственно, иначе он не банк. В частности, он должен про­верять, не посылают ли на выкуп два разных магазина один и тот же денежный файл, и не допускать, чтобы одни и те же деньги и отменялись, и выкупались. Магазин тоже должен быть осторожен. Он, например, не должен доставлять товар, пока не убедится, что получил за него деньги, действительные к оплате.

Протоколы такого типа можно представить в виде конечных автоматов. Каждое со­стояние представляет ситуацию, в которой может находиться один из участников. Таким образом, состояние «помнит», что одни важные события произошли, а другие — еще нет. Переходы между состояниями в нашем случае совершаются, когда происходит одно из пяти описанных выше событий. События мы будем считать «внешними» по отношению к автоматам, представляющим трех наших участников, несмотря на то, что каждый из них может инициировать одно или несколько из этих событий. Оказывается, важно не то, кому именно позволено вызывать эти события, а то, какие последовательности событий могут произойти.

На рис. 2.1 участники представлены автоматами. На диаграмме показаны лишь те со­бытия, которые влияют на того или иного участника. Например, действие оплата влияет лишь на клиента и магазин. Банк не знает о том, что клиент отправил деньги в магазин; он узнает об этом, когда магазин выполняет действие выкуп.

Рассмотрим вначале автомат (в), изображающий банк. Его начальное состояние — это состояние 1. Оно соответствует ситуации, когда банк выпустил денежный файл, о ко­тором идет речь, но еще не получил требования на его выкуп или отмену. Если клиент посылает в банк запрос на отмену, то банк восстанавливает деньги на счету клиента и переходит в состояние 2. Оно представляет ситуацию, в которой деньги возвращены клиенту. Поскольку банк в ответе за свои действия, то, попав в состояние 2, он уже не покидает его. Этим он не позволит клиенту вернуть на свой счет с помощью отмены или израсходовать те же самые деньги.^[1]

б) клиент                                             в) банк Рис. 2.1. Конечные автоматы, представляющие клиента, магазин и банк

С другой стороны, находясь в состоянии 1, банк может получить от магазина требо­вание выкупа денег. В этом случае он переходит в состояние 3 и тут же отправляет мага­зину сообщение о переводе, в котором содержится новый денежный файл, принадлежа­щий уже магазину. Отослав это сообщение, банк переходит в состояние 4. В этом со­стоянии он не принимает запросов на отмену или выкуп денег, равно как не совершает никаких других действий с этим конкретным денежным файлом.

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

Магазин начинает в состоянии а. Когда покупатель заказывает товар, выполняя оп­лату, магазин переходит в состояние Ь. В этом состоянии магазин начинает одновремен­но два процесса: доставку товара и выкуп денег. Если первым заканчивается процесс доставки, то магазин переходит в состояние с, в котором он еще должен осуществить выкуп денег и получить перевод эквивалентного денежного файла из банка. Магазин также может сначала отправить в банк запрос на выкуп денег и перейти в состояние d. В состоянии d магазин либо доставит товар и перейдет в состояние е, либо получит из бан­ка денежный перевод и перейдет в состояние/ Следует ожидать, что в состоянии/мага­зин в конце концов доставит товар и перейдет в состояние g. В последнем случае сделка завершена, и ничего больше не происходит. В состоянии е магазин ожидает перевода де­нег из банка. К сожалению, может получиться, что магазину не повезет: товар он доста­вит, а денежного перевода так никогда и не получит.

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

2.1.3. Возможность игнорирования автоматом некоторых действий

Тройка автоматов на рис. 2.1 отображает поведение участников независимо друг от друга, однако некоторые переходы в автоматах пропущены. Так, сообщение об отмене де­нег не затрагивает магазин, и если клиент отменяет деньги, то магазин должен оставаться в том же состоянии, в котором находился. Однако согласно формальному определению ко­нечного автомата, которое мы рассмотрим в разделе 2.2, если на вход автомата подается X, то он должен совершить переход по дуге с меткой X из текущего состояния в некоторое но­вое. Следовательно, к каждому состоянию автомата для магазина нужно добавить еще одну дугу с меткой отмена, ведущую в то же состояние. Тогда при выполнении отмены авто­мат, изображающий магазин, может совершить «переход», который состоит в том, что ав­томат остается в том же состоянии, в котором и был. Если бы этих дополнительных дуг не было, то автомат, изображающий магазин, «умирал» бы, т.е. он не находился бы ни в каком состоянии, и любые его последующие действия были бы невозможны.

Еще одна потенциальная проблема кроется в том, что участники могут, умышленно или случайно, отправить сообщение, не предусмотренное протоколом, и мы не хотим, чтобы это повлекло «смерть» одного из автоматов. Представим, например, что клиент выполнил действие оплата во второй раз, когда магазин находился в состоянии е. По­скольку это состояние не имеет выходящей дуги с меткой оплата, то автомат, изобра­жающий магазин, умрет прежде, чем получит перевод из банка. Итак, к некоторым со­
стояниям автоматов на рис. 2.1 нужно добавить петли с метками, обозначающими дейст­вия, которые следует проигнорировать в этих состояниях. Дополненные таким образом автоматы изображены на рис. 2.2. Для экономии места дуги с разными метками, имею­щие начало и конец в одном и том же состоянии, объединяются в одну дугу с несколь­кими метками. Игнорироваться должны следующие два типа действий.

отмена

Начало

оплата, отмена оплата, отмена оплата, отмена

доставка

а) магазин

оплата, отмена оплата, отмена оплата, отмена оплата, доставка

доставка, выкуп, перевод, оплата, отмена

оплата, выкуп, оплата, выкуп, отмена, доставка отмена, доставка

б)клиент                                               в)банк Рис. 2.2. Полные множества переходов для трех автоматов

перевод

0

Начало                                  Начало

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

2.

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

всем его состояниям, за исключением состояния а (в котором действие оплата уме­стно и ожидаемо). Кроме того, добавлены петли с меткой отмена к состояниям 3 и 4 банка для того, чтобы не допустить смерти автомата банка, если покупатель попыта­ется отменить деньги, которые уже были выкуплены. Банк с полным правом игнори­рует такое требование. Точно так же состояния 3 и 4 имеют петли с меткой выкуп. Магазин не должен пытаться дважды выкупить одни и те же деньги. Но если он все же делает это, то банк совершенно справедливо игнорирует второе требование.

2.1.4. Система в целом как автомат

Обычный способ изучения взаимодействия подобных автоматов состоит в построении так называемого автомата-произведения. Состояниями этого автомата являются пары со­стояний, первое из которых есть состояние магазина, а второе — состояние банка. Напри­мер, состояние автомата-произведения (3, d) представляет ситуацию, когда банк находится в состоянии 3, а магазин — в состоянии d. Поскольку магазин имеет четыре состояния, а банк — семь, то число состояний автомата-произведения равно 4×7 = 28.

Данный автомат-произведение изображен на рис. 2.3. Для ясности все 28 состояний расположены в виде массива, строки которого соответствуют состояниям банка, а столб­цы — состояниям магазина. Кроме того, в целях экономии места дуги помечены буква­ми, каждая из которых соответствует определенному действию: Р — оплата (pay), S — доставка (ship), С — отмена (cancel), R — выкуп (redeem), Т— перевод (transfer).

Чтобы правильно построить дуги в автомате-произведении, нужно проследить «параллельную» работу автоматов банка и магазина. Каждый из двух компонентов авто­мата-произведения совершает, в зависимости от входных действий, различные переходы. Важно отметить, что если, получив на вход некоторое действие, один из этих двух авто­матов не может совершить переход ни в какое состояние, то автомат-произведение «умирает», поскольку также не может перейти ни в какое состояние.

Придадим строгость правилу переходов из одного состояния в другое. Рассмотрим автомат-произведение в состоянии (/, х). Это состояние соответствует ситуации, когда банк находится в состоянии а магазин — в состоянии х. Пусть Z означает одно из входных действий. Мы смотрим, имеет ли автомат банка переход из состояния / с мет­кой Z. Предположим, что такой переход есть, и ведет он в состояние j (которое может совпадать с /, если банк, получив на вход Z, остается в том же состоянии). Затем, глядя на автомат магазина, мы выясняем, есть ли у него дуга с меткой Z, ведущая в некото­рое состояние у. Если j и у существуют, то автомат-произведение содержит дугу из со­стояния (i, х) в состояние (/’, у) с меткой Z. Если же либо состояния J, либо состояния у нет (по той причине, что банк или магазин для входного действия Z не имеет, соответ­ственно, перехода из состояния i или jc), то не существует и дуги с меткой Z, выходя­щей из состояния (/, х).

Теперь ясно, каким образом выбраны дуги на рис. 2.3. Например, получая на вход действие оплата, магазин совершает переход из состояния а в состояние ft, а из любого другого состояния— в него же. Банк же, получая на вход действие оплата, в любом случае сохраняет свое состояние, поскольку это действие его не затрагивает. Эти наблю­дения объясняют, как были построены четыре дуги с меткой Р в четырех столбцах рис. 2.3 и петли с меткой Р для других состояний.

Начало

с              d                 е             /

4                                       Гн-Ю УоУ оо С                    Р,С                  Р.С                  Р.С                    Р.С Р.С                                  Р.С Рис. 2.3. Автомат-произведение для магазина и банка

8^8 6-^6 6^6

Еще один пример выбора дуг мы получим, рассмотрев действие выкуп. Если банк по­лучит запрос на выкуп, находясь в состоянии 1, то он перейдет в состояние 3, а если в со­стоянии 3 или 4 — останется в том же состоянии. Если же он получит это действие на вход, находясь в состоянии 2, то «умрет», т.е. не сможет никуда перейти. С другой сто­роны, магазин, получив на вход выкуп, может из состояния ft перейти в d или из с в е. На рис. 2.3 мы видим шесть дуг с меткой выкуп, соответствующих шести комбинациям из трех состояний банка и двух состояний магазина, имеющих выходящие дуги с меткой R. Например, из состояния (1, ft) дуга с меткой R переводит автомат в состояние (3, d), так как выкуп переводит банк из состояния 1 в 3, а магазин— из ft в d. Еще один пример: существует дуга с меткой R, ведущая из состояния (4, с) в (4, ё), поскольку выкуп пере­водит банк из состояния 4 снова в состояние 4, а магазин — из с в е.

2.1.5. Проверка протокола с помощью автомата-произведения

Из рис. 2.3 можно узнать кое-что интересное. Так, из начального состояния (1, а) — комбинации начальных состояний банка и магазина — можно попасть только в десять из всех 28 состояний. Заметим, что такие состояния, как (2, е) и (4, d), не являются дости­жимыми, т.е. пути, ведущего к ним из начального состояния, не существует. Нет надоб­ности включать в автомат недостижимые состояния, и в нашем случае это сделано ис­ключительно для последовательности изложения.

Однако реальной целью анализа протоколов, подобных данному, с помощью автома­тов является ответ на вопрос: «возможна ли ошибка данного типа?». Простейший при­мер: нас может интересовать, возможно ли, что магазин доставит товар, а оплаты за него так и не получит, т.е. может ли автомат-произведение попасть в состояние, в котором магазин уже завершил доставку (и находится в одном из состояний в столбцах с, е или g), и при этом перехода, соответствующего входу Т, никогда ранее не было и не будет.

К примеру, в состоянии (3, е) товар уже доставлен, но переход в состояние (4, g), со­ответствующий входу Т, в конце концов произойдет. В терминах действий банка это оз­начает, что если банк попал в состояние 3, то он уже получил запрос на выкуп и обрабо­тал его. Значит, он находился в состоянии 1 перед получением этого запроса, не получал требования об отмене и будет игнорировать его в будущем. Таким образом, в конце концов банк переведет деньги магазину.

Однако в случае состояния (2, е) мы сталкиваемся с проблемой. Состояние достижи­мо, но единственная выходящая дуга ведет в него же. Это состояние соответствует си­туации, когда банк получил сообщение об отмене раньше, чем запрос на выкуп. Но ма­газин получил сообщение об оплате, т.е. наш пройдоха-клиент одни и те же деньги и по­тратил, и отменил. Магазин же, по глупости, доставил товар прежде, чем попытался выкупить деньги. Теперь, если магазин выполнит запрос на выкуп, то банк даже не под­твердит получение соответствующего сообщения, так как после отмены, находясь в со­стоянии 2, банк не будет обрабатывать запрос на выкуп.

2.2. Детерминированные конечные автоматы

Теперь пора ввести формальное понятие конечного автомата и уточнить рассуждения и описания из разделов 1.1.1 и 2.1. Начнем с рассмотрения формализма детерминиро­ванного конечного автомата, который, прочитав любую последовательность входных данных, может находиться только в одном состоянии. Термин «детерминированный» го­ворит о том, что для всякой последовательности входных символов существует лишь од­но состояние, в которое автомат может перейти из текущего. В противоположность де­терминированному, «недетерминированный» конечный автомат, который рассматрива­ется в разделе 2.3, может находиться сразу в нескольких состояниях. Под термином «конечный автомат» далее подразумевается автомат детерминированного типа. Но обычно для того, чтобы напомнить читателю, автомат какого типа рассматривается, употребляется слово «детерминированный» или сокращение ДКА (DFA — Deterministic Finite Automaton).

• Определение детерминированного конечного автомата

Детерминированный конечный автомат состоит из следующих компонентов.

1. Конечное множество состояний, обозначаемое обычно как Q.
2. Конечное множество входных символов, обозначаемое обычно как
3. Функция переходов, аргументами которой являются текущее состояние и входной символ, а значением — новое состояние. Функция переходов обычно обозначается как д. Представляя нестрого автомат в виде графа, мы изображали 5 отмеченными дугами, соединяющими состояния. Если q— состояние и а— входной символ, то S(q, а) — это состояние р, для которого существует дуга, отмеченная символом а и ведущая из q в р.^[2]
4. Начальное состояние, одно из состояний в Q.
5. Множество заключительных, или допускающих, состояний F. Множество F является подмножеством Q.

В дальнейшем детерминированный конечный автомат часто обозначается как ДКА. Наиболее компактное представление ДКА— это список пяти вышеуказанных его ком­понентов. В доказательствах ДКА часто трактуется как пятерка

A=(Q,Z,S,q_D, F),

где А — имя ДКА, Q — множество состояний, £ — множество входных символов, <5 — функция переходов, q₀— начальное состояние и F— множество допускающих со­стояний.

• Как ДКА обрабатывает цепочки

Первое, что следует выяснить о ДКА, — это понять, каким образом ДКА решает, «допускать» ли последовательность входных символов. «Язык» ДКА— это множество всех его допустимых цепочек. Пусть а\а₂…а_п — последовательность входных символов. ДКА начинает работу в начальном состоянии q₀. Для того чтобы найти состояние, в ко­торое А перейдет после обработки первого символа а\, мы обращаемся к функции пере­ходов д. Пусть, например, S(q₀, ai) — q\. Для следующего входного символа а₂ находим <5(<7i, а₂). Пусть это будет состояние q₂. Аналогично находятся и последующие состояния <7з, <74, …, q_n, где S(q,.\, а,) = <7, для каждого i. Если q„ принадлежит множеству F, то вход­ная последовательность а\а₂…а_п допускается, в противном случае она «отвергается» как недопустимая.

Пример 2.1. Определим формально ДКА, допускающий цепочки из 0 и 1, которые содержат в себе подцепочку 01. Этот язык можно описать следующим образом:

{w | w имеет видхОГу, где* и у — цепочки, состоящие только из 0 и 1}.

Можно дать и другое, эквивалентное описание, содержащее хну слева от вертикаль­ной черты:

{xOly | х и у — некоторые цепочки, состоящие из 0 и 1}.

Примерами цепочек этого языка являются цепочки 01, 11010 и 1000111. В каче­стве примеров цепочек, не принадлежащих данному языку, можно взять цепочки £, 0 и 111000.

Что мы знаем об автомате, допускающем цепочки данного языка L1 Во-первых, что алфавитом его входных символов является 2 = {0, 1}. Во-вторых, имеется некоторое множество Q состояний этого автомата. Один из элементов этого множества, скажем, q₀, является его начальным состоянием. Для того чтобы решить, содержит ли входная по­следовательность подцепочку 01, автомат А должен помнить следующие важные факты относительно прочитанных им входных данных.

1. Была ли прочитана последовательность 01? Если это так, то всякая читаемая далее последовательность допустима, т.е. с этого момента автомат будет находиться лишь в допускающих состояниях.
2. Если последовательность 01 еще не считана, то был ли на предыдущем шаге считан символ 0? Если это так, и на данном шаге читается символ 1, то последовательность 01 будет прочитана, и с этого момента автомат будет находиться только в допус­кающих состояниях.
3. Действительно ли последовательность 01 еще не прочитана, и на предыдущем шаге на вход либо ничего не подавалось (состояние начальное), либо был считан символ 1? В этом случае А не перейдет в допускающее состояние до тех пор, пока им не бу­дут считаны символы 0 и сразу за ним 1.

Каждое из этих условий можно представить как некоторое состояние. Условию (3) соответствует начальное состояние q₀. Конечно, находясь в самом начале процесса, нуж­но последовательно прочитать 0 и 1. Но если в состоянии q₀ читается 1, то это нисколько не приближает к ситуации, когда прочитана последовательность 01, поэтому нужно ос­таваться в состоянии <7о- Таким образом, 5{q₀, \) = q₀.

Однако если в состоянии q₀ читается 0, то мы попадаем в условие (2), т.е. 01 еще не прочитаны, но уже прочитан 0. Пусть q₂ обозначает ситуацию, описываемую условием (2). Переход из q₀ по символу 0 имеет вид 8 (q₀, 0) = q₂.

Рассмотрим теперь переходы из состояния q₂. При чтении 0 мы попадаем в ситуацию, которая не лучше предыдущей, но и не хуже. 01 еще не прочитаны, но уже прочитан 0, и теперь ожидается 1. Эта ситуация описывается состоянием q₂, поэтому определим S(q₂, 0) = q₂. Если же в состоянии q₂ читается 1, то становится ясно, что во входной по­следовательности непосредственно за 0 следует 1. Таким образом, можно перейти в до­пускающее состояние, которое обозначается q_{ и соответствует приведенному выше ус­ловию (1), т.е. S(q₂, 1) = q_h

Наконец, нужно построить переходы в состоянии q_x. В этом состоянии уже прочитана последовательность 01, и, независимо от дальнейших событий, мы будем находиться в этом же состоянии, т.е. 8(q_x, 0) = 8(q_x, 1) = q_x.

Таким образом, Q = {qo, q_u q₂}. Ранее упоминалось, что q₀ — начальное, a q_x — един­ственное допускающее состояние автомата, т.е. F= {91}. Итак, полное описание автома­та Л, допускающего язык/, цепочек, содержащих 01 в качестве подцепочки, имеет вид

^{А =} ({<7о, <7ь Чг), {0, 1}, <5, <7о, {<7i}), где <5—функция, описанная выше. □

2.2.3. Более простые представления ДКА

Определение ДКА как пятерки объектов с детальным описанием функции переходов слишком сухое и неудобочитаемое. Существует два более удобных способа описания ав­томатов.

1. Диаграмма переходов, которая представляет собой граф (его пример приведен в раз­деле 2.1).
2. Таблица переходов, дающая табличное представление функции <5. Из нее очевидны состояния и входной алфавит.

Диаграммы переходов

Диаграмма переходов для ДКА вида А = (Q, <5, q₀, F) есть граф, определяемый сле­дующим образом:

а)   всякому состоянию из Q соответствует некоторая вершина;

б)   пусть 8(q, а)=р для некоторого состояния q из Q и входного символа а из Тогда диаграмма переходов должна содержать дугу из вершины q в вершину р, отмеченную а. Если существует несколько входных символов, переводя­щих автомат из состояния q в состояние р, то диаграмма переходов может содержать одну дугу, отмеченную списком этих символов;

в)   диаграмма содержит стрелку в начальное состояние, отмеченную как Нача­ло. Эта стрелка не выходит ни из какого состояния;

г)   вершины, соответствующие допускающим состояниям (состояниям из F), отмечаются двойным кружком. Состояния, не принадлежащие F, изобража­ются простым (одинарным) кружком.

Пример 2.2. На рис. 2.4 изображена диаграмма переходов для ДКА, построенного в примере 2.1 На диаграмме видны три вершины, соответствующие трем состояниям, стрелка Начало, ведущая в начальное состояние q₀, и одно допускающее состояние q\, отмеченное двойным кружком. Из каждого состояния выходят две дуги: одна отмечена О, вторая — 1 (для состояния q\ дуги объединены в одну). Каждая дуга соответствует од­ному из фактов для <5, построенных в примере 2.1. □

1                          о

Рис. 2.4. Диаграмма переходов для ДКА, допускающего все цепочки, которые содержат подцепочку 01

Таблицы переходов

Таблица переходов представляет собой обычное табличное представление функции, подобной <5, которая двум аргументам ставит в соответствие одно значение. Строки таб­лицы соответствуют состояниям, а столбцы — входным символам. На пересечении стро­ки, соответствующей состоянию q, и столбца, соответствующего входному символу а, находится состояние <5 (q, а).

Пример 2.3. На рис. 2.5 представлена таблица переходов, соответствующая функции <5 из примера 2.1. Кроме того, здесь показаны и другие особенности таблицы переходов. На­чальное состояние отмечено стрелкой, а допускающее— звездочкой. Поскольку пропис­ные символы строк и столбцов задают множества состояний и символов, у нас есть вся ин­формация, необходимая для однозначного описания данного конечного автомата. □

	0	1
-><7о	Яг	Яо
*Я\	<7i	<7i
Яг	Яг	<7i

Рис. 2.5. Таблица переходов для ДКА из примера 2.1

2.2.4. Расширение функции переходов на цепочки

Ранее было нестрого обосновано утверждение о том, что всякий ДКА определяет некоторый язык, а именно: множество всех цепочек, приводящих автомат из начально­го состояния в одно из допускающих. В терминах диаграмм переходов язык ДКА — это множество меток вдоль всех путей, ведущих из начального состояния в любое до­пускающее.

Теперь дадим строгое определение языка ДКА. С этой целью определим расширен­ную функцию переходов, которая описывает ситуацию, при которой мы, начиная с про­извольного состояния, отслеживаем произвольную последовательность входных симво­лов. Если 8 — наша функция переходов, то расширенную функцию, построенную по 8,

Л

обозначим 8 . Расширенная функция переходов ставит в соответствие состоянию q и цепочке w состояние р, в которое автомат попадает из состояния q, обработав входную последовательность w. Определим 8 индукцией по длине входной цепочки следую­щим образом.

Л

Базис. 8 (q, £) = q, т.е., находясь в состоянии q и не читая вход, мы остаемся в со­стоянии q.

Индукция. Пусть w — цепочка вида ха, т.е. а — последний символ в цепочке, ах — цепочка, состоящая из всех символов цепочки w, за исключением последнего.^[3] Напри­мер, w = 1101 разбивается над: = 110 и а = 1. Тогда

5(g,w) = 6{6(.q,x),a)                                                                     (2.1)

Выражение (2.1) может показаться довольно громоздким, но его идея проста. Для того чтобы найти 8 (q, w), мы вначале находим 8 (q, х) — состояние, в которое автомат попадает, обработав все символы цепочки w, кроме последнего. Предположим, что это

Л                                                                                                         Л

состояние р, т.е. 8 (q, х) = р. Тогда 8 (q, w) — это состояние, в которое автомат перехо­дит из р при чтении а — последнего символа w. Таким образом, 8 (q, w) = 8 (р, а). Пример 2.4. Построим ДКА, допустимым для которого является язык

L = {w | w содержит четное число 0 и четное число 1}. Вполне естественно, что состояния данного ДКА используются для подсчета числа нулей и единиц. При этом подсчет ведется по модулю 2, т.е. состояния «запоминают», четное или нечетное число 0 или 1 было прочитано на данный момент. Итак, существуют четыре состояния, которые можно описать следующим образом.

q₀ : Прочитано четное число 0 и четное число 1. q\ : Прочитано четное число 0 и нечетное число 1. q₂: Прочитано четное число 1 и нечетное число 0. q-i: Прочитано нечетное число 0 и нечетное число 1.

Состояние qo одновременно является и начальным, и единственным допускающим. Начальным оно является потому, что до того, как будут прочитаны какие-либо входные данные, количество прочитанных и 0, и 1 равно нулю, а нуль — число четное. Это же со­
стояние— единственное допускающее, поскольку в точности описывает условие при­надлежности последовательности из 0 и 1 языку L.

Теперь мы знаем почти все, что нужно для определения ДКА, соответствующего язы­ку L. Это автомат

Начало

Рис. 2.6. Диаграмма переходов для ДКА из примера 2.4

0

Данный ДКА можно также представить таблицей переходов, изображенной на рис. 2.7. Но нам нужно не просто построить ДКА. Мы хотим с его помощью показать, как строится функция 8 по функции переходов 8. Допустим, на вход подается цепочка 110101. Она содержит четное число 0 и 1, поэтому принадлежит данному языку. Таким образом, мы ожидаем, что 8 (q0, 110101) = q0, так как q0— единственное допускающее состояние. Проверим это утверждение. Для проверки требуется найти 8 (q0, w) для всех постепенно нарастающих, начи­ная с £, префиксов w цепочки 110101. Результат этих вычислений выглядит следую­щим образом.

Л = ({<7о, <7ь <72, <7з}> {0, 1}, <5, <7о, {<7о}), где функция переходов <5 изображается диаграммой переходов на рис. 2.6. Заметим, что по каждому символу 0 совершается переход через горизонтальную пунктирную линию. Таким образом, после чтения четного числа символов 0 мы находимся над го­ризонтальной линией, в состоянии q₀ или q_{, а после нечетного числа — под ней, в со­стоянии q₂ или <7₃. Аналогично, символ 1 заставляет нас пересечь вертикальную пунк­тирную линию. Следовательно, после чтения четного числа единиц мы находимся сле­ва от вертикальной линии, в состоянии q₀ или q₂, а после чтения нечетного — справа, в состоянии q_{ или q₃. Эти наблюдения представляют собой нестрогое доказательство того, что данные четыре состояния интерпретируются правильно. Хотя можно и фор­мально, как в примере 1.23, доказать корректность наших утверждений о состояниях, используя совместную индукцию.

	0	1
*-><7о	<72	<7i
*<7i	<7з	<7о
<72	<7о	<7з
<7з	<71	<72

Рис. 2.7. Таблица переходов для ДКА из примера 2.4

• 5 (с/о, £) = с/о-

Л                                                                       Л

• <5 (go, 1) = <5(<5(<?о, е), 1) = 5(<7₀, l) = <7i.
• <5 («ft, И) = <5(5 (<7о, 1), 1) = 5(<7Ь 1) = <7₀.
• 5 (<7о, 110) = 5(5 (<7о, 11), 0) = <5(<7о, 0) = q₂,
• <5 (<7о, 1101) = <5(5 С<7о, 110), 1) = <5(<7₂, 1) = <7₃.
• 8 (<7о, 11010) = <5(5 (<7о, 1101),0) = 5(<7з,0) = <7,.
• 8 (<7о, 110101) = 5(5 (<7о, 11010), 1) = 5(<7ь 1) = <7о. □

Стандартные обозначения и локальные переменные

По прочтении этого раздела может сложиться впечатление, что нужно обязательно пользоваться введенными здесь обозначениями, т.е. функцию переходов обозначать 5, ДКА — буквой А и т.д. Действительно, во всех примерах мы стараемся использо­вать одинаковые переменные для обозначения однотипных объектов. Делается это для того, чтобы легче было вспомнить, о каком типе переменных идет речь. Так, в программах i почти всегда обозначает переменную целого типа. Однако в выборе обозначений для компонентов автомата (или чего-либо другого) мы совершенно сво­бодны. Например, при желании мы можем обозначить ДКА буквой М, а его функцию переходов — буквой Т.

Более того, нет ничего странного в том, что одна и та же переменная обозначает, в зависимости от контекста, разные объекты. Например, функции переходов в приме­рах 2.1 и 2.4 обозначены буквой 5. Но эти две функции являются локальными пере­менными и относятся только к своим примерам. Они значительно отличаются друг от друга и никак не связаны.

2.2.5. Язык ДКА

Теперь можно определить язык ДКА вида А = (Q, X, 5, q₀, F). Этот язык обозначается L(A) и определяется как

L(A) = { w | S (<70, w) принадлежит F}.

Таким образом, язык — множество цепочек, приводящих автомат из состояния q₀ в одно из допускающих состояний. Если язык L есть L(A) для некоторого ДКА А, то гово­рят, что L является регулярным языком.

Пример 2.5. Ранее упоминалось, что если А — ДКА из примера 2.1, то ЦА)— множе­ство цепочек из 0 и 1, содержащих подцепочку 01. Если же А— ДКА из примера 2.4, то ЦА) — множество всех цепочек из 0 и 1, содержащих четное число 0 и четное число 1. □

2.2.6. Упражнения к разделу 2.2

2.2.1. На рис. 2.8 изображена игра «катящиеся шарики». Мраморный шарик бросается в точке А или В. Направляющие рычаги х_х, х₂ и х₃ заставляют шарик катиться влево или вправо. После того как шарик, столкнувшись с рычагом, проходит его, рычаг поворачивается в противоположную сторону, так что следующий ша­рик покатится уже в другую сторону.

А                                    В Рис. 2.8. Игра «катящиеся шарики»

Выполните следующее:

а)     (*) постройте конечный автомат, моделирующий данную игру. Пусть А и В обозначают входы — те места, куда бросается шарик. Допустимость со­ответствует попаданию шарика в точку D, а недопустимость — в точку С;

б)     (!) дайте нестрогое описание этого автомата;

в)      предположим, что рычаги поворачиваются до того, как шарик проходит через них. Как это обстоятельство повлияет на ответ в частях (а) и (б)?

• (*!) Мы определяли S , разбивая цепочку на цепочку и следующий за ней сим­вол (в индуктивной части определения, уравнение 2.1). Однако неформально

л

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

А

входную цепочку в определении S. Покажите, что в действительности

Л             Л Л

<5 (q, ху) = <5 (S (q, х), у) для всякого состояния q и цепочек х и у. Указание. Проведите индукцию по [у|.

Л                                                          Л Л

• (!) Покажите, что <5 (q, ах) — б (5 (q, а), х) для всякого состояния q, цепочки х и входного символа а. Указание. Используйте упражнение 2.2.2.
• Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}:

а)  (*) множество всех цепочек, оканчивающихся на 00;

б)  множество всех цепочек, содержащих три нуля подряд;

в)   множество цепочек, содержащих в качестве подцепочки 011.

• (!) Опишите ДКА, допускающие такие языки над алфавитом {0, 1}:

а)  множество всех цепочек, в которых всякая подцепочка из пяти последова­тельных символов содержит хотя бы два 0;

б)  множество всех цепочек, у которых на десятой позиции справа стоит 1;

в)   множество цепочек, которые начинаются или оканчиваются (или и то, и дру­гое) последовательностью 01;

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

• (!!) Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}:

а)  (*) множество всех цепочек, начинающихся с 1, и если рассматривать их как дво­ичное представление целого числа, то это число кратно 5. Например, цепочки 101,1010 и 1111 принадлежат этому языку, а цепочки 0, 100 и 111 — нет;

б)  множество всех цепочек, запись которых в обратном порядке образует дво­ичное представление целого числа, кратного 5. Примерами цепочек этого языка являются цепочки 0, 10011, 1001100 и 0101.

• Пусть А есть некоторый ДКА и q — его состояние, у которого 8(q, a) = q для любого символа ввода а. Докажите индукцией по длине входной цепочки w, что <5 (q, w) = q для всякой входной цепочки w.
• Пусть А — некоторый ДКА и а — входной символ, причем 8(q, а) = q для всех состояний q автомата А :

а)  докажите индукцией по п, что 5 (q, а») = q для всякого п > О, где сГ — цепоч­ка, состоящая из п символов а;

б)   покажите, что либо {a}* Q L(A), либо {а}* П L(A) = 0.

• (*!) Пусть А = (Q, 5, q₀, {g_f}) — ДКА. Предположим, что для всех а из Е имеет место равенство S(q₀, а) = S(qt, а):

Л                                                           Л

а)  покажите, что для всех w * £ верно равенство S (q₀, w) = 5 (q_f, а);

б)  покажите, что если х— непустая цепочка из L(A), то для всех к> 0, х^к (т.е. цепочках, записанная к раз) также принадлежит L(A).

• (*!) Рассмотрим ДКА со следующей таблицей переходов:

	0	1
->А	А	В
*В	В	А

Опишите неформально язык, допустимый данным ДКА, и докажите индукци­ей по длине входной цепочки, что ваше описание корректно. Указание. Уста­навливая индуктивную гипотезу, разумно сформулировать утверждение о том, какие входные последовательности приводят в каждое состояние, а не только в допускающее.

2.2.11. (!) Выполните задание упражнения 2.2.10 со следующей таблицей переходов.

	0	1
->*А	В	А
*В	с	А
С	с	С

2.3. Недетерминированные конечные автоматы

«Недетерминированный» конечный автомат, или НКА (NFA — Nondeterministic Finite Automaton), обладает свойством находиться в нескольких состояниях одновременно. Эту особенность часто представляют как свойство автомата делать «догадки» относительно его входных данных. Так, если автомат используется для поиска определенных цепочек символов (например, ключевых слов) в текстовой строке большой длины, то в начале поиска полезно «догадаться», что мы находимся в начале одной из этих цепочек, а затем использовать некоторую последовательность состояний для простой проверки того, что символ за символом появляется данная цепочка. Пример приложения такого типа приве­ден в разделе 2.4.

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

2.3.1. Неформальное описание недетерминированного конечного автомата

НКА, как и ДКА, имеют конечное множество состояний, конечное множество вход­ных символов, одно начальное состояние и множество допускающих состояний. Есть также функция переходов, которая, как обычно, обозначается через <5. Различие между ДКА и НКА состоит в типе функции <5. В НКА <5 есть функция, аргументами которой яв­ляются состояние и входной символ (как и в ДКА), а значением — множество, состоя­щее из нуля, одного или нескольких состояний (а не одно состояние, как в ДКА). Прежде чем дать строгое определение НКА, рассмотрим пример.

Пример 2.6. На рис. 2.9 изображен недетерминированный конечный автомат, допус­кающий те и только те цепочки из 0 и 1, которые оканчиваются на 01. Начальным явля­ется состояние q₀, и можно считать, что автомат находится в этом состоянии (а также, возможно, и в других состояниях) до тех пор, пока не «догадается», что на входе нача­лась замыкающая подцепочка 01. Всегда существует вероятность того, что следующий символ не является начальным для замыкающей подцепочки 01, даже если это символ 0. Поэтому состояние q₀ может иметь переходы в себя как по 1, так и по 0.

о, 1

Начало y^N 0                     1

—«кч;———— ►

Рис. 2.9. НКА, допускающий цепочки, которые оканчиваются на 01

Если очередной входной символ — 0, то НКА может предположить, что уже началась замыкающая подпоследовательность 01. Таким образом, дуга с меткой 0 ведет из со­стояния q₀ в q\. Заметим, что из q₀ выходят две дуги, отмеченные символом 0. НКА мо­жет перейти как в q₀, так ив q_u ив действительности переходит в оба эти состояния. Мы убедимся в этом, когда дадим строгое определение НКА. В состоянии <71 наш НКА про­веряет, является ли следующий входной символ единицей. Если это так, то он переходит в состояние q₂ и считает цепочку допустимой.

Заметим, что из состояния q_x дуга, отмеченная нулем, не выходит, а состояние q₂ вооб­ще не имеет выходящих дуг. В этих состояниях пути НКА «умирают», хотя другие пути по- прежнему существуют. В то время как ДКА имеет в каждом состоянии ровно одну выхо­
дящую дугу для каждого входного символа, для НКА такого ограничения нет. На примере рис. 2.9 мы убедились, что числом дуг может быть, например, нуль, один или два.

На рис. 2.10 видно, как НКА обрабатывает цепочку. Показано, что происходит, когда автомат (см. рис. 2.9) получает на вход последовательность 00101. Движение начинается из единственного начального состояния q₀. Когда прочитан первый символ 0, НКА мо­жет перейти в состояние либо q₀, либо q\, а потому переходит в оба эти состояния. Эти два пути представлены на рис. 2.10 вторым столбцом.

% ——— % ————— Яо ———— % ————— % ————— %

0 0 10 1 Рис. 2.10. Состояния, в которых находится НКА в процессе обработки цепочки 00101

Затем читается второй символ 0. Из состояния q₀ вновь можно перейти в q₀ и q_x. Од­нако состояние q\ не имеет переходов по символу 0, и поэтому оно «умирает». Когда по­является третий входной символ, 1, нужно рассмотреть переходы из обоих состояний q₀ nq\. Из состояния q₀ по 1 есть переход только в q₀, а из q_{ — только в q₂. Таким образом, прочитав цепочку 001, НКА находится в состояниях q₀ и q₂. НКА допускает ее, посколь­ку q₂ — допускающее состояние.

Однако чтение входных данных еще не завершено. Четвертый входной символ 0 при­водит к тому, что ветвь, соответствующая q₂, отмирает, в то время как q₀ переходит в q₀ и q\. По последнему символу 1 происходит переход из q₀ в q₀, а из q_x — в q₂. Поскольку мы вновь попали в допускающее состояние, то цепочка 00101 допустима. □

2.3.2. Определение недетерминированного конечного автомата

Теперь мы определим формально понятия, связанные с недетерминированными ко­нечными автоматами, выделив по ходу различия между ДКА и НКА. Структура НКА в основном повторяет структуру ДКА:

А = (Q, Z, <5, go, F). Эти обозначения имеют следующий смысл.

1. Q есть конечное множество состояний.
2. S есть конечное множество входных символов.
3. <7о, один из элементовQ, — начальное состояние.
4. F, подмножество Q, — множество заключительных (или допускающих) состояний.
5. S, функция переходов, — это функция, аргументами которой являются состояние из Q и входной символ из Е, а значением — некоторое подмножество множества Q. Заме­тим, что единственное различие между НКА и ДКА состоит в типе значений функции 8. Для НКА — это множество состояний, а для ДКА — одиночное состояние. Пример 2.7. НКА на рис. 2.9 можно формально задать, как

({<7o,<7I,<72}, {0, 1}, <5, <7о, {<72}), где функция переходов б задается таблицей на рис. 2.11. □

	0	1
-><7о	{<72, <7i}	Ы
<7i	0	{<72}
*<72	0	0

Рис. 2.11. Таблица переходов для ДКА, допускающего цепочки, которые оканчиваются на 01

Заметим, что, как и для ДКА, функцию переходов НКА можно задавать таблицей. Единственное различие состоит в том, что в таблице для НКА на пересечениях строк и столбцов стоят множества, хотя, возможно, и одноэлементные, т.е. содержащие один элемент (singleton). Заметим также, что, когда из некоторого состояния по определенно­му символу перехода нет, на пересечении соответствующих строки и столбца должно стоять 0 — пустое множество.

2.3.3. Расширенная функция переходов

Для НКА, так же, как и для ДКА, нам потребуется расширить функцию 5 до функции 8 , аргументами которой являются состояние q и цепочка входных символов w, а значе­нием — множество состояний, в которые НКА попадает из состояния q, обработав це-

Л

почку w. Эта идея проиллюстрирована на рис. 2.10. По сути, 8 (q, w) есть столбец со­стояний, которые получаются при чтении цепочки w, при условии, что q — единственное

л

состояние в первом столбце. Так, на рис. 2.10 видно, что 8 (q₀, 001) = {q₀, qi}. Формаль-

л

но 8 для НКА определяется следующим образом.

Л

Базис. 8 (q, £)= {q}, т.е., не прочитав никаких входных символов, НКА находится только в том состоянии, в котором начинал.

Индукция. Предположим, цепочка w имеет вид w=xa, где а — последний символ цепоч-

л

ки w, ах — ее оставшаяся часть. Кроме того, предположим, что 8 (q, х) = {р\,р₂,…, •

Пусть к

|J<5 (pi, a) = {г,, г₂, …,г_т}.

Тогда 6(q,w) = {г,, r₂, …, /•„,}. Говоря менее формально, для того, чтобы найти

л                                        л

8 (q; w), нужно найти 5 (q, х), а затем совершить из всех полученных состояний все пе­реходы по символу а.

Л

Пример 2.8. Используем 8 для описания того, как НКА на рис. 2.9 обрабатывает це­почку 00101.

1. Няо,ё)=Ш-
2. S(qo,0) = S(q₀,0)={q₀,qi).
3. 6 {до, 00) = <5(<7о, 0) U 8(_gi, 0) = {q₀, <?,} U 0 = {<7о, qx).
4. б (go, 001) = 8{q₀, 1)U 8{q_u 1) = {,q₀} U {q₂} = {*>, Яг)-
5. S (,7o, 0010) = S (<7o, 0) U <5 (<72, 0) = {q₀, <7,} U 0 = {<7o, <7i}.
6. 5(go,00101) = <5(^o, 1) U 5(91, 1)=ЫиЫ = {Яо,Я2}-

Строка (1) повторяет основное правило. Строку (2) получаем, применяя S к единст­венному состоянию <7о из предыдущей строки. В результате получаем множество {<70, <71}. Строка (3) получается объединением двух состояний предыдущего множества и приме­нением к каждому из них 8 с входным символом 0, т.е. 8{q₀, 0) = {<70, <7i}, и 8(qi, 0) = 0. Для того чтобы получить строку (4), берется объединение d(q₀, 1) ⁼ {<7о} и d(q\, 1) = {<72}. Строки (5) и (6) получены так же, как строки (3) и (4). □

2.3.4. Язык НКА

По нашему описанию НКА допускает цепочку w, если в процессе чтения этой цепоч­ки символов можно выбрать хотя бы одну последовательность переходов в следующие состояния так, чтобы прийти из начального состояния в одно из допускающих. Тот факт, что при другом выборе последовательности переходов по символам цепочки w мы мо­жем попасть в недопускающее состояние или вообще не попасть ни в какое (т.е. после­довательность состояний «умирает»), отнюдь не означает, что w не является допустимой для НКА в целом. Формально, если А = (Q, Е, 8, <70, F) — некоторый НКА, то

L(A)={wj 8 (<70, w)ClF=0}.

Таким образом, L(A) есть множество цепочек w из £*, для которых среди состояний

л

S (<7о, w) есть хотя бы одно допускающее.

Пример 2.9. В качестве примера докажем формально, что НКА на рис. 2.9 допускает язык L = {w | w оканчивается на 01}. Доказательство представляет собой совместную ин­дукцию следующих трех утверждений, характеризующих три состояния.

1. 8 (<7о, w) содержит <70 для всякой цепочки w.
2. б (<7о, w) содержит </, тогда и только тогда, когда w оканчивается на 0.
3. S (с/о, vv) содержит q₂ тогда и только тогда, когда w оканчивается на 01.

Чтобы доказать эти утверждения, нужно рассмотреть, каким образом А может по­пасть в каждое из этих состояний, т.е. каким был последний входной символ, и в каком состоянии находился А непосредственно перед тем, как прочитал этот символ.

Поскольку язык этого автомата есть множество цепочек w, для которых 5 (q₀, ^w) содержит q₂ (так как q₂ — единственное допускающее состояние), то доказа­тельство этих трех утверждений, в частности, доказательство 3, гарантирует, что язык данного НКА есть множество цепочек, оканчивающихся на 01. Доказательство этой теоремы представляет собой индукцию по |и>|, длине цепочки w, начиная с нуля.

А

Базис. Если |н>| = 0, то w = е. В утверждении 1 говорится, что S (q₀, е) содержит q₀. Но

Л

это действительно так в силу базисной части определения <5 . Рассмотрим теперь утвер­ждение 2. Мы знаем, что е не заканчивается на 0, и, кроме того, опять же в силу базисной

л

части определения <5 (q₀, е) не содержит q_x. Таким образом, гипотезы утверждения 2 ти­па «тогда и только тогда» в обе стороны ложны. Поэтому само утверждение является ис­тинным в обе стороны. Доказательство утверждения 3, по сути, повторяет доказательст­во утверждения 2.

Индукция. Допустим, что w = ха, где а есть символ 0 или 1. Можно предположить, что утверждения 1-3 выполняются для х. Нужно доказать их для vv, предположив, что |и>| = и + 1, а = п. Предполагая, что гипотеза индукции верна для п, докажем ее для п+ 1.

1. Нам известно, что <5 (q₀, х) содержит q₀. Поскольку по обоим входным символам 0 и 1 существуют переходы из q₀ в себя, то д (q₀, vv) также содержит q₀. Таким образом, утверждение 1 доказано для
2. {Достаточность) Предположим, что н> оканчивается на 0, т.е. а = 0. Применяя ут-

л

верждение 1 к х, получаем, что <5 (q₀, х) содержит q₀. Поскольку по символу 0 суще­ствует переход из q₀ в q_u заключаем, что д (q₀, w) содержит q_x.

Л

(Необходимость) Допустим, что <5 (q₀, vv) содержит q_x. По диаграмме на рис. 2.9 видно, что единственная возможность попасть в состояние q_x реализуется, когда w имеет вид хО. Это доказывает необходимость в утверждении 2.

3. (Достаточность) Предположим, что н> оканчивается на 01. Тогда если w = ха, то мы знаем, что а = 1, ах оканчивается на 0. Применив утверждение 2 к х, получим, что д (qo,x) содержит q_x. Поскольку по символу 1 существует переход из q_x в q₂, приходим к выводу, что <5 (q₀, vv) содержит q₂.

(Необходимость) Допустим, что <5 (q₀, vv) содержит q₂. По диаграмме на рис. 2.9 видно, что в состояние q₂ можно попасть тогда и только тогда, когда w имеет вид х\

л

и 8 (<7о, х) содержит q\. Применяя утверждение 2 кх, получим, что х оканчивается на

1. Таким образом, w оканчивается на 01, и утверждение 3 доказано.

□

2.3.5. Эквивалентность детерминированных и недетерминированных конечных автоматов

Для многих языков, в частности, для языка цепочек, оканчивающихся на 01 (пример 2.6), построить соответствующий НКА гораздо легче, чем ДКА. Несмотря на это, всякий язык, который описывается некоторым НКА, можно также описать и некото­рым ДКА. Кроме того, этот ДКА имеет, как правило, примерно столько же состояний, сколько и ЙКА, хотя часто содержит больше переходов. Однако в худшем случае наи­меньший ДКА может содержать 2″ состояний, в то время как НКА для того же самого языка имеет всего п состояний.

В доказательстве того, что ДКА обладают всеми возможностями НКА, используется одна важная конструкция, называемая конструкцией подмножеств, поскольку включает построение всех подмножеств множества состояний НКА. Вообще, в доказательствах утверждений об автоматах часто по одному автомату строится другой. Для нас конст­рукция подмножеств важна в качестве примера того, как один автомат описывается в терминах состояний и переходов другого автомата без знания специфики последнего.

Построение подмножеств начинается, исходя из НКА N= (<2n, Z, q₀, F_N). Целью является описание ДКА D = (Q_D, <5d, {<70}, F_D), у которого L(N) = L(D). Отметим, что входные алфавиты этих двух автоматов совпадают, а начальное состояние D есть множе­ство, содержащее только начальное состояние N. Остальные компоненты D строятся следующим образом.

• Q_d есть множество всех подмножеств <2n, или булеан множества <2n. Отметим, что если <2n содержит п состояний, то Q_D будет содержать уже 2″ состояний. Од­нако часто не все они достижимы из начального состояния автомата D. Такие не­достижимые состояния можно «отбросить», поэтому фактически число состояний D может быть гораздо меньше, чем 2″.
• F_d есть множество подмножеств S множества Q_N, для которых S f| Fn * 0, т.е. F_D

состоит из всех множеств состояний N, содержащих хотя бы одно допускающее состояние N.

• Для каждого множества S с <2n и каждого входного символа а из £ 8o(S, а) = (J Ss(p, а).

р и j s

Таким образом, для того, чтобы найти <5d(S, а), мы рассматриваем все состоя­ния р из S, ищем те состояния N, в которые можно попасть из состояния р по символу а, а затем берем объединение множеств найденных состояний по всем состояниям р.

Пример 2.10. Пусть N— автомат на рис. 2.9, допускающий цепочки, которые окан­чиваются на 01. Поскольку множество состояний N есть {qo, qi, qi}, то конструкция под­множеств дает ДКА с 2³ = 8 состояниями, отвечающими всем подмножествам, состав­ленным из этих трех состояний. На рис. 2.12 приведена таблица переходов для получен­ных восьми состояний. Объясним вкратце, как были получены элементы этой таблицы.

	0	1
0	0	0
ы	{<7o, <7i}	Ы
ы	0	Ы
	0	0
{<7о. <7i)	{qo, <71)	{qo, <72}
*{<7о. qi)	{qo, <71}	{qo)
*{<7i. qi)	0	{qi)
*{<7o. <7i. <72}	{qo, <71}	{qo, qi)

Рис. 2.12. Полная конструкция подмножеств для автомата на рис. 2.9

Заметим, что данная таблица, элементами которой являются множества, соответству­ет детерминированному конечному автомату, поскольку состояния построенного ДКА сами являются множествами. Для ясности можно переобозначить состояния. Напри­мер, 0 обозначить как A, {q₀} — как В и т.д. Таблица переходов для ДКА на рис. 2.13 определяет в точности тот же автомат, что и на рис. 2.12, и из ее вида понятно, что эле­ментами таблицы являются одиночные состояния ДКА.

	0	1
A	A	A
->B	E	В
с	A	D
*D	A	A
E	E	F
*F	E	В
*G	A	D
*H	E	F

Рис. 2.13. Переименование состояний на рис. 2.12

Начиная в состоянии В, из всех восьми состояний мы можем попасть только в со­стояния В, Е и F. Остальные пять состояний из начального недостижимы, и поэтому их можно исключить из таблицы. Часто можно избежать построения элементов таблицы переходов для всех подмножеств, что требует экспоненциального времени. Для этого выполняется следующее «ленивое вычисление» подмножеств.

Базис. Мы точно знаем, что одноэлементное множество, состоящее из начального состояния М, является достижимым.

Индукция. Предположим, мы установили, что множество состояний S является дос­тижимым. Тогда для каждого входного символа а нужно найти множество состояний 5o(S, а). Найденные таким образом множества состояний также будут достижимы.

Элементарный пример: нам известно, что Wo} есть одно из состояний ДКА D. Нахо­дим, что <5d({<7o}, 0) = Wo, q_t} и {<7о}, 1) = Wo}- Оба эти факта следуют из диаграммы переходов для автомата на рис. 2.9; как видно, по символу 0 есть переходы из q₀ в q₀ и q_u а по символу 1 — только в q₀. Таким образом, получена вторая строка таблицы перехо­дов ДКА на рис. 2.12.

Одно из найденных множеств, {qo}, уже рассматривалось. Но второе, {q_Q, q_t}, — но­вое, и переходы для него нужно найти: <!b(Wo, q,j, 0) = {q₀, q_t] н <5d(Wo, <?i}, 1) = Wo, qi}. Проследить последние вычисления можно, например, так:

<5d(Wo, <7i}, О = <5n(<7o, О U <5n07i, 1) = Wo} U {qi}= {qo, Чг)-

Теперь получена пятая строка таблицы на рис. 2.12 и одно новое состояние Wo, q₂). Аналогичные вычисления показывают, что

<5d(Wo, qi}, 0) = 8n(q₀, 0) U 8n(q₂, 0) = {q₀, q_{} U 0 = Wo, <7i}, <WWo, qi), 1) = Uqo, 1) U М_Чг, 1) = Wo} U 0 = Wo}.

Эти вычисления дают шестую строку таблицы на рис. 2.12, но при этом не получено ни одного нового множества состояний.

Итак, конструкция подмножеств сошлась; известны все допустимые состояния и со­ответствующие им переходы. Полностью ДКА показан на рис. 2.14. Заметим, что он имеет лишь три состояния. Это число случайно оказалось равным числу состояний НКА на рис. 2.9, по которому строился этот ДКА. Но ДКА на рис. 2.14 имеет шесть перехо­дов, а автомат на рис. 2.9 — лишь четыре. □

0

Начало

Рис. 2.14. ДКА, построенный по НКА на рис. 2.9

На последнем примере мы убедились, что конструкция подмножеств успешно рабо­тает. Теперь докажем это формально. По прочтении последовательности символов w по­строенный нами ДКА находится в состоянии, представляющем собой множество состоя­ний НКА, в которые тот попадает, прочитав эту цепочку. Но допускающие состояния ДКА — это состояния, которые содержат хотя бы одно допускающее состояние НКА, а допустимыми для НКА являются цепочки, приводящие его хотя бы в одно из допускаю­щих состояний. Поэтому можно заключить, что ДКА и НКА допускают в точности одни и те же цепочки. Следовательно, они допускают один и тот же язык.

Теорема 2.11. Если ДКА D = (Q_D, 3d, q₀, F_D) построен по НКА N = (£>_N, Е, <5^, q₀, F\i) посредством конструкции подмножеств, то L(D) = L(N).

Доказательство. Вначале с помощью индукции по |w| покажем, что

Л                                                                             Л

8 d({<7o}, w)= 5 _n(<7o, w).

Л

Заметим, что как для одной, так и для другой функции S , значением является множе-

Л

ство состояний из При этом 8 _D интерпретирует его как состояние из Q_D

л

(являющегося булеаном g_N), а д _N — как подмножество Q^.

л

Базис. Пусть |w| = 0, т.е. w = е. Из базисных частей определений 5 для ДКА и НКА имеем, что как 8 ₀({<7о}, £), так и 8 _N(g₀, е) равны

Индукция. Пусть w имеет длину п + 1, и предположим, что утверждение справедли­во для цепочки длины п. Разобьем w на w = ха, где а — последний символ цепочки w.

А                                                                           Л

Согласно гипотезе индукции 8 d({<7oK х)= 8 _N(q₀, х). Пусть оба эти множества состояний

N представляют собой {р\,рг, ■■■,Pv}-

По индуктивной части определения для НКА

а                                                              к

8 N(<7O, W) = [J5 _н(р„ а).                                      (2.2)

/=1

С другой стороны, конструкция подмножеств дает

к

<5о({р,,р₂, …,рь},а)= (j5_N(pi a).                                                         (2.3)

i=]

Теперь, подставляя (2.3) в индуктивную часть определения для ДКА и используя тот

.                  л

факт, что 8 d({<7o},*)= {PuPi,              получаем:

Л                                                                         к

5D(Wo},w) ⁼ 5_D(5_D(<7o,x),a)) = <5_D({p₁,p₂,…,p_k}_ia)= U<5 _N(p_b а).                                   (2.4)

/=i

Л                         Л

Таким образом, из уравнений (2.2) и (2.4) видно, что 8 d({<7o}, w) = 8 _n(g₀, w). Далее, за-

Л                                                                                               Л

мечая, что и D, и N допускают w тогда и только тогда, когда 8 _D({g₀}, w) или 8 _N(c/o, w) соответственно содержат некоторое состояние из F_N, получаем полное доказательство того, что L(D) = L(N). □

Теорема 2.12. Язык L допустим некоторым ДКА тогда и только тогда, когда он до­пускается некоторым НКА.

Доказательство. Достаточность следует из конструкции подмножеств и тео­ремы 2.11.

(Необходимость) Доказательство этой части не представляет трудности; нам нужно лишь перейти от ДКА к идентичному НКА. Диаграмму переходов для некоторого ДКА можно рассматривать неформально как диаграмму переходов для некоторого НКА, при­чем последний имеет по любому входному символу лишь один переход. Точнее, пусть D = (Q, X, <5о, q₀, F) есть некоторый ДКА. Определим N = (Q, qo, F) как эквивалент­ный ему НКА, где <5n определена следующим правилом.

• Если 5o(q, а) = р, то а) = {р}. Индукцией по Н легко показать, что, если 8 ₀(q, w) = р, то

<5 n(<7o, w) = {р}.

Доказательство предоставляется читателю. Как следствие, D допускает w тогда и только тогда, когда N допускает и>, т.е. L(D) = L(N). □

2.3.6. Плохой случай для конструкции подмножеств

В примере 2.10 мы обнаружили, что число состояний ДКА и число состояний НКА одинаково. Как мы уже говорили, ситуация, когда количества состояний НКА и постро­енного по нему ДКА примерно одинаковы, на практике встречается довольно часто. Од­нако при переходе от НКА к ДКА возможен и экспоненциальный рост числа состояний, т.е. все 2″ состояний, которые могут быть построены по НКА, имеющему п состояний, оказываются достижимыми. В следующем примере мы немного не дойдем до этого пре­дела, но будет ясно, каким образом наименьший ДКА, построенный по НКА с п + 1 со­стояниями, может иметь 2″ состояний.

Пример 2.13. Рассмотрим НКА на рис. 2.15. L(N) есть множество всех цепочек из 0 и 1, у которых я-м символом с конца является 1. Интуиция подсказывает, что ДКА D, до­пускающий данный язык, должен помнить последние п прочитанных символов. По­скольку всего имеется 2″ последовательностей, состоящих из последних п символов, то при числе состояний D меньше 2″ нашлось бы состояние q, в которое D попадает по про­чтении двух разных последовательностей, скажем, aia₂…a„ и bib₂…b_n.

0,1

1                         о, 1                    о, 1 о, 1 >. о, 1

нач1^Ч!у— Ч!^)—^—- <J- *

Рис. 2.15. Этот НКА не имеет эквивалентного ДКА, число состояний которого меньше 2″

Поскольку последовательности различны, они должны различаться символом в неко­торой позиции, например, а, Ф Ь, Предположим (с точностью до симметрии), что а, = 1 и Ь, = 0. Если / = 1, то состояние q должно быть одновременно и допускающим, и недо-
пускающим, поскольку последовательность а\а₂…а_п допустима (п-й символ с конца есть 1), а Ь\Ь₂…Ь_а — нет. Если же i > 1, то рассмотрим состояние р, в которое D попадает из состояния q по прочтении цепочки из / — 1 нулей. Тогда р вновь должно одновременно и быть, и не быть допускающим, так как цепочка ад₊₁…а_пОО…О допустима, а £Д₊₁…6_П00…0 — нет.

Теперь рассмотрим, как работает НКА N на рис. 2.15. Существует состояние q₀, в ко­тором этот НКА находится всегда, независимо от входных символов. Если следующий символ — 1, то N может «догадаться», что эта 1 есть п-й символ с конца. Поэтому одно­временно с переходом в q₀ НКА N переходит в состояние q\. Из состояния q_x по любому символу N переходит в состояние q₂. Следующий символ переводит N в состояние q₃ и так далее, пока п — 1 последующий символ не переведет N в допускающее состояние q_n. Формальные утверждения о работе состояний /V выглядят следующим образом.

1. N находится в состоянии q₀ по прочтении любой входной последовательности w.
2. N находится в состоянии q-_t (; = 1,2, …, п) по прочтении входной последовательно­сти w тогда и только тогда, когда /-й символ с конца w есть 1, т.е. w имеет вид x\a\a₂…ai.i, где а, — входные символы.

«Принцип голубятни»

В примере 2.13 мы использовали важный технический прием, применяемый в раз­личных обоснованиях. Он называется принципом голубятни,^[4] Простыми словами, ес­ли у вас больше голубей, чем клеток для них, и каждый голубь залетает в одну из кле­ток, то хотя бы в одной клетке окажется больше одного голубя. В нашем примере «голубями» являются последовательности из п элементов, а «клетками» — состояния. Поскольку состояний меньше, чем последовательностей, две различные последова­тельности должны вести в одно и то же состояние.

Принцип голубятни может показаться очевидным, но в действительности он зависит от конечности числа клеток. Поэтому он применим к автоматам с конечным числом состояний и неприменим к автоматам, число состояний которых бесконечно. Чтобы убедиться в том, что конечность числа клеток существенна, рассмотрим слу­чай, когда есть бесконечное число клеток, соответствующих целым числам 1, 2, …. Пронумеруем голубей числами 0, 1,2, …, т.е. так, чтобы их было на одного больше, чем клеток. Тогда можно поместить голубя с номером i в (/’+ 1)-ю клетку для всех /’ > 0. Тогда каждый из бесконечного числа голубей попадет в клетку, и никакие два голубя не окажутся в одной клетке.

Мы не доказываем эти утверждения формально. Скажем лишь, что доказательство представляет собой несложную индукцию по |w|, как в примере 2.9. Завершая доказа­тельство того, что данный автомат допускает именно те цепочки, у которых на п-й пози­ции с конца стоит 1, мы рассмотрим утверждение (2) при / = п. В нем говорится, что N находится в состоянии q_n тогда и только тогда, когда п-й символ с конца есть 1. Но q„ яв­ляется единственным допускающим состоянием, поэтому это условие также точно ха­рактеризует множество цепочек, допускаемых автоматом N. □

2.3.7. Упражнения к разделу 2.3

2.3.1. Преобразуйте следующий НКА в эквивалентный НКА.

	0	1
	{р. я\	{р1
я	И	Н
г	И	0
*s		{5}

2.3.2. Преобразуйте следующий НКА в эквивалентный ДКА

	0	1
	{<7>«}	{<?}
*я	{г}	{Я, г]
г	{s}	{р)
*s	0	{.Р}

2.3.3. Преобразуйте следующий НКА в эквивалентный ДКА и опишите неформально язык, который он допускает.

	0	1
	{р>я)	{Р)
Я	{r,s}	U)
г	{.P,r}	м
*s	0	0
*t	0	0

2.3.4. (!) Найдите недетерминированные конечные автоматы, которые допускают следующие языки. Постарайтесь максимально использовать возможности не­детерминизма:

а) (*) множество цепочек над алфавитом {0, 1, …, 9}, последняя цифра которых встречается еще где-то в них;

Дьявольские состояния и ДКА с неопределенными переходами

Формально определяя ДКА, мы требовали, чтобы по каждому входному символу он имел переход в одно и только одно состояние. Однако иногда бывает более удобно устроить ДКА таким образом, чтобы он «умирал» в ситуации, когда входная последо­вательность уже не может быть допустимой, что бы к ней ни добавлялось. Рассмот­рим, например, автомат на рис. 1.2, единственной задачей которого является распо­знавание одиночного ключевого слова then. Чисто технически, данный автомат не является ДКА, так как для каждого состояния в нем отсутствуют переходы по боль­шинству входных символов.

Но этот автомат является НКА. И если посредством конструкции подмножеств пре­вратить его в ДКА, то вид автомата практически не изменится, хотя при этом в нем появится дьявольское состояние, которое не является допускающим и переходит са­мо в себя по любому символу. Это состояние соответствует 0 — пустому множеству состояний автомата на рис. 1.2.

Вообще говоря, можно добавить дьявольское состояние в любой автомат, если он имеет не более одного перехода для всякого состояния и входного символа. Тогда до­бавляется переход в дьявольское состояние из остальных состояний q по всем симво­лам, для которых переход из q не определен. В результате получается ДКА в точном смысле слова. Поэтому иногда будем говорить об автомате как о ДКА, если он имеет не более одного перехода из любого состояния по любому входному символу, а не только в случае, когда он имеет только один переход.

б)  множество цепочек над алфавитом {0, 1, …,9}, последняя цифра цепочки которых больше нигде в них не встречается;

в)   множество цепочек из 0 и 1, в которых содержится два 0, разделенных пози­циями в количестве, кратном 4. Отметим, что нуль позиций можно также считать кратным 4.

• В части «необходимость» теоремы 2.12 было пропущено индуктивное доказа-

Л                              л

тельство того, что если <5 _D(q, w) = р, то <5 _N(q, w) = {р}, где индукция велась бы по |w|. Приведите это доказательство.

• (!) В замечании «Дьявольские состояния и ДКА с неопределенными пере­ходами» утверждалось, что если НКА N по каждому входному символу со­держит переход не более чем в одно состояние (т.е. 5{q, а) есть не более чем одноэлементное множество), то ДКА D, построенный по N с помощью конст­рукции подмножеств, содержит точно те же состояния и переходы, что и N, плюс переходы в новое дьявольское состояние из тех состояний и по тем входным символам, для которых переходы N не определены. Докажите это утверждение.

2.3.7. В примере 2.13 утверждалось, что НКА находится в состоянии (/’ = 1, 2, …, ri) по прочтении входной последовательности w тогда и только тогда, когда г-й символ с конца есть 1. Докажите это утверждение.

2.4. Приложение: поиск в тексте

В предыдущем разделе была рассмотрена абстрактная «проблема», состоявшая в том, что нужно было выяснить, оканчивается ли данная последовательность двоичных чисел на 01. В этом разделе мы увидим, что подобного рода абстракции прекрасно подходят для описания таких реальных задач, возникающих в приложениях, как поиск в сети Inter­net н извлечение информации из текста.

2.4.1. Поиск цепочек в тексте

В век Internet и электронных библиотек с непрерывным доступом обычной является следующая проблема. Задано некоторое множество слов, и требуется найти все докумен­ты, в которых содержится одно (или все) из них. Популярным примером такого процесса служит работа поисковой машины, которая использует специальную технологию поиска, называемую обращенными индексами (inverted indexes). Для каждого слова, встречаю­щегося в Internet (а их около 100,000,000), хранится список адресов всех мест, где оно встречается. Машины с очень большим объемом оперативной памяти обеспечивают по­стоянный доступ к наиболее востребованным из этих списков, позволяя многим людям одновременно осуществлять поиск документов.

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

1. Содержимое хранилища текста, в котором производится поиск, быстро меняется.

Вот два примера:

а)  каждый день аналитики ищут статьи со свежими новостями по соответст­вующим темам. К примеру, финансовый аналитик может искать статьи с оп­ределенными аббревиатурами ценных бумаг или названиями компаний;

б)  «робот-закупщик» по требованию клиента отслеживает текущие цены по оп­ределенным наименованиям товаров. Он извлекает из сети страницы, содер­жащие каталоги, а затем просматривает эти страницы в поисках информации о ценах по конкретному наименованию.

2. Документы, поиск которых осуществляется, не могут быть каталогизированы. На­пример, очень непросто отыскать в сети все страницы, содержащие информацию обо всех книгах, которые продает компания Amazon.com, поскольку эти страницы генерируются как бы «на ходу» в ответ на запрос. Однако мы можем отправить за­прос на книги по определенной теме, скажем, «конечные автоматы», а затем искать в той части текста, которая содержится на появившихся страницах, определенное сло­во, например слово «прекрасно».

2.4.2. Недетерминированные конечные автоматы для поиска в тексте

Пусть нам дано множество слов, которые мы в дальнейшем будем называть ключе­выми словами, и нужно отыскать в тексте места, где встречается любое из этих слов. В подобных приложениях бывает полезно построить недетерминированный конечный ав­томат, который, попадая в одно из допускающих состояний, дает знать, что встретил од­но из ключевых слов. Текст документа, символ за символом, подается на вход НКА, ко­торый затем распознает в нем ключевые слова. Существует простая форма НКА, распо­знающего множество ключевых слов.

1. Есть начальное состояние с переходом в себя по каждому входному символу, на­пример, печатному символу ASCII при просмотре текста. Начальное состояние можно представлять себе, как «угадывание» того, что ни одно из ключевых слов еще не началось, даже если несколько букв одного из ключевых слов уже прочитано.
2. Для каждого ключевого слова а\а₂…а_к имеется к состояний, скажем q_u q₂,

Для входного символа а_х есть переход из начального состояния в q_x, для входного символа а₂ — переход из q_x в q₂ и т.д. Состояние q_k является допускающим и сигна­лизирует о том, что ключевое слово а,а₂…а_к обнаружено.

Пример 2.14. Предположим, что мы хотим построить НКА, распознающий слова web и ebay. Диаграмма переходов данного НКА, изображенная на рис. 2.16, построена с помощью изложенных выше правил. Начальное состояние — это состояние 1, а £ обо­значает множество печатаемых символов ASCII. Состояния 2-4 отвечают за распознава­ние слова web, а состояния 5-8 — за распознавание слова ebay. □

На

Рис. 2.16. НКА, осуществляющий поиск слов web и ebay

Безусловно, НКА — не программа. Для реализации данного НКА у нас есть две ос­новные возможности.

1. Написать программу, имитирующую работу данного НКА путем вычисления мно­жества состояний, в которых он находится по прочтении каждого из входных сим­волов. Такая реализация была рассмотрена на рис. 2.10.
2. Преобразовать данный НКА в эквивалентный ему ДКА, используя конструкцию подмножеств. Затем непосредственно реализовать ДКА.

В некоторых программах, обрабатывающих текст, таких, например, как наиболее продвинутые версии команды grep (egrep и fgrep) операционной системы UNIX, используется комбинация этих двух подходов. Однако в нашем случае более удобно пре­образование к ДКА, так как это, во-первых, просто, а во-вторых, гарантирует, что число состояний при этом не возрастет.

2.4.3. ДКА, распознающий множество ключевых слов

Конструкция подмножеств применима к любому НКА. Но, применяя ее к НКА, по­строенному по множеству ключевых слов, как в разделе 2.4.2, мы обнаружим, что число состояний соответствующего ДКА никогда не превосходит числа состояний этого НКА. А поскольку нам известно, что при переходе к ДКА в худшем случае может произойти экспоненциальный рост числа состояний, то последнее замечание ободряет и объясняет, почему для распознавания ключевых слов так часто используется метод построения со­ответствующего НКА, а по нему — ДКА. Правила, в соответствии с которыми строятся состояния ДКА, состоят в следующем:

а)  если <7о — начальное состояние НКА, то {q₀} — одно из состояний ДКА;

б)  допустим, р — одно из состояний НКА, и НКА попадает в него из начально­го состояния по пути, отмеченному символами а\а2—.а_т. Тогда одним из со­стояний ДКА является множество, состоящее из q₀, р и всех остальных со­стояний НКА, в которые можно попасть из q₀ по пути, отмеченному суффик­сом (окончанием) цепочки aia₂…a_m, т.е. последовательностью символов вида a_sa_s+\…a_m.

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

Пример 2.15. На рис. 2.17 показано, как по НКА (см. рис. 2.16) построен ДКА. Каж­дое из состояний ДКА расположено на том же самом месте, что и состояние р, по кото­рому оно построено, в соответствии с приведенным выше правилом (б). Рассмотрим, на­пример, состояние {1, 3, 5}, обозначенное для краткости как 135. Это состояние было построено по состоянию 3. Как и всякое множество состояний нашего ДКА, оно включа­ет состояние 1. Кроме того, оно включает состояние 5, так как в него автомат попадает из 1 по окончанию е цепочки we, приводящей в состояние 3 на рис. 2.16.

1-е

Рис. 2.17. Преобразовование НКА, изображенного нарис. 2.16, в ДКА

Для каждого из состояний ДКА переходы могут быть найдены с помощью конструк­ции подмножеств. Но тут можно поступить проще. Для всякого множества состояний, включающего начальное состояние q₀ и некоторые другие состояния р\,р₂, ■■■■,Рп, и для каждого входного символа х вычислим те состояния НКА, в которые по х переходят р\. Тогда данное состояние ДКА, т.е. {q₀, р\, рг, ■ ■■, р_а}, будет иметь переход по символу х в состояние ДКА, содержащее q₀ и все те состояния, в которые переходят р\. По всем тем символам х, по которым переходов ни из одного р_л нет, данный ДКА будет иметь пере­ход по символу х в состояние, содержащее q₀ и все те состояния исходного НКА, кото­рые достигаются переходом из q₀ по дуге с меткой х.

Рассмотрим состояние 135 на рис. 2.17. НКА на рис. 2.16 имеет переходы по символу b из состояний 3 и 5 в состояния 4 и 6, соответственно. Следовательно, 135 по b перехо­дит в 146. По входному символу е переходов из состояний НКА 3 и 5 нет, но есть пере­ход из 1 в 5. Таким образом, по е ДКА переходит из 135 в 15. Точно так же, now 135 пе­реходит в 12.

По любому другому символу х переходов из состояний 3 и 5 нет, а состояние 1 имеет переход только в себя. Таким образом, по любому символу из Z, за исключением b, е и w, 135 переходит в 1. Обозначим это множество как I, — b — е -w, а также используем подобные обозначения для других множеств, получающихся из X удалением нескольких символов. □

2.4.4. Упражнения к разделу 2.4

• Постройте НКА, распознающие следующие множества цепочек:

а)   (*) abc, abd и aacd. Входным алфавитом считать {а, Ь, с, d};

б)   0101, 101 и 011;

в)   ab, be и са. Входным алфавитом считать {а, Ь, с}.

• Преобразуйте ваши НКА из упражнения 2.4.1 в ДКА.

2.5. Конечные автоматы с эпсилон-переходами

Рассмотрим еще одно обобщение понятия конечного автомата. Придадим автомату новое «свойство» — возможность совершать переходы по е, пустой цепочке, т.е. спон­танно, не получая на вход никакого символа. Эта новая возможность, как и недетерми­низм, введенный в разделе 2.3, не расширяет класса языков, допустимых конечными ав­томатами, но дает некоторое дополнительное «удобство программирования». Кроме то­го, рассмотрев в разделе 3.1 регулярные выражения, мы увидим, что последние тесно связаны с НКА, имеющими е-переходы. Такие автоматы будем называть е-НКА. Они оказываются полезными при доказательстве эквивалентности между классами языков, задаваемых конечными автоматами и регулярными выражениями.

2.5.1. Использование е-переходов

Вначале будем оперировать с е-НКА неформально, используя диаграммы переходов с Е в качестве возможной метки. В следующих примерах автомат можно рассматривать как допускающий последовательности меток, среди которых могут быть е, вдоль путей из начального состояния в допускающее. Но при этом каждое е вдоль пути «невидимо», т.е. в последовательность ничего не добавляет.

Пример 2.16. На рис. 2.18 изображен е-НКА, допускающий десятичные числа, кото­рые состоят из следующих элементов.

1. Необязательный знак + или -.
2. Цепочка цифр.
3. Разделяющая десятичная точка.
4. Еще одна цепочка цифр. Эта цепочка, как и цепочка (2), может быть пустой, но хотя бы одна из них непуста.

0,1,…,9

0,1,…,9

Рис. 2.18. е-НКА, допускающий десятичные числа

Особого интереса заслуживает переход из состояния q₀ в q_x по любому из символов +, — или е. Состояние q_u таким образом, представляет ситуацию, когда прочитан знак числа, если он есть, но не прочитана ни одна из цифр, ни десятичная точка. Состояние q₂ соот­ветствует ситуации, когда только что прочитана десятичная точка, а цифры целой части числа либо уже были прочитаны, либо нет. В состоянии q₄ уже наверняка прочитана хотя бы одна цифра, но еще не прочитана десятичная точка. Таким образом, q₃ интерпретиру­ется как ситуация, когда мы прочитали десятичную точку и хотя бы одну цифру слева или справа от нее. Мы можем оставаться в состоянии q₃, продолжая читать цифры, но можем и «догадаться», что цепочка цифр закончена, и спонтанно перейти в допускающее состояние <75. □

Пример 2.17. Метод распознавания множества ключевых слов, предложенный в примере 2.14, можно упростить, разрешив е-переходы. Например, НКА на рис. 2.16, распознающий ключевые слова web и ebay, можно реализовать и с помощью е- переходов, как показано на рис. 2.19. Суть в том, что для каждого ключевого слова строится полная последовательность состояний, как если бы это было единственное слово, которое автомат должен распознавать. Затем добавляется новое начальное со­стояние (состояние 9 на рис. 2.19) с е-переходами в начальные состояния автоматов для каждого из ключевых слов. □

Начало

е

2.19. Использование e-переходов для распознавания ключевых слов

2.5.2. Формальная запись е-НКА

£-НКА можно представлять точно так же, как и НКА, с той лишь разницей, что функ­ция переходов должна содержать информацию о переходах по £. Формально, £-НКА А можно представить в виде А = (Q, Е, <5, q₀, F), где все компоненты имеют тот же смысл, что и для НКА, за исключением <5, аргументами которой теперь являются состояние из Q и элемент множества Е U{£}, т.е. либо некоторый входной символ, либо £. Никаких не­доразумений при этом не возникает, поскольку мы оговариваем, что £, символ пустой цепочки, не является элементом алфавита 2.

Пример 2.18. £-НКА на рис. 2.18 можно формально представить как

£ = ({<?<), <?1, …,<?5}, {•, +, о, 1, …, 9}, <5, q₀, {<?₅}), где функция переходов <5 определена таблицей переходов на рис. 2.20. □

	£			0, 1, …, 9
<7о	{<?!}	Ы	0	0
<7i	0	0	{<72}	{<?1, <?4}
<72	0	0	0	{<7з}
<7з	{<75}	0	0	{<7з}
<74	0	0	{<7з}	0
<75	0	0	0	0

Рис. 2.20. Таблица переходов к рис. 2.18

2.5.3. Что такое е-замыкание

Дадим формальное определение расширенной функции переходов для £-НКА, кото­рое приведет к определению допустимости цепочек и языков для данного типа автоматов и в конце концов поможет понять, почему ДКА могут имитировать работу £-НКА. Одна­ко прежде нужно определить одно из центральных понятий, так называемое е-замыкание состояния. Говоря нестрого, мы получаем £-замыкание состояния q, совершая все воз­можные переходы из этого состояния, отмеченные е. Но после совершения этих перехо­дов и получения новых состояний снова выполняются £-переходы, уже из новых состоя­ний, и т.д. В конце концов, мы находим все состояния, в которые можно попасть из q по любому пути, каждый переход в котором отмечен символом е. Формально мы определя­ем е-замыкание, ECLOSE, рекурсивно следующим образом.

Базис. ECLOSE(g) содержит состояние q.

Индукция. Если ECLOSE(g) содержит состояние р, и существует переход, отмечен­ный £, из состояния р в состояние г, то ECLOSE(g) содержит г. Точнее, если <5 есть функ­ция переходов рассматриваемого е-НКА и ECLOSE(g) содержит р, то ECLOSE(g) содер­жит также все состояния из д{р, е).

Пример 2.19. У автомата, изображенного на рис. 2.18, каждое состояние является собственным е-замыканием, за исключением того, что ECLOSE^o)⁼ {q₀, q\} и ECLOSE(g₃) = {q_h q_}). Это объясняется тем, что имеется лишь два е-перехода, один из которых добавляет Ц\ в ECLOSE(c/₀), а другой — q₅ в ECLOSE(c/₅).

На рис. 2.21 приведен более сложный пример. Для данного в нем набора состояний, который может быть частью некоторого е-НКА, мы можем заключить, что

ECLOSE(l)= {1,2, 3,4, 6}.

Рис. 2.21. Несколько состояний и переходов

В каждое из этих состояний можно попасть из состояния 1, следуя по пути, отмечен­ному исключительно е. К примеру, в состояние 6 можно попасть по пути 1—>2—>3—>6. Состояние 7 не принадлежит ECLOSE(l), поскольку, хотя в него и можно попасть из состояния 1, в соответствующем пути содержится переход 4—>5, отмеченный не е. И не важно, что в состояние 6 можно попасть из состояния 1, следуя также по пути 1 —>4—>5—>6, в котором присутствует не е-переход. Существования одного пути, от­меченного только е, уже достаточно для того, чтобы состояние 6 содержалось в ECLOSE(l). □

2.5.4. Расширенные переходы и языки е-НКА

С помощью е-замыкания легко объяснить, как будут выглядеть переходы е-НКА для заданной последовательности входных (не-е) символов. Исходя из этого, можно опреде­лить, что означает для е-НКА допустимость входных данных.

Пусть Е = (Q, Z, <5, q₀, F) — некоторый е-НКА. Для отображения того, что происходит при чтении некоторой последовательности символов, сначала определим 8 — расши­ренную функцию переходов. Замысел таков: определить <5 (q, vv) как множество состоя­ний, в которые можно попасть по путям, конкантенации меток вдоль которых дают це­почку w. При этом, как и всегда, символы е, встречающиеся вдоль пути, ничего не до­бавляют к w. Соответствующее рекурсивное определение 8 имеет следующий вид.

Базис. 8 (q, e) = ECLOSE(<7). Таким образом, если £— метка пути, то мы можем со­вершать переходы лишь по дугам с меткой е, начиная с состояния q; это дает нам в точ­ности то же, что и ECLOSE(g).

Индукция. Предположим, что w имеет вид ха, где а — последний символ w. Отме­тим, что а есть элемент 2 и, следовательно, не может быть е, так как £ не принадлежит Z. Мы вычисляем 8 (q, vv) следующим образом.

Л

1. Пусть {р 1, р2, . Рк} есть 8 (q, х), т.е. /;, — это все те и только те состояния, в кото­рые можно попасть из q по пути, отмеченному х. Этот путь может оканчиваться од­ним или несколькими е-переходами, а также содержать и другие £-переходы.

к

2. Пусть (J<5 (pi, а) есть множество {г_ь г₂, …, /*_т}, т.е. нужно совершить все переходы,

/=1

отмеченные символом а, из тех состояний, в которые мы можем попасть из q по пу­ти, отмеченному х. Состояния г\ — лишь некоторые из тех, в которые мы можем попасть из q по пути, отмеченному w. В остальные такие состояния можно попасть из состояний г\ посредством переходов с меткой е, как описано ниже в (3).

л                             ^т

3. 8 (q, vv) = IJ ECLOSE(rj). На этом дополнительном шаге, где мы берем замыкание

и добавляем все выходящие из q пути, отмеченные w, учитывается возможность су­ществования дополнительных дуг, отмеченных е, переход по которым может быть совершен после перехода по последнему «непустому» символу а.

Пример 2.20. Вычислим 5 (до, 5 . 6) для £-НКА на рис. 2.18. Для этого выполним следующие шаги.

• 5 (go, £) = ECLOSE^o) = {<?₀,<7i}.
• Вычисляем 8 (cj_n, 5) следующим образом.
  1. Находим переходы по символу 5 из состояний q₀ и q_u полученных при вычислении

Л

8 (q₀, £): 8(qo, 5) U <5(<?i, 5) = {q_u q_A).

2. Находим £-замыкание элементов, вычисленных на шаге (1). Получаем: ECLOSEOyO U ECLOSE(<jr₄) = {<5^} U {<74} ⁼ {<7ь Яа}, т.е. множество 8 (q₀, 5).

Эта двушаговая схема применяется к следующим двум символам.

• Вычисляем 8 (q₀, 5 .).
  1. Сначала <5(<7i, — )U<5(<74, )= {<?г} U {<?з} = {<?2, <?з}-
  2. Затем 8 (q₀, 5 .) = ECLOSE(«7₂) U ECLOSE^) = {<72} U {<?з, <?s} = U/2, <?з, q₅}.
• Наконец, вычисляем 8 (q₀, 5 . 6).
  1. Сначала <5(q₂, 6) U d(q₃, 6) U S(q₅, б) = {q₃} U Ы U 0 = {<?з}.
  2. Затем 5 (q₀, 6) = ECLOSEO^) = {q₃, q₅}-

□

Теперь можно определить язык £-НКА Е = (Q, 2, <5, с/₀, F) так, как и было задумано ранее: L(E) = {w \ 8 (q, w) f| F Ф 0}. Таким образом, язык £— это множество цепочек w, которые переводят автомат из начального состояния хотя бы в одно из допускающих. Так, в примере 2.20 мы видели, что 8 (q₀, 5 . 6) содержит допускающее состояние q₅, по­этому цепочка 5 . 6 принадлежит языку £-НКА.

2.5.5. Устранение е-переходов

Для всякого £-НКА Е можно найти ДКА D, допускающий тот же язык, что и Е. По­скольку состояния D являются подмножествами из состояний Е, то используемая конст­рукция очень напоминает конструкцию подмножеств. Единственное отличие состоит в том, что нужно присоединить еще и £-переходы Е, применив механизм £-замыкания.

Пусть Е = (Q_e, 2, <$е, qE, Fe)- Тогда эквивалентный ДКА

D = (2_d, 2, q_D, F_d) определяется следующим образом.

1. Q_d есть множество подмножеств Q_E. Точнее, как мы выясним, для D допустимыми состояниями являются только е-замкнутые подмножества Qe, т.е. такие множе­ства S с Qe, для которых S = ECLOSE(S). Иначе говоря, £-замкнутые множества состояний S— это такие множества, у которых всякий £-переход из состояния, принадлежащего S, приводит снова в состояние из S. Заметим, что 0 есть £-зам- кнутое множество.
2. q_D — ECLOSE(go), т.е., замыкая множество, содержащее только начальное состояние Е, мы получаем начальное состояние D. Заметим, что это правило отличается от ис­пользованного ранее в конструкции подмножеств — там за начальное состояние по­строенного автомата принималось множество, содержащее только начальное со­стояние данного НКА.
3. F_d — это такие множества состояний, которые содержат хотя бы одно допускающее состояние автомата Е. Таким образом, F_D = {S | S принадлежит Q_D и S f| F_E Ф 0}.
4. 8o(S, а) для всех а из 2 и множеств S из Q_D вычисляется следующим образом:

а)   nycTbS= {puPi,

k

б)   вычислим (J<5 (pi, а); пусть это будет множество {г_ь г₂, …, /-,„};

(=i

т

в)   тогда 8o(S, а) = [J ECLOSE(/-j).

Пример 2.21. Удалим е-переходы из е-НКА (см. рис. 2.18), который далее называется Е. По Е мы строим ДКА D, изображенный на рис. 2.22. Для того чтобы избежать излиш­него нагромождения, мы удалили на рис. 2.22 дьявольское состояние 0 и все переходы в него. Поэтому, глядя на рис. 2.22, следует иметь в виду, что у каждого состояния есть еще дополнительные переходы в состояние 0 по тем входным символам, для которых переход на рисунке отсутствует. Кроме того, у состояния 0 есть переход в себя по лю­бому входному символу.

0,1   9 0,1,…,9 0,1,…,9 Рис. 2.22. ДКА D, полученный устранением е-переходов на рис. 2.18

Поскольку начальное состояние Е— это qo, начальным состоянием D является ECLOSE(g₀), т.е. множество {q₀, q{\. В первую очередь нужно найти состояния, в кото­рые переходят q₀ и q_x по различным символам из Z; напомним, что это знаки плюс и ми­нус, точка и цифры от 0 до 9. Как видно на рис. 2.18, по символам + и — qi никуда не пе­реходит, в то время как q₀ переходит в q_{. Таким образом, чтобы вычислить mio, <7i}> +)> нужно взять е-замыкание {q\}. Поскольку е-переходов, выходящих из q_u нет, получаем, что 5o({q₀, q_x), +) = {q_x}. Точно так же находится (5_D({go, <7ih -)⁼ {<7i}- Эти два перехода изображены одной дугой на рис. 2.22.

Теперь найдем <^({<7о, <?ib •)• Как видно на рис. 2.18, по точке q₀ никуда не перехо­дит, a qi переходит в q₂. Поэтому нужно взять замыкание {<72}- Но состояние q₂ является собственным замыканием, так как £-переходов из него нет.

И, наконец, в качестве примера перехода из {q₀, q 1} по произвольной цифре найдем 5o({qo, qi), 0). По цифре q₀ никуда не переходит, a q_x переходит сразу в q_x и q_A. Так как ни одно из этих состояний не имеет выходящих £-переходов, делаем вывод, что (5d({c7o, <7ih 0) ⁼ {<?ь <?4}- Последнее равенство справедливо для всех цифр.

Итак, мы объяснили, как строятся дуги на рис. 2.22. Остальные переходы находятся аналогично; проверка предоставляется читателю. Поскольку q₅ есть единственное допус­кающее состояние Е, допускающими состояниями D являются те его достижимые со­стояния, которые содержат q₅. На рис. 2.22 эти два состояния, {q₃, g₅} и {q₂, q₃, q^}, от­мечены двойными кружками. □

Теорема 2.22. Язык L допускается некоторым е-НКА тогда и только тогда, когда L допускается некоторым ДКА.

Доказательство. (Достаточность) Доказательство в эту сторону просто. Допустим, L = L(D) для некоторого ДКА D. Преобразуем D в е-НКА Е, добавив переходы <5(q, е) = 0 для всех состояний q автомата D. Чисто технически нужно также преобразо­вать переходы D по входным символам к виду НКА-переходов. Например, So(q, а)= р нужно превратить в множество, содержащее только состояние р, т.е. &t(q, а) = {/>}. Та­ким образом, Е и D имеют одни и те же переходы, но при этом, совершенно очевидно, Е не содержит переходов по е, выходящих из какого-либо состояния.

(Необходимость) Пусть Е = (Q_E, 2, <Se, qе, Ее) — некоторый е-НКА. Применим опи­санную выше модифицированную конструкцию подмножеств для построения ДКА

D = (Q_d, 2, So, q_D, E_d). Нужно доказать, что L(D) = L(E). Для этого покажем, что расширенные функции пе­реходов Е и D совпадают. Формально покажем индукцией по длине w, что 8 _E(qo, w) = 8 d(<?O, w).

Базис. Если |w| = 0, то w = е. По определению замыкания 5 _E(q₀, е) = ECLOSE(g₀)- Кроме того, по определению начального состояния D q_D = ECLOSEWo). Наконец, нам известно, что для любого ДКА 8 (р, е) = р, каково бы ни было состояние р. Поэтому, в

л                                                                                                         л                    Л

частности, 8 _D(q_D, е) = ECLOSE(c/₀). Таким образом, доказано, что 8 _E(q₀, е) = 8 _D(q_D, £)■

Индукция. Предположим, что w = ха, где а— последний символ цепочки vv, и что

для х утверждение справедливо. Таким образом, 8 _E(qo, х) — 8 _D(c/_D, х). Пусть оба эти

множества состояний представляют собой {р\,р₂, •••, Рь}-

По определению 8 для е-НКА находим 8 _E(q₀, w) следующим образом. к

1. Пусть [J8 _E(pi, а) есть {г_ь г₂, …, г_т}.

j=i

А                     ^т

2. Тогда 8 _E(q₀, vv) = 1J ECLOSE(rj).

j=i

Внимательно рассмотрев, как ДКА D строится посредством описанной выше моди-

Л

фицированной конструкции подмножеств, мы видим, что 8 о({рь Рг,                о) построе­

но с помощью описанных только что шагов (1) и (2). Таким образом, значение

8 d(<7d, w), т.е. 8 _D({/?b Рг, ■■■,Рк}, а), совпадает с 8 _E(qo, w). Тем самым доказаны равен-

Л                                                                 Л

ство 8 е(йо, ^н‘) ⁼ ^ d(<?d, vv) и индуктивная часть теоремы. □

2.5.6. Упражнения к разделу 2.5 2.5.1. (*) Рассмотрите следующий £-НКА и:

	£	а	b	с
	0	\Р)	{<?}	И
я	{Р}	{<?}	{/»}	0
*г	{<?}		0	{р}

а)   найдите £-замыкание каждого из состояний;

б)   выпишите все цепочки, длина которых не более 3, допустимые данным ав­томатом;

в)   преобразуйте данный автомат в ДКА.

2.5.2. Выполните задание упражнения 2.5.1 со следующим £-НКА.

	£	а	Ъ	с
	{<?,/-}	0	{<?}	И
<7	0	[Р)	И	{p,q}
*г	0	0	0	0

2.5.3. Постройте £-НКА, которые допускают следующие языки. Для упрощения по­строений используйте, по возможности, £-переходы:

а)   множество всех цепочек, состоящих из нуля или нескольких символов а, по­сле которых стоит нуль или несколько символов Ь, и вслед за ними нуль или несколько символов с;

б)   (!) множество цепочек, состоящих либо из повторяющихся один или не­сколько раз фрагментов 01, либо из повторяющихся один или несколько раз фрагментов 010;

в)   (!) множество цепочек из 0 и 1, в которых хотя бы на одной из последних де­сяти позиций стоит 1.

Резюме

• Детерминированные конечные автоматы. ДКА имеет конечное число состояний и конечное множество входных символов. Одно из состояний выделено как на­чальное, и нуль или несколько состояний являются допускающими. Функция пе­реходов определяет, как изменяются состояния при обработке входных символов.
• Диаграммы переходов. Автомат удобно представлять в виде графа, в котором вершины соответствуют состояниям, а дуги, отмеченные входными символами,

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

• Язык автомата. Автомат допускает цепочки. Цепочка является допустимой, если, стартуя в начальном состоянии и обрабатывая символы этой цепочки по одному, автомат переходит в некоторое допускающее состояние. В терминах диаграмм переходов цепочка является допустимой, если она состоит из символов, отме­чающих путь из начального состояния в одно из допускающих.
• Недетерминированный конечный автомат. НКА отличается от ДКА тем, что НКА может иметь любое число переходов (в том числе, ни одного) из данного со­стояния в по данному входному символу.
• Конструкция подмножеств. Множества состояний НКА можно рассматривать как состояния некоторого ДКА. Таким образом, мы можем преобразовать НКА в ДКА, допускающий тот же самый язык.
• е-переходы. Можно расширить понятие НКА, разрешив переходы по пустой це­почке, т.е. вообще без входных символов. Расширенные таким образом НКА мо­гут быть преобразованы в ДКА, допускающие те же самые языки.
• Приложения типа «поиск в тексте». Недетерминированные конечные автоматы представляют собой удобный способ моделирования программы поиска одного или нескольких ключевых слов в больших массивах текста. Эти автоматы либо непосредственно имитируются с помощью программы, либо вначале преобразу­ются в ДКА, а затем уже реализуются в виде программы.

Литература

Принято считать, что начало формальному изучению систем с конечным числом со­стояний было положено в работе [2]. Однако эта работа была посвящена не теперешним ДКА, а так называемой вычислительной модели «нейронных сетей». ДКА, в общеприня­том смысле слова, были введены независимо в нескольких различных вариантах в рабо­тах [1], [3] и [4]. Материал по недетерминированным автоматам и конструкции подмно­жеств взят из работы [5].

1. A. Huffman, «The synthesis of sequential switching circuits», J.Franklin Inst. 257:3-4 (1954), pp. 161-190 and 275-303.
2. S. McCulloch and W. Pitts, «A logical calculus of the ideas immanent in nervuous ac­tivity», Bull. Math. Biophysics 5 (1943), pp. 115-133. (Маккалок У.С., Питтс Э. Логи­ческое исчисление идей, относящихся к нервной активности. / сб. «Автоматы». — М.: ИЛ, 1956. — С. 362-384.)
3. Н. Mealy, «A method for synthesizing sequential circuits», Bell System Technical Journal 34:5 (1955), pp. 1045-1079.
4. F.Moore, «Gedanken experiments on sequential machines», in [6], pp. 129-153. (Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. / сб. «Автоматы». — М.: ИЛ, 1956. — С. 179-210.)
5. М. О. Rabin and D. Scott, «Finite automata and their decision problems», IBM J. Research and Development 3:2 (1959), 115-125. (Рабин M.O., Скотт Д. Конечные автоматы и задачи их разрешения. — Кибернетический сборник, вып. 4. — М.: ИЛ, 1962. — С. 56-71.)
6. С. Е. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, (Шен­нон К.Э., Мак-Карти Дж. Теория автоматов. / сб. «Автоматы». — М.: ИЛ, 1956.)

^[1] Нужно помнить, что тут речь идет об одном денежном файле. На самом деле, банк будет ра­ботать по такому же протоколу с большим количеством единиц электронных денег. При этом вся­кий раз протокол работы с каждой такой единицей — один и тот же, поэтому мы можем рассмат­ривать данную проблему так, как если бы существовала всего одна единица электронных денег.

^[2] Точнее говоря, граф есть изображение некоторой функции переходов S, а дуги этого графа отображают переходы, определяемые функцией S.

^[3] Напомним, что мы условились обозначать символы буквами из начальной части алфавита, а цепочки— буквами из конца алфавита. Это соглашение необходимо для того, чтобы понять смысл выражения «цепочка видалга».

^[4] В русскоязычной литературе часто употребляется термин «принцип Дирихле». — Прим. ред. 82       ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ