ГЛАВА 4

Свойства регулярных языков

В этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков — теорема, которая называется «леммой о накачке» («pumping lemma»).

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

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

4.1. Доказательство нерегулярности языков

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

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

4.1.1. Лемма о накачке для регулярных языков

Рассмотрим язык L_n, = {0″Г | п > 1}. Этот язык состоит из всех цепочек вида 01, 0011, 000111 и так далее, содержащих один или несколько нулей, за которыми следует такое же количество единиц. Утверждается, что язык L₀, нерегулярен. Неформально, если бы L₍,i был регулярным языком, то допускался бы некоторым ДКА А, имеющим какое-то число состояний к. Предположим, что на вход автомата поступает к нулей. Он находится в некотором состоянии после чтения каждого из к + 1 префиксов входной цепочки, т.е. е,

1. 00, …, 0^к. Поскольку есть только к различных состояний, то согласно «принципу голу­бятни», прочитав два различных префикса, например, О¹ и О¹, автомат должен находится в одном и том же состоянии, скажем, q.

Допустим, что, прочитав / или j нулей, автомат А получает на вход 1. По прочтении / единиц он должен допустить вход, если ранее получил / нулей, и отвергнуть его, получив j нулей. Но в момент поступления 1 автомат А находится в состоянии q и не способен «вспомнить», какое число нулей, i или /, было принято. Следовательно, его можно «обманывать» и заставлять работать неправильно, т.е. допускать, когда он не должен этого делать, или наоборот.

Приведенное неформальное доказательство можно сделать точным. Однако к заклю­чению о нерегулярности языка L₀i приводит следующий общий результат.

Теорема 4.1 (лемма о накачке для регулярных языков). Пусть L — регулярный язык. Существует константа п (зависящая от L), для которой каждую цепочку w из языка L, удовлетворяющую неравенству \w\ > п, можно разбить на три цепочки w = xyz так, что выполняются следующие условия.

1. уф е.
2. \ху\ < п.
3. Для любого к > 0 цепочка xy^kz также принадлежит L.

Это значит, что всегда можно найти такую цепочку у недалеко от начала цепочки w, ко­торую можно «накачать». Таким образом, если цепочку у повторить любое число раз или удалить (при к = 0), то результирующая цепочка все равно будет принадлежать языку L.

Доказательство. Пусть L — регулярный язык. Тогда L = L(A) для некоторого ДКА А. Пусть А имеет п состояний. Рассмотрим произвольную цепочку w длиной не менее п, скажем, w = а,а₂…а_т, где т>п и каждый а, есть входной символ. Для /= 0, 1, 2, …,« определим состояние р, как 8 (с/,,. а/От…а,), где 8— функция переходов автомата А, а qo — его начальное состояние. Заметим, что р₀ = qo.

Рассмотрим п + 1 состояний p_t при i = О, 1,2, …, п. Поскольку автомат А имеет п раз­личных состояний, то по «принципу голубятни» найдутся два разных целых числа / и j (0<i<j< п), при которых р, = р_г Теперь разобьем цепочку w на xyz.

1. х = а^.-.а,.
2. у = a_l+ia,.₂—cij.
3. z = а_)Ча^₂—а_т—

Таким образом, х приводит в состояние р„ у — из р, обратно в р, (так как р, = pj), а z — это остаток цепочки w. Взаимосвязи между цепочками и состояниями показаны на рис. 4.1. Заметим, что цепочка х может быть пустой при / = 0, a z — при j = п = т. Однако цепочка у не может быть пустой, поскольку / строго меньше j.

У = а_!+, … о,

X =                                         ‘».                            2 =

Начало ^-ч      -Ч/^V          V —                /^S

-М^)…………………………………………………. *\J

Рис. 4.1. Каждая цепочка, длина которой больше числа состояний автомата, приводит к повторению некоторого состояния

Теперь посмотрим, что происходит, когда на вход автомата А поступает цепочка xy^kz для любого к > 0. При к = 0 автомат переходит из начального состояния q₀ (которое есть также р₀) в р„ прочитав х. Поскольку р, =p_Jt то z переводит А из р, в допускающее со­стояние (см. рис. 4.1).

Если к > 0, то по х автомат А переходит из q₀ в р„ затем, читая у\ к раз циклически про­ходит через р^ и, наконец, по z переходит в допускающее состояние. Таким образом, для любого к > 0 цепочка xy^kz также допускается автоматом А, т.е. принадлежит языку L. □

4.1.2. Применение леммы о накачке

Рассмотрим несколько примеров использования леммы о накачке. В каждом примере эта лемма применяется для доказательства нерегулярности некоторого предлагаемого языка.

Лемма о накачке как игра двух противников

В разделе 1.2.3 говорилось о том, что любую теорему, утверждение которой содержит несколько чередующихся кванторов «для всех» («для любого») и «существует», можно представить в виде игры двух противников. Лемма о накачке служит важным примером теорем такого типа, так как содержит четыре разных квантора: «для любого регулярно­го языка L существует п, при котором для всех w из L, удовлетворяющих неравенству Н > п, существует цепочка xyz, равная w, удовлетворяющая …». Применение леммы о накачке можно представить в виде игры со следующими правилами.

1. Игрок 1 выбирает язык L, нерегулярность которого нужно доказать.
2. Игрок 2 выбирает п, но не открывает его игроку 1; первый игрок должен постро­ить игру для всех возможных значений п.
3. Игрок 1 выбирает цепочку w, которая может зависеть от п, причем ее длина долж­на быть не меньше п.
4. Ифок 2 разбивает цепочку w на х, у и z, соблюдая условия леммы о накачке, т.е. у Ф г и \ху\ < п. Опять-таки, он не обязан говорить первому игроку, чему равны х, у и z, хотя они должны удовлетворять условиям леммы.
5. Первый игрок «выигрывает», если выбирает к, которое может быть функцией от п, х, у и z и для которого цепочка xy^kz не принадлежит L.

Пример 4.2. Покажем, что язык L_eq, состоящий из всех цепочек с одинаковым числом нулей и единиц (расположенных в произвольном порядке), нерегулярен. В терминах иг­ры, описанной во врезке «Лемма о накачке как игра двух противников», мы являемся иг­роком 1 и должны иметь дело с любыми допустимыми ходами игрока 2. Предположим, что п — это та константа, которая согласно лемме о накачке должна существовать, если язык L_eq регулярен, т.е. «игрок 2» выбирает п. Мы выбираем цепочку w = Oⁿr, которая наверняка принадлежит L_eq.

Теперь «игрок 2» разбивает цепочку w на xyz. Нам известно лишь, что у Ф е и \ху\ < п. Но эта информация очень полезна, и мы-«выигрываем» следующим образом. Поскольку \ху\ < п, и цепочка ху расположена в начале цепочки w, то она состоит только из нулей. Если язык L_eq регулярен, то по лемме о накачке цепочка хг принадлежит L_eq (при к = 0 в лемме)². Цепочка xz содержит п единиц, так как все единицы цепочки w попадают в z. Но в xz нулей меньше п, так как потеряны все нули из у. Поскольку у Ф е, то вместе х и z со­держат не более п — 1 нулей. Таким образом, предположив, что язык L_eq регулярен, при­ходим к ошибочному выводу, что цепочка xz принадлежит L_eq. Следовательно, методом от противного доказано, что язык L_eq нерегулярен. □

Пример 4.3. Докажем нерегулярность языка L_pr, образованного всеми цепочками из единиц, длины которых — простые числа. Предположим, что язык L_pr регулярен. Тогда должна существовать константа п, удовлетворяющая условиям леммы о накачке. Рас­смотрим некоторое простое число р>п + 2. Такое р должно существовать, поскольку множество простых чисел бесконечно. Пусть w = 1^р.

Согласно лемме о накачке можно разбить цепочку w = xyz так, что у Ф е и |ху| < п. Пусть [>.’) = т. Тогда |xz| = р- т. Рассмотрим цепочку ху? ^mz, которая по лемме о накачке должна принадлежать языку L_pr, если он действительно регулярен. Однако

|хУ^^тг| = |xz| + (р — т)\у\ = р-т + (р- т)т = (т + 1 )(р — т).

2 или любом другом значении к, кроме k = 1. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ

, Похоже, что число |х>’^{р т}г| не простое, так как имеет два множителя т + 1 и р-т. Од­нако нужно еще убедиться, что ни один из этих множителей не равен 1, потому что тогда яисло (т+ \)(р-т) будет простым. Из неравенства у фе следует т > 1 и т + 1 > 1. Кро­ме того, т = [у| < \ху\ < п, а р > п + 2, поэтому р-т >2.

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

4.1.3. Упражнения к разделу 4.1

• Докажите нерегулярность следующих языков:

а) {0^ПГ|«> 1}. Это язык L_0h который рассматривался в начале раздела. Ему принадлежат все цепочки, состоящие из нулей, за которыми следует такое же количество единиц. Здесь для доказательства примените лемму о накачке;

б)  множество цепочек, состоящих из «сбалансированных» скобок «(» и «)», ко­торые встречаются в правильно построенном арифметическом выражении;

в)   (*) {0^П10^П | л > 1};

г)   {0″l^m2ⁿ [пит — произвольные целые числа};

д)  {0″Г| п<т}\

е)   {0″1^2п|«>1}.

• (!) Докажите нерегулярность следующих языков:

а)  (*) {0″ | л? — полный квадрат};

б)  {0″ | « — полный куб};

в)   {0″ | п — степень числа 2};

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

д)  множество цепочек из нулей и единиц вида ww, где некоторая цепочка w по­вторяется дважды;

е)   множество цепочек из нулей и единиц вида mv^R, где за цепочкой следует це­почка, обратная к ней (формальное определение цепочки, обратной к данной, см. в разделе 4.2.2);

ж)  множество цепочек из нулей и единиц вида w w , где цепочка w образована из w путем замены всех нулей единицами и наоборот. Например, 011 = 100, так что цепочка 011100 принадлежит данному языку;

з)   множество цепочек из нулей и единиц вида w 1″, где w— цепочка из нулей и единиц длиной п.

• (!!) Докажите нерегулярность следующих языков:

а)  множество всех цепочек из нулей и единиц, которые начинаются с единицы и удовлетворяют следующему условию: если интерпретировать такую це­почку как целое число, то это число простое;^[2]

б)  множество цепочек вида 0’l^j, для которых наибольший общий делитель чи­сел / и j равен 1.

• (!) При попытке применения леммы о накачке к регулярным языкам «противник выигрывает», и закончить доказательство не удается. Определите, что именно происходит не так, как нужно, если в качестве L выбрать следующий язык:

а)  (*) пустое множество;

б)  (*) {00, 11};

в)   (*) (00 + 11)*;

г)   01*0*1.

4.2. Свойства замкнутости регулярных языков

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

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

1. Объединение.
2. Пересечение.
3. Дополнение.
4. Разность.
5. Обращение.

6. Итерация (звездочка).
7. Конкатенация.
8. Гомоморфизм (подстановка цепочек вместо символов языка).
9. Обратный гомоморфизм.

4.2.1. Замкнутость регулярных языков относительно булевых операций

Сначала рассмотрим замкнутость для трех булевых операций: объединение, пересе­чение и дополнение.

1. Пусть L и М— языки в алфавите Тогда язык L U М содержит все цепочки, кото­рые принадлежат хотя бы одному из языков L или М.
2. Пусть L и М— языки в алфавите Z. Тогда язык Lf] М содержит все цепочки, при­надлежащие обоим языкам L и М.
3. Пусть L — некоторый язык в алфавите Тогда язык L , дополнение L, — это мно­жество тех цепочек в алфавите Z*, которые не принадлежат L.

Что делать, если языки имеют разные алфавиты?

При объединении или пересечении двух языков LnM может оказаться, что они опре­делены в разных алфавитах. Например, возможен случай, когда L_t с {a, b}, a L₂Q {Ь, с, d}. Однако, если язык L состоит из цепочек символов алфавита то L можно также рассматривать как язык в любом конечном алфавите, включающем Z (надмножестве Z). Например, можно представить указанные выше языки L] и L₂ как языки в алфавите {а, Ь, с, d}. То, что ни одна цепочка языка L/ не содержит символов с или d, несущественно, как и то, что ни одна цепочка языка Ь₂ не содержит а. Аналогично, рассматривая дополнение языка L, который является подмножеством множества Z,* для некоторого алфавита Z_;, можно взять дополнение относительно некоторого алфавита включающего (надмножества ЕД В этом случае дополне­нием L будет Z/ — L, т.е. дополнение языка L относительно алфавита Z? включает (среди прочих) все цепочки из Z/, которые содержат хотя бы один символ алфавита 1₂, не принадлежащий Z,. Если взять дополнение L относительно Z,, то ни одна це­почка, содержащая символы из Z, — Z/, не попадет в L . Таким образом, чтобы избе­жать неточностей, нужно указывать алфавит, относительно которого берется допол­нение. Часто, однако, бывает очевидно, какой алфавит подразумевается в конкретном случае. Например, если язык L определен некоторым автоматом, то в описании этого автомата указывается и алфавит. Итак, во многих ситуациях можно говорить о «до­полнении», не указывая алфавит.

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

Замкнутость относительно объединения

Теорема 4.4. Если L и М— регулярные языки, то L U М также регулярен.

Доказательство. Поскольку языки L и М регулярны, им соответствуют некоторые регулярные выражения. Пусть L = L{R) и М = L(S). Тогда L U М = L(R + S) согласно оп­ределению операции + для регулярных выражений. □

Замкнутость относительно регулярных операций

Доказательство замкнутости регулярных выражений относительно объединения было исключительно легким, поскольку объединение является одной из трех операций, оп­ределяющих регулярные выражения. Идея доказательства теоремы 4.4 применима также к конкатенации и итерации. Таким образом,

• если L и М— регулярные языки, то язык LM регулярен;
• если L — регулярный язык, то L* также регулярен.

Замкнутость относительно дополнения

Теорема для объединения языков легко доказывается с помощью регулярных выра­жений. Теперь рассмотрим дополнение. Знаете ли вы, как преобразовать регулярное вы­ражение, чтобы оно определяло дополнение языка? Мы тоже не знаем. Однако это вы­полнимо, так как согласно теореме 4.5 можно_ч начать с ДКА и построить ДКА, допус­кающий дополнение. Таким образом, начав с регулярного выражения для языка, можно найти выражение для его дополнения следующим образом.

1. Преобразовать регулярное выражение в е-НКА.
2. Преобразовать е-НКА в ДКА с помощью конструкции подмножеств.
3. Дополнить допускающие состояния этого ДКА.
4. Преобразовать полученный ДКА для дополнения обратно в регулярное выражение, используя методы из разделов 3.2.1 или 3.2.2.

Теорема 4.5. Если L — регулярный язык в алфавите Z, то язык L = £* — L также ре­гулярен.

Доказательство. Пусть L = ЦА) для некоторого ДКА А = (Q, Е, <5, q₀, F). Тогда L = ЦВ), где В — это ДКА (Q, X, 5, q₀, Q — F), т.е. автоматы А и В одинаковы, за исключением то­го, что допускающие состояния автомата А стали не допускающими в В, и наоборот. То­гда w принадлежит ЦВ), если, и только если, <5 (q₀, vv) принадлежит Q — F, т.е. w не при­надлежит ЦА). □

Заметим, что для приведенного выше доказательства важно, чтобы 5 (q₀, w) всегда было некоторым состоянием. Это значит, что в автомате А все переходы определены. Если бы некоторые переходы отсутствовали, то определенные цепочки не вели бы ни в допускающее, ни в недопускающее состояния автомата А, т.е. отсутствовали бы как в L(A), так и ЦБ). К счастью, ДКА определен так, что в любом состоянии у него есть пере­ход по каждому символу алфавита 2, так что каждая цепочка приводит в состояние либо из F, либо из Q-F.

Пример 4.6. Пусть А— автомат, изображенный на рис. 2.14. Напомним, что этот ДКА допускает те и только те цепочки символов 0 и 1, которые заканчиваются на 01. В терминах регулярных выражений L(A) = (0 + 1)*01. Таким образом, дополнение к L(A) содержит все те цепочки из нулей и единиц, которые не заканчиваются на 01. На рис. 4.2 представлен автомат для {0, 1 }* -L(A). Он совпадает с автоматом на рис. 2.14, за исклю­чением того, что допускающие состояния стали недопускающими, а два недопускающих состояния стали допускающими. □

Пример 4.7. Используем теорему 4.5 для доказательства нерегулярности определен­ного языка. В примере 4.2 была доказана нерегулярность языка L_eq, состоящего из цепо­чек с равными количествами символов 0 и 1. Это доказательство было непосредствен­ным применением леммы о накачке. Теперь рассмотрим язык М, состоящий из цепочек с неравными количествами нулей и единиц.

1                            о

Рис. 4.2. ДКА, допускающий дополнение языка (0 + 1) 01

В данном случае для доказательства нерегулярности языка М лемму о накачке при­менить трудно. Интуиция подсказывает, что если начать с некоторой цепочки w из А/, разбить ее на w = xyz и «накачать» у, то может оказаться, что у — это цепочка вроде 01, в которой поровну символов 0 и 1. В этом случае не существует такого к, для которого це­почка ху z имела бы поровну нулей и единиц, поскольку xyz содержит неравные количе­ства нулей и единиц, а при «накачивании» у эти количества изменяются одинаково. Сле­довательно, мы не можем использовать лемму о накачке для того, чтобы прийти к про­тиворечию с предположением, что язык М регулярен.

Но все-таки язык М нерегулярен. Объясняется это тем, что М= L_eq. Поскольку до­полнение к дополнению некоторого множества равно этому же множеству, то L_eq = М .

Если М регулярен, то по теореме 4.5 язык Ь_щ также регулярен. Но мы знаем, что L_eq не регулярен, и полученное противоречие доказывает нерегулярность языка М. □

Замкнутость относительно пересечения

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

1пМ=1ил7                                                                        (4.1)

Вообще, пересечение двух множеств — это множество элементов, не принадлежащих дополнениям каждого из них. Это замечание, записанное в виде равенства (4.1), пред­ставляет один из законов Де Моргана. Другой закон имеет аналогичный вид, только объ­единение и пересечение меняются местами, т.e.LuM = L пМ .

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

Теорема 4.8. Если L и М— регулярные языки, то язык L П М также регулярен.

Доказательство. Пусть L и М— языки автоматов A_L = (Q_L, Z, 8_Ь q,. F,) и А_м = (Q_M, X, S_M, q_M, F_M). Заметим, что алфавиты автоматов считаются одинаковыми, т.е. X есть объединение алфавитов языков L и М, если эти алфавиты различаются. В действи­тельности конструкция произведения работает для НКА точно так же, как и для ДКА, но для максимального упрощения предположим, что A_L и А_м— ДКА.

Для L П М построим автомат А, моделирующий автоматы А, и А_м одновременно. Со­стояниями автомата А будут пары состояний, первое из которых принадлежит А, , а вто­рое — А_м. Чтобы построить переходы автомата А, предположим, что он находится в со­стоянии (р, q), где р— состояние автомата А,_, a q— состояние А_м— Нам известно, как ведет себя автомат А/,, получая на входе символ а. Пусть он переходит в состояние .у. Также допустим, что автомат А_м по входному символу а совершает переход в состояние t. Тогда следующим состоянием автомата А будет (.s, t). Таким образом, автомат А моде­лирует работу автоматов A_L и А_м. Эта идея в общих чертах представлена на рис. 4.3.

Остальные детали доказательства очень просты. Начальным состоянием автомата А будет пара начальных состояний автоматов A_L и А_м. Поскольку автомат А допускает то­гда и только тогда, когда допускают оба автомата А, и Ам, в качестве допускающих со­стояний автомата А выбираем все пары (р, q), где р — допускающее состояние автомата A_l, a q —А_м. Формально автомат А определяется как

А = {Qi X Q_M, Z, S, (q_L, q_M), (F, x F_M), где 8{{p, q), a) = (S_r(p, a), S_x1(q, a)).

А,»

Начало

Рис. 4.3. Автомат, имитирующий два других автомата и допускающий тогда и только тогда,

когда допускают оба автомата

Чтобы увидеть, почему L(A) = L(A_l) f| L(A_m), сначала заметим, что индукцией по \w\ легко доказать равенство S ((q_L, q^), w) = (5 /{q_L, w), 8 лХ^лл w)). Но А допускает w тогда и только тогда, когда <5 {{q_L, q_M), w) является парой допускающих состояний, т.е.

Л                                                                                                                                                                                                                         Л

8 _L(q_L, w) должно принадлежать F_L, a S м(Ям, w) — F_M. Иными словами, цепочка w до­пускается автоматом А тогда и только тогда, когда ее допускают оба автомата А/ и А_м. Итак, А допускает пересечение языков L и М. □

Пример 4.9. На рис. 4.4 представлены два ДКА. Автомат на рис. 4.4, а допускает все цепочки, имеющие 0, а автомат на рис. 4.4, б — все цепочки, имеющие 1. На рис. 4.4, в представлен автомат— произведение двух данных автоматов. Его состояния помечены как пары состояний исходных автоматов.

Легко доказать, что этот автомат допускает пересечение первых двух языков, т.е. те цепочки, которые содержат как 0, так и 1. Состояние рг представляет начальное условие, когда на вход автомата пока не поступили ни 0, ни 1. Состояние qr означает, что посту­пили только нули, а состояние ps — только единицы. Допускающее состояние qs пред­ставляет условие того, что на вход автомата поступили и нули, и единицы. □ Замкнутость относительно разности

Вход а

Существует еще одна, четвертая, операция, часто применяемая к множествам и свя­занная с булевыми операциями, а именно, разность множеств. В терминах языков разно­стью L-M языков L и М называют множество цепочек, которые принадлежат L и не принадлежат М. Регулярные языки замкнуты относительно этой операции. Доказатель­ство замкнутости относительно разности следует из доказанных выше теорем.

Начало

а)

0,1

О

Начало

0,1

Начало

0

0

О, 1

п

в)

Рис. 4.4. Конструкция произведения

Теорема 4.10. Если LnM— регулярные языки, то язык L — М также регулярен. Доказательство. Заметим, что L — М = Lf] Л/ . По теореме 4.5 регулярен язык М , а по теореме 4.8 — L f| М . Следовательно, язык L — Мрегулярен. □

4.2.2. Обращение

Обращением цепочки а/а_г…а„ называется цепочка, записанная в обратном порядке, т.е. a„a„-i…ai. Обращение w обозначается w^R. Таким образом, 00L0^R есть 0100, е.

Обращение языка L, обозначаемое Z,^R, состоит из всех цепочек, обратных цепочкам языка L. Например, если! ={001, 10, 111}, тоL^K= {100, 01, 111}.

Обращение является еще одной операцией, сохраняющей регулярность языков, т.е. если язык L регулярен, то L^R также регулярен. Это легко доказать двумя способами, пер­вый из которых основан на автоматах, а второй — на регулярных выражениях. Доказа­тельство, основанное на автоматах, приводится неформально, так что читатель при же­лании может восполнить детали. Затем приводится формальное доказательство, исполь­зующее регулярные выражения.

Если задан язык L, который есть L(A) для некоторого конечного автомата А, вероят­но, с недетерминизмом и £-переходами, то можно построить автомат для L^K следующим образом.

1. Обратить все дуги на диаграмме переходов автомата А.
2. Сделать начальное состояние автомата А единственным допускающим состоянием нового автомата.
3. Создать новое начальное состояние р₀ с £-переходами во все допускающие состоя­ния автомата А.

В результате получим автомат, имитирующий автомат А «в обратном порядке» и, следо­вательно, допускающий цепочку w тогда и только тогда, кода А допускает w^R. Теперь докажем теорему для обращения формально. Теорема 4.11. Если язык L регулярен, то язык L^R также регулярен. Доказательство. Предположим, что язык L определяется регулярным выражением Е. Доказательство проводится структурной индукцией по длине выражения Е. Покажем, что существует еще одно регулярное выражение Е^к, для которого L(E^R) = (ЦЕ))^К, т.е. язык выражения Е^к является обращением языка выражения Е.

Базис. Если Е равно £, 0 или а, где а — некоторый символ, то Е^к совпадает с Е, т.е.

{£}^R={£},0^R=0H{«}^R={«}.

Индукция. В зависимости от вида выражения Е возможны три варианта.

1. Е = Е/ + Е₂. Тогда E^R = £_;^R + E₂^R. Доказательство состоит в том, что обращение объ­единения двух языков получается, если сначала вычислить, а затем объединить об­ращения этих языков.
2. Е= Е]Е₂. Тогда £^R = E₂^RE,^R. Заметим, что необходимо обратить не только сами язы­ки, но и их порядок. Например, если L(E_t) = {01,111}, a ЦЕ₂) = {00,10}, то ЦЕ,Е₂)= {0100, 0110, 11100, 11110}. Обращение этого языка есть {0010, 0110, 00111,01111}.

Если соединить обращения языков ЦЕ₂) и ЦЕ,) в таком порядке, как они здесь запи­саны, то получим язык

{00, 01} {10, 111} = {0010, 00111,0110,01111}, который равен языку (L(E,E₂yf~. В общем случае, если цепочка w из ЦЕ) является конкатенацией цепочек w, из ЦЕ,) и w₂ из ЦЕ₂), то w^R = w₂^Rw_;^R.

3. Е = Е*. Тогда £^R = (£_;^R)*. Доказательство состоит в том, что любая цепочка w из L{E) может быть записана как w,w₂…w_m где каждая vv, принадлежит ЦЕ). Но

r _ r r r W =W„ W„_i …Wi .

Каждая w,^R принадлежит L(£^R), т.е. w^R принадлежит (£/^R)*. И наоборот, любая це­почка из Z((£_;^r)*) имеет вид w,w₂…w_m где каждая цепочка vv, является обращением некоторой цепочки из L(Ei). Следовательно, обращение данной цепочки w„^Rw„ A..w/^R принадлежит языку ЦЕ*), который равен ЦЕ). Таким образом, доказано, что цепочка принадлежит ЦЕ) тогда и только тогда, когда ее обращение принадле­жит Ц(Е,^К)*). □

Пример 4.12. Пусть язык L определяется регулярным выражением (0 + 1)0*. Тогда согласно правилу для конкатенации L^K— это язык выражения (0*)^R(0 + 1)^R. Если приме­нить правила для итерации и объединения к двум частям этого выражения, а потом ис­пользовать базисное правило, которое говорит, что обратными к 0 и 1 будут эти же вы­ражения, то получим, что язык L^K определяется регулярным выражением 0 (0 + 1). □

4.2.3. Гомоморфизмы

Гомоморфизм цепочек — это такая функция на множестве цепочек, которая подстав­ляет определенную цепочку вместо каждого символа данной цепочки.

Пример 4.13. Функция h, определенная как /;(0) = ab и h(l) = e, является гомомор­физмом. В любой цепочке из символов 0 и 1 h заменяет все нули цепочкой ab, а все еди­ницы — пустой цепочкой. Например, применяя h к цепочке 0011, получим abab. О

Формально, если h есть некоторый гомоморфизм на алфавите Z, a w = а\а₂…а„— це­почка символов в X, то h(w) = h(ai)h(a₂)…h(a_n). Таким образом, сначала h применяется к каждому символу цепочки w, а потом полученные цепочки символов соединяются в со­ответствующем порядке. Например, рассмотрим гомоморфизм h из примера 4.13 и це­почку w = 0011: h(w) = h(0)h(0)h(l)h(l) = (ab)(ab)(e)(e) = abab, что и утверждается в этом примере.

Гомоморфизм языка определяется с помощью его применения к каждой цепочке язы­ка, т.е. если L — язык в алфавите Z, a h — гомоморфизм на Z, то h(L) = {h(w) | w принад­лежит L}. Рассмотрим язык L регулярного выражения 10 1, т.е. все цепочки, которые на­чинаются и заканчиваются единицей, а между ними содержат произвольное число нулей. Пусть h — гомоморфизм из примера 4.13. Тогда h(L) — это язык выражения (ab)*. Объ­ясняется это тем, что h исключает все единицы, заменяя их е, а вместо каждого нуля под­ставляет цепочку ab. Идея применения гомоморфизма непосредственно к регулярному выражению используется для доказательства замкнутости регулярных языков относи­тельно гомоморфизма.

Теорема 4.14. Если L — регулярный язык в алфавите а /г — гомоморфизм на X, то язык /г(£) также регулярен.

Доказательство. Пусть L = Z(/?) для некоторого регулярного выражения Л. Вообще, если £ есть регулярное выражение с символами из алфавита Z, то пусть h(E) — выраже­ние, полученное в результате замены каждого символа я в выражении £ цепочкой й(я). Утверждается, что выражение /г(К) определяет язык /;(£).

Это легко доказать с помощью структурной индукции. Если применить гомоморфизм /г к любому подвыражению Е выражения Л, то язык выражения /г(£) совпадет с языком, полученным в результате применения этого гомоморфизма к языку L{E). Формально, ШЕ)) = Й(Ц£)).

Базис. Если Е есть £ или 0, то /г(£) совпадает с Е, поскольку Л не влияет на цепочку е или язык 0. Следовательно, L(h(E)) = L{E). В то же время, если Е равно 0 или е, то L(E) либо не содержит ни одной цепочки, либо состоит из цепочки без символов. Таким обра­зом, в обоих случаях h(L(E)) = L(£). Из этого следует, что L(h(E)) = L(E) = h(L(E)).

Возможен еще один базисный вариант, когда Е= а для некоторого символа а из 2. В этом случае L{E) = {а}, и И(ЦЕ)) = {/г(а)}. Выражение /г(£) представляет собой цепочку символов h(a). Таким образом, язык L(h(E)) также совпадает с {h(a)}, и, следовательно,

ЩЕ)) = №Е))-

Индукция. В зависимости от операции в регулярном выражении возможны три си­туации. Все они просты, поэтому обоснуем индукцию только для объединения, Е = F + G. Способ применения гомоморфизмов к регулярным выражениям гарантирует, что h(E) = h(F + G) = h(F) + h(G). Нам также известно, что L(E) = L(F) U L(G) и

L(h(E)) = L(h(F) + h(G)) = l(h(Fj) U L(h(G j)                                                    (4.2)

по определению операции + для регулярных выражений. Наконец,

h(L(E)) = h(L{F) U L(G)) = h{L(Fj) U h(L(G)),                                                (4.3)

поскольку h применяется к языку путем применения его к каждой цепочке этого языка по отдельности. По индуктивной гипотезе L(h(F)) = h(L(F)) и L(h(G)) = h(L(G)). Таким образом, правые части выражений (4.2) и (4.3) эквивалентны, и, следовательно, L{h{E)) = h{L{E)).

Для случаев, когда выражение Е является конкатенацией или итерацией, доказатель­ства не приводятся, поскольку они аналогичны доказательству, представленному выше. Итак, можно сделать вывод, что L(h(R)) действительно равняется h(L(R)), т.е. примене­ние гомоморфизма к регулярному выражению языка L дает регулярное выражение, оп­ределяющее язык h(L). □

4.2.4. Обратный гомоморфизм

Гомоморфизм можно применять «назад», и это также сохраняет регулярность языков. Предположим, что h—- гомоморфизм из алфавита £ в цепочки, заданные в другом (возможно, том же) алфавите Т^[3]. Пусть L — язык в алфавите Т. Тогда h~^l(L), читаемое как »обратное h от L», — это множество цепочек w из для которых h(w) принадлежит L. На рис. 4.5, а представлено применение гомоморфизма к языку L, а на рис. 4.5, б — ис­пользование обратного гомоморфизма.

Пример 4.15. Пусть L — язык регулярного выражения (00 + 1) , т.е. все цепочки из символов 0 и 1, в которых нули встречаются парами. Таким образом, цепочки 0010011 и 10000111 принадлежат L, а 000 и 10100 — нет.

Пусть h— такой гомоморфизм: h(a) = 01, h(b) = 10. Утверждается, что h~\L)— это язык регулярного выражения (Ьа)*, т.е. все цепочки, в которых повторяются пары Ьа. До­кажем, что h(w) принадлежитL тогда и только тогда, когда цепочка w имеет вид baba…Ьа.

Достаточность. Предположим, что цепочка w состоит из п повторений Ьа для неко­торого п > 0. Заметим, что h{ba) = 1001, т.е. h(w) — это п повторений цепочки 1001. По­скольку цепочка 1001 построена из двух единиц и пары нулей, то она принадлежит языку L. Следовательно, цепочка, состоящая из любого числа повторений 1001, также образо­вана единицами и парами нулей и принадлежит L. Таким образом, h(w) принадлежит L.

Необходимость. Теперь предположим, что h(yv) принадлежит L, и покажем, что це­почка w имеет вид baba…ba. Существует четыре условия, при которых цепочка имеет другой вид. Покажем, что при выполнении любого из них h(w) не принадлежит L, т.е. до­кажем утверждение, противоположное тому, что нам нужно доказать.

1. Если w начинается символом а, то h(w) начинается с 01. Следовательно, она содер­жит отдельный 0 и поэтому не принадлежит L.
2. Если w заканчивается символом Ь, то в конце h(w) стоит 10, и опять-таки в цепочке h(w) есть изолированный 0.
3. Если в цепочке w дважды подряд встречается а, то h(w) содержит подцепочку 0101. Снова в w есть изолированный нуль.
4. Аналогично, если в w есть два символа b подряд, то h(w) содержит подцепочку 1010 с изолированным 0.

Таким образом, при выполнении хотя бы одного из вышеперечисленных условий цепоч­ка h(w) не принадлежит L. Но если ни одно из условий 1-4 не выполняется, то цепочка w имеет вид baba…ba. Чтобы понять, почему это происходит, предположим, что ни одно из этих условий не выполняется. Тогда невыполнение условия 1 означает, что w должна начинаться символом Ь, а невыполнение 2 — что она должна заканчиваться символом а. Невыполнение условий 3 и 4 говорит, что символы а и b должны чередоваться. Следова­тельно, логическое ИЛИ условий 1-4 эквивалентно утверждению «цепочка w имеет вид, отличный от baba…bcC\ Но выше было доказано, что из логического ИЛИ условий 1-4 следует, что h(w) не принадлежит L. Это утверждение противоположно тому, что нужно доказать, а именно, что «если h(w) принадлежит L, то цепочка w имеет вид babu…ba\ □

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

Теорема 4.16. Если h— гомоморфизм из алфавита X в алфавит Т, L— регулярный язык над Т, то язык h~^l(L) также регулярен.

Доказательство. Начнем с ДКА А для языка L. По А и h строится ДКА для h’^l(L) с помощью схемы, представленной на рис. 4.6. Этот ДКА использует состояния автомата А, но переводит входной символ в соответствии с h перед тем, как решить, в какое со­стояние перейти.

Вход о Рис. 4.6. ДКА для h ‘(L) применяет гомоморфизм h ко входным символам, а потом имитирует ДКА для L

Формально, пусть L — это ЦА), где ДКА А = (Q, Т, 8, q₀, F). Определим ДКА

л

функция переходов /которого строится по правилу y(q, а)= 8 (q, h(a)). Таким образом, переход автомата В по входному символу а является результатом последовательности переходов, совершаемых автоматом А при получении цепочки символов h{a). Напомним, что, хотя h(a) может равняться е, состоять из одного или нескольких символов, функция <5 определена так, чтобы справиться со всеми этими случаями.

С помощью индукции по |vv| легко показать, что у (q„, vv) = 8(q₀,h(w)). Поскольку допускающие состояния автоматов А и В совпадают, то В допускает цепочку w тогда и только тогда, когда А допускает цепочку h{w). Иными словами, В допускает только те цепочки, которые принадлежат языку h’^l(L). □

Пример 4.17. В этом примере обратный гомоморфизм и некоторые другие свойства замкнутости регулярных множеств используются для доказательства одного необычного свойства конечных автоматов. Предположим, что, допуская входную цепочку, некоторый автомат должен побывать в каждом состоянии хотя бы по одному разу. Точнее, допустим, что А = (Q, Z, 8, q₀, F) — ДКА, и нас интересует язык L, состоящий из всех цепочек w в ал­фавите Z*, для которых 8 (q,_h vv) принадлежит F, и для каждого состояния q из Q существу­ет некоторый префикс х_ч цепочки vv, для которого 8 (q₀, х_ч) = q. Будет ли язык L регуляр­ным? Докажем, что такой язык регулярен, хотя доказательство довольно сложное.

Начнем с языка M-L(A), т.е. множества цепочек, допускаемых автоматом А обычным путем, независимо от того, в какие состояния он переходит, обрабатывая входную цепочку. Заметим, что LqM, так как определение языка L накладывает дополнительные ограниче­ния на цепочки из ЦА). Доказательство регулярности языка L начинается с использования обратного гомоморфизма для вставки состояний автомата А во входные символы. Точнее, определим новый алфавит Т как состоящий из символов, которые можно представить в ви­де троек \paq], где pwq — состояния из Q, а — символ из Z, и 8(р, а) = q.

Таким образом, символы алфавита Г представляют переходы автомата А. Важно по­нимать, что запись [paq] представляет собой единый символ, а не конкатенацию трех символов. Можно обозначить этот символ одной буквой, но при этом трудно описать его связь cp,qna.

Теперь определим гомоморфизм h([paq]) = а для всех р, а и q. Это значит, что гомо­морфизм h удаляет из каждого символа алфавита Т компоненты, представляющие со­стояния, и оставляет только символ из Z. Первый шаг доказательства регулярности языка L состоит в построении языка L, = h~^l(M). Поскольку язык М регулярен, то согласно тео­реме 4.16 язык Li также регулярен. Цепочками языка Li будут цепочки из М, к каждому символу которых присоединяется пара состояний, представляющая некоторый переход автомата.

В качестве простого примера рассмотрим автомат с двумя состояниями, представ­ленный на рис. 4.4, а. Алфавит Х= {0, 1}, а алфавит Т состоит из четырех символов [pQq], [q$q], [pip] и [q\q]. Например, поскольку по символу 0 есть переход из р в q, то \pOq] — один из символов алфавита Т. Так как цепочка 101 допускается этим автоматом, применив к ней обратный гомоморфизм /Г¹, получим 2³ = 8 цепочек, две из которых, на­пример, равны [p\p]\pQq][q\q] и [q\q][q0q]\p\p].

Теперь по языку построим язык L с помощью ряда операций, сохраняющих регу­лярность языков. Наша первая цель — исключить все те цепочки языка L_h в которых со­стояния указаны неправильно. Поскольку каждый символ вида \paq\ означает, что авто­мат был в состоянии р, прочитал а и затем перешел в состояние q, последовательность таких символов, представляющая допускающее вычисление в автомате А, должна удов­летворять следующим трем условиям.

1. Первым состоянием в первом символе должно быть q₀ — начальное состояние А.
2. Каждый переход автомата должен начинаться там, где закончился предыдущий, т.е. пер­вое состояние в символе должно равняться второму состоянию в предыдущем символе.
3. Второе состояние в последнем символе должно принадлежать F. Если выполняются первые два условия, то и это условие будет выполнено, поскольку каждая цепочка языка L, образована из цепочки, допускаемой автоматом А.

и		Язык автомата А
		Обратный гомоморфизм
L	1	Цепочки языка М, в которые вставлены компоненты состояний
i	‘	Пересечение с регулярным языком
L	2	Добавить условие, что первым является начальное состояние
	‘	Разница с регулярным языком
1	3	Добавить условие, что смежные состояния должны совпадать
		Разница с регулярными языками
	‘4	Добавить условие, что на пути встречаются все состояния
		Гомоморфизм
L		Удалить компоненты состояний, оставляя только символы

Рис. 4.7. Построение языка L по языку М с помощью операций, сохраняющих регулярность языков

План построения языка L представлен на рис. 4.7.

Условие 1 обеспечивается пересечением языка Li со множеством цепочек, которые на­чинаются символом вида [qoaq] для некоторого символа а и состояния q. Пусть Ei — вы­ражение [qnQ^h] + [qoOiCji] + …, где a,q, — все пары из X X Q, для которых S(q_fl, а,) = q,. Пусть L₂ = L] П L{E_;T). Регулярное выражение Е,Т обозначает все цепочки из Т*, которые начинаются стартовым состоянием (здесь Т можно рассматривать как сумму всех его сим­волов). Поэтому язык /,₂ состоит из всех цепочек, полученных в результате применения об­ратного гомоморфизма /Г¹ к языку М, у которых первым компонентом в первом символе является начальное состояние, т.е. язык L₂ удовлетворяет условию 1.

Чтобы обеспечить выполнение условия 2, проще всего вычесть из L₂ (используя опе­рацию разности множеств) все цепочки, нарушающие это условие. Пусть Е₂ — регуляр­ное выражение, состоящее из суммы (объединения) конкатенации всех пар символов, ко­торые друг другу не подходят. Это все пары вида \paq\[rbs\, где q Ф г. Тогда регулярное выражение Т*Е₂Т* обозначает все цепочки, не удовлетворяющие условию 2.

Теперь можно определить h₃ = L₂— L(fE₂f). Цепочки языка L₃ удовлетворяют усло­вию 1, поскольку цепочки языка L₂ начинаются стартовым состоянием. Они также удов­летворяют условию 2, так как в результате вычитания ЦТ* Е₂Т*) будут удалены все це­почки, для которых это условие не выполняется. Наконец, они удовлетворяют условию 3 (последнее состояние является допускающим), поскольку доказательство было начато с цепочек языка М, допускаемых автоматом А. В результате L_} состоит из цепочек языка М с состояниями допускающего вычисления такой цепочки, вставленными в каждый сим­вол. Заметим, что язык L₃ регулярен, так как он построен из регулярного языка М с по­мощью операций обратного гомоморфизма, пересечения и разности множеств, сохра­няющих регулярность.

Напомним, что наша цель состоит в том, чтобы допустить только те цепочки из М, при обработке которых автомат проходит через каждое состояние. Выполнение этого ус­ловия можно обеспечить с помощью операции разности множеств. Пусть для каждого состояния q регулярное выражение Е_ц представляет собой сумму всех символов алфавита Г, в которые не входит состояние q (q не стоит ни на первой, ни на последней позиции). В результате вычитания языка L(E_q*) из L₃ получим цепочки, представляющие допус­кающее вычисление автомата А и проходящие через состояние q, по крайней мере, один раз. Если вычесть из L₃ языки L{E_q) для всех q из Q, то получим допускающие вычисле­ния автомата А, проходящие через все состояния. Обозначим этот язык L₄. По теоре­ме 4.10 язык L₄ также регулярен.

Последний шаг состоит в построении языка L из Ь₄ с помощью исключения компо­нентов состояний, т.е. L = h(L₄). Теперь L является множеством цепочек в алфавите X*, допускаемых автоматом А, причем при их обработке автомат проходит через каждое со­стояние, по крайней мере, один раз. Поскольку регулярные языки замкнуты относитель­но гомоморфизмов, делаем вывод, что язык L регулярен. □

4.2.5. Упражнения к разделу 4.2

• Пусть h— гомоморфизм из алфавита {0, 1, 2} в алфавит {а, Ь}, определенный как k(0) = a, h(l) = ab и h(2) = ba\

а)   (*) найдите h(0120);

б)   найдите h(2\ 120);

в)   (*) найдите h(L) для/, = 1(01*2);

г)   найдите h(L) для Z, = Z,(0 + 12);

д)   (*) найдите h~\L) для L= {ababa}, т.е. языка, состоящего из одной- единственной цепочки ababa;

е)   (!) найдите /Г (L) для

• (*!) Если L — язык, а— символ, то L/a, частное L и а, — это множество цепочек

w, для которых wa принадлежит L. Например, если L = {a, aab, baa}, то Ыа = {е, Ьа}. Докажите, что из регулярности L следует регулярность L!a. Указание. Начните с ДКА для L и рассмотрите множество допускающих состояний.

• (!) Если L — язык, а — символ, то a\L — это множество цепочек w, для которых

aw принадлежит L. Например, если L = {a, aab, Ъаа}, то d\L = {е, ab}. Докажите, что из регулярности L следует регулярность d\L. Указание. Вспомните, что регу­лярные языки замкнуты относительно обращения и операции деления из упраж­нения 4.2.2.

• (!) Какие из следующих тождеств истинны?

а)   (Ua)a = L (в левой части представлена конкатенация языков L/a и {а}).

б)   a(a\L) = L (снова представлена конкатенация с языком {а}, но на этот раз слева).

в)   (La)/a = L.

г)   a\(aL) = L.

• Операция из упражнения 4.2.3 иногда рассматривается как «производная», а выра-

^ ^dL ^

жение a\L записывается как —. Эти производные применяются к регулярным

da

выражениям аналогично тому, как обычные производные применяются к ариф­метическим выражениям. Таким образом, если R — регулярное выражение, то

— обозначает то же, что и —, если L = L(R): da     da

d(R + S) dR dS

а)   докажите, что———— = — + — ;

da da da

б)   (*!) напишите правило для «производной» от RS. Указание. Нужно рассмот­реть два случая: язык L(R) включает или не включает цепочку е. Это правило не совпадает с «правилом произведения» для обычных производных, но по­хоже на него;

d( R*}

в)   (!) найдите «производную» от итерации, т.е. ——— ;

da

г)   используя формулы (а)-(в), найдите производную регулярного выражения (0 + 1)*011;

д)   (*) опишите такие языки L, для которых — = 0 ;

d0

е)   (*!) опишите такие языки L, для которых = L.

• (!) Докажите замкнутость регулярных языков относительно следующих операций:

а)   min(L) = {w\w принадлежит L, но ни один собственный префикс цепочки w не принадлежит L};

б)   max(L) = {w | w принадлежит L, но для любого хФ е цепочка wx не принад­лежит /,};

в)   init(L) = {w | для некоторого х цепочка wx принадлежит /.}.

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

• (!) Если w = а,а₂…а_п и х = Ъ₁Ъ₂…Ь„ — цепочки одинаковой длины, то определим alt(w, х) как цепочку, в которой символы цепочек w и х чередуются, начиная с w, т.е. a,b,a₂b..a_nb„. Если L и М— языки, определим alt{L, М) как множество це­почек вида alt{w, х), где w — произвольная цепочка из L, ах — любая цепочка из М такой же длины. Докажите, что из регулярности языков L и М следует ре­гулярность языка alt(L, М).
• (*!!) Пусть L — язык. Определим halJ{L) как множество первых половин цепочек языка L, т.е. множество {w | существует х, для которой wx принадлежит L, причем |х| = Н}. Например, если L = {е, 0010, 011, 010110}, то halJ{L) = {е, 00, 010}. Заме­тим, что цепочки с нечетной длиной не влияют на halJ[L). Докажите, что если язык L регулярен, то halj{L) также регулярен.
• (!!) Упражнение 4.2.8 можно распространить на многие функции, определяющие длину части цепочки. Если / — функция, определенная на множестве целых чи­сел, то обозначим через J{L) множество цепочек {w | существует цепочка х, для которой |х| =.АМ) ^{и wx} принадлежит L). Например, операция half соответствует тождественной функции Дя) = п, так как для цепочек из языка half(L) выполня­ется |х| = |w|. Покажите, что если язык L регулярен, то язык^/(!) также регулярен,

‘ где/— одна из следующих функций:

1. a) fin) = 2я (т.е. используются первые трети цепочек);

б)  Л^п)⁼ и² (длина выбираемой части цепочки равна квадратному корню длины оставшейся части цепочки);

^в)   Л’¹)⁼ 2″ (длина выбираемой части цепочки равна логарифму длины ее остатка).

• (!!) Пусть L— язык, не обязательно регулярный, в алфавите {0}, т.е. цепочки языка L состоят из одних нулей. Докажите, что язык L* регулярен. Указание. На первый взгляд эта теорема кажется абсурдной. Чтобы проиллюстрировать ис­тинность утверждения теоремы, приведем один небольшой пример. Рассмотрим язык L = {0′ | i— простое число}, который, как известно, нерегулярен (см. при­мер 4.3). Нетрудно доказать, что если j > 2, то 0* принадлежит С. Поскольку числа 2 и 3 — простые, цепочки 00 и 000 принадлежат L. Если j — четное число, то О¹ можно получить, повторив j!2 раз цепочку 00, а если j — нечетное, можно взять одну цепочку 000 и (j — 3)/2 цепочек 00. Следовательно, L = е + 000*.
• (!!) Докажите замкнутость регулярных языков относительно следующей опера­ции: cycle(L) = {w | цепочку w можно представить в виде w = ху, где ух принад­лежит L}. Например, если L = {01,011}, то cycle(L) = {01, 10, 011, 110, 101}. Указание. Начните с ДКА для языка L и постройте е-НКА для cycle(L).
• (!!) Пусть w, = a₀a₀a_h a w_t = для всех ;> 0. Например, w₃ = а₀а₀аia_ga_gaia₂a₀a₀a,а₀а_даia₂a₃. Кратчайшим регулярным выражением для языка L_n ⁼ {w„}, т.е. языка, состоящего из цепочки w„, будет сама w„, причем длина этого выражения равна 2ⁿ⁺¹ — 1. Однако, если применить операцию пересечения, то для языка L„ можно записать выражение длиной 0(п²). Найдите такое выра­жение. Указание. Найдите п языков с регулярными выражениями длины О(п), пересечение которых равно L„.
• Свойства замкнутости можно использовать для доказательства нерегулярности некоторых языков. Докажите, что язык

L_0n,„={(f\^tt\n>0}

нерегулярен. Докажите нерегулярность следующих языков, преобразовав их с помощью операций, сохраняющих регулярность, в язык L₀„i„\

а)   (*) {О’О¹1 /*/’};

б)   {0ⁿl^m2″»^m | и > m > 0}.

• В теореме 4.8 представлена «конструкция произведения», в которой по двум дан­ным ДКА построен ДКА, допускающий пересечение языков данных автоматов:

а)   покажите, как построить конструкцию произведения для НКА (без е-переходов);

б)   (!) продемонстрируйте, как построить конструкцию произведения для е-НКА;

в)   (*) покажите, как изменить конструкцию для произведения так, чтобы ре­зультирующий ДКА допускал разность языков двух данных ДКА;

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

• В доказательстве теоремы 4.8 утверждалось, что с помощью индукции по длине цепочки w можно доказать следующее равенство:

<5 ((<7/., Ям), w) = (<5 ,(q_L, w), 8 w)). Приведите это доказательство.

• Завершите доказательство теоремы 4.14, рассмотрев случаи, когда выражение Е яв­ляется конкатенацией двух подвыражений или итерацией некоторого выражения.
• В теореме 4.16 пропущено доказательство индукцией по длине цепочки w того, что у (q,_h w)= 8 (q,_h h(w)). Восполните этот пробел.

4.3. Свойства разрешимости регулярных языков

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

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

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

1. Является ли описываемый язык пустым множеством?
2. Принадлежит ли некоторая цепочка w представленному языку?
3. Действительно ли два разных описания представляют один и тот же язык? (Этот во­прос часто называют «эквивалентностью» языков.)

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

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

Преобразование НКА в ДКА

Время выполнения преобразования НКА или е-НКА в ДКА может быть экспоненци­альной функцией от количества состояний НКА. Начнем с того, что вычисление е- замыкания п состояний занимает время 0(п³). Необходимо найти все дуги с меткой е, ве­дущие от каждого из п состояний. Если есть п состояний, то может быть не более и² дуг. Разумное использование системных ресурсов и хорошо спроектированные структуры данных гарантируют, что время исследования каждого состояния не превысит 0{п²). В действительности для однократного вычисления всего е-замыкания можно использовать такой алгоритм транзитивного замыкания, как алгоритм Уоршалла (Warshall)^[4].

После вычисления е-замыкания можно перейти к синтезу ДКА с помощью конструк­ции подмножеств. Основное влияние на расход времени оказывает количество состояний ДКА, которое может равняться 2″. Для каждого состояния можно вычислить переходы за время (){п ), используя е-замыкание и таблицу переходов НКА для каждого входного символа. Предположим, нужно вычислить 5{{q_h q₂, …, q^}, а) для ДКА. Из каждого со­стояния <7, можно достичь не более п состояний вдоль путей с меткой е, и каждое из этих состояний может иметь не более, чем п дуг с меткой а. Создав массив, проиндексиро­ванный состояниями, можно вычислить объединение не более п множеств, состоящих из не более, чем п состояний, за время, пропорциональное и².

Таким способом для каждого состояния q, можно вычислить множество состояний, достижимых из q, вдоль пути с меткой а (возможно, включая дуги, отмеченные е). По­скольку к < п, то существует не более п таких состояний q„ и для каждого из них вычис­ление достижимых состояний занимает время 0(п²). Таким образом, общее время вы­числения достижимых состояний равно 0{п^ъ). Для объединения множеств достижимых состояний потребуется только 0(п²) дополнительного времени, следовательно, вычисле­ние одного перехода ДКА занимает время 0(п).

Заметим, что количество входных символов считается постоянным и не зависит от п. Таким образом, как в этой, так и в других оценках времени работы количество входных символов не рассматривается. Размер входного алфавита влияет только на постоянный коэффициент, скрытый в обозначении «О большого».

Итак, время преобразования НКА в ДКА, включая ситуацию, когда НКА содержит е- переходы, равно 0(п³2″). Конечно, на практике обычно число состояний, которые стро­ятся, намного меньше 2^П. Иногда их всего лишь п. Поэтому можно установить оценку времени работы равной 0(n³s), где .v — это число состояний, которые в действительности есть у ДКА.

Преобразование ДКА в НКА

Это простое преобразование, занимающее время 0(п) для ДКА с п состояниями. Все, что необходимо сделать, — изменить таблицу переходов для ДКА, заключив в скобки {} состояния, а также добавить столбец для е, если нужно получить е-НКА. Поскольку чис­ло входных символов (т.е. ширина таблицы переходов) считается постоянным, копиро­вание и обработка таблицы занимает время О(п).

Преобразование автомата в регулярное выражение

Рассмотрев конструкцию из раздела 3.2.1, заметим, что на каждом из п этапов (где п — число состояний ДКА) размер конструируемого регулярного выражения может уве­личиться в четыре раза, так как каждое выражение строится из четырех выражений пре­дыдущего цикла. Таким образом, простая запись и³ выражений может занять время 0(п³4″). Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент, но не влияет на экспоненциальность этой задачи (в наихудшем случае).

Аналогичная конструкция требует такого же времени работы, если преобразуется НКА, или даже е-НКА, но это здесь не доказывается. Однако использование конструкции для НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем ДКА — в регулярное выражение, то на это потребуется время 0(п³4″³²«), которое являет­ся дважды экспоненциальным.

Преобразование регулярного выражения в автомат

Для преобразования регулярного выражения в е-НКА потребуется линейное время. Необходимо эффективно проанализировать регулярное выражение, используя метод, за­нимающий время 0(п) для регулярного выражения длины и^[5]. В результате получим де­рево с одним узлом для каждого символа регулярного выражения (хотя скобки в этом дереве не встречаются, поскольку они только управляют разбором выражения).

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

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

4.3.2. Проверка пустоты регулярных языков

На первый взгляд ответ на вопрос «является ли регулярный язык L пустым?» кажется очевидным: язык 0 пуст, а все остальные регулярные языки — нет. Однако, как говори­лось в начале раздела 4.3, при постановке задачи явный перечень цепочек языка L не приводится. Обычно задается некоторое представление языка L, и нужно решить, обо­значает ли оно язык 0, или нет.

Если язык задан с помощью конечного автомата любого вида, то вопрос пустоты со­стоит в том, есть ли какие-нибудь пути из начального состояния в допускающие. Если есть, то язык непуст, а если все допускающие состояния изолированы от начального, то язык пуст. Ответ на вопрос, можно ли перейти в допускающее состояние из начального, является простым примером достижимости в графах, подобным вычислению е- замыкания, рассмотренному в разделе 2.5.3. Искомый алгоритм можно сформулировать следующим рекурсивным образом.

Базис. Начальное состояние всегда достижимо из начального состояния.

Индукция. Если состояние q достижимо из начального, и есть дуга из q в состояние р с любой меткой (входным символом или е, если рассматривается е-НКА), то р также достижимо.

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

Если язык L представлен регулярным выражением, а не автоматом, то можно преоб­разовать это выражение в е-НКА, а далее продолжить так, как описано выше. Поскольку автомат, полученный в результате преобразования регулярного выражения длины п, со­держит не более 0{п) состояний и переходов, для выполнения алгоритма потребуется время 0(п).

Можно проверить само выражение — пустое оно, или нет. Сначала заметим, что если в данном выражении ни разу не встречается 0, то его язык гарантированно не пуст. Если же в выражении встречается 0, то язык такого выражения не обязательно пустой. Ис­пользуя следующие рекурсивные правила, можно определить, представляет ли заданное регулярное выражение пустой язык.

Базис. 0 обозначает пустой язык, но е и а для любого входного символа а обознача­ют не пустой язык.

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

1. R = R_t + R₂. L(R) пуст тогда и только тогда, когда оба языка L(Rf) и L(R₂) пусты.
2. R = RiR₂. L{R) пуст тогда и только тогда, когда хотя бы один из языков L{Ri) и L{R₂) пуст.
3. R = R, . L(R) не пуст: он содержит цепочку е.
4. R = (R/). ЦЯ) пуст тогда и только тогда, кода L(R,) пуст, так как эти языки равны.

4.3.3. Проверка принадлежности регулярному языку

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

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

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

Если длина цепочки w равна п, а количество состояний НКА равно s, то время работы этого алгоритма равно 0(ns²). Чтобы обработать очередной входной символ, необходимо взять предыдущее множество состояний, число которых не больше s, и для каждого из них найти следующее состояние. Затем объединяем не более s множеств, состоящих из не более, чем s состояний, для чего нужно время 0{s²).

Если заданный НКА содержит е-переходы, то перед тем, как начать имитацию, необ­ходимо вычислить е-замыкание. Такая обработка очередного входного символа а состо­ит из двух стадий, каждая из которых занимает время 0(s²). Сначала для предыдущего множества состояний находим последующие состояния при входе а. Далее вычисляем е- замыкание полученного множества состояний. Начальным множеством состояний для такого моделирования будет е-замыкание начального состояния НКА.

И наконец, если язык L представлен регулярным выражением, длина которого s, то за время 0(s) можно преобразовать это выражение в е-НКА с числом состояний не больше 2s. Выполняем описанную выше имитацию, что требует 0(ns²) времени для входной це­почки w длиной п.

4.3.4. Упражнения к разделу 4.3

• (*) Приведите алгоритм определения, является ли регулярный язык L бесконеч­ным. Указание. Используйте лемму о накачке для доказательства того, что если язык содержит какую-нибудь цепочку, длина которой превышает определенную нижнюю границу, то этот язык должен быть бесконечным.
• Приведите алгоритм определения, содержит ли регулярный язык L по меньшей мере 100 цепочек.
• Пусть L — регулярный язык в алфавите Z. Приведите алгоритм проверки равен­ства L = Z*, т.е. содержит ли язык L все цепочки в алфавите Z.
• Приведите алгоритм определения, содержат ли регулярные языки /./ и L₂ хотя бы одну общую цепочку.
• Пусть L_t и L₂ — два регулярных языка с одним и тем же алфавитом Z. Приведи­те алгоритм определения, существует ли цепочка из X*, которая не принадлежит ни I/, ни L₂.

4.4. Эквивалентность и минимизация автоматов

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

4.4.1. Проверка эквивалентности состояний

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

• для всех входных цепочек w состояние 8 (р, и>) является допускающим тогда и только тогда, когда состояние 5 (q, w) — допускающее.

Менее формально, эквивалентные состояния puq невозможно различить, если просто прове­рить, допускает ли автомат данную входную цепочку, начиная работу в одном (неизвестно, каком именно) из этих состояний. Заметим, что состояния 8 (p,w) и 8 (q, vt>) могут и не сов­падать — лишь бы оба они были либо допускающими, либо недопускающими.

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

Пример 4.18. Рассмотрим ДКА на рис. 4.8. Функцию переходов этого автомата обо­значим через 8. Очевидно, что некоторые пары состояний не эквивалентны, например С и G, потому что первое из них допускающее, а второе — нет. Пустая цепочка различает эти состояния, так как 8 (С, е) — допускающее состояние, а 8 (G, е) — нет.

о

Рис. 4.8. Автомат с эквивалентными состояниями 172      ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ

Рассмотрим состояния А и G. Различить их с помощью цепочки £ невозможно, так как оба они недопускающие. О также не различает их, поскольку по входу 0 автомат пе­реходит в состояния В и G, соответственно, а оба эти состояния недопускающие. Однако цепочка 01 различает А и G, так как 8 (А, 01) = С, 8 (G, 01) = £, состояние С— допус­кающее, а Е— нет. Для доказательства неэквивалентности А и G достаточно любой входной цепочки, переводящей автомат из состояний А и G в состояния, одно из которых является допускающим, а второе — нет.

Рассмотрим состояния А и Е. Ни одно из них не является допускающим, так что це­почка е не различает их. По входу 1 автомат переходит и из А, и из £ в состояние F. Та­ким образом, ни одна входная цепочка, начинающаяся с 1, не может различить их, по­скольку 5 (А, 1х) = 5 (Е, 1х) для любой цепочки х.

Рассмотрим поведение в состояниях А и Е на входах, которые начинаются с 0. Из со­стояний А и £ автомат переходит в В и Я, соответственно. Так как оба эти состояния не­допускающие, сама по себе цепочка 0 не отличает А от £. Однако состояния В и Яне помогут: по входу 1 оба эти состояния переходят в С, а по входу 0 — в G. Значит, ни од­на входная цепочка, начинающаяся с 0, не может различить состояния А и £. Следова­тельно, ни одна входная цепочка не различает состояния А и £, т.е. они эквивалентны. □

Для того чтобы найти эквивалентные состояния, нужно выявить все пары различи­мых состояний. Как ни странно, но если найти все пары состояний, различимых в соот­ветствии с представленным ниже алгоритмом, то те пары состояний, которые найти не удастся, будут эквивалентными. Алгоритм, который называется алгоритмом заполнения таблицы, состоит в рекурсивном обнаружении пар различимых состояний ДКА А = (в, Ъ,8,9о, F)-

Базис. Если состояние р — допускающее, a q — не допускающее, то пара состояний {р, q} различима.

Индукция. Пусть р и q — состояния, для которых существует входной символ а, приводящий их в различимые состояния г = 8(р, а) и s = S(q, а). Тогда {р, q} — пара раз­личимых состояний. Это правило очевидно, потому что должна существовать цепочка w, отличающая г от s, т.е. только одно из состояний 8 (г, w) и 8 (s, и>) является допускаю­щим. Тогда цепочка aw отличает р от q, так как 8 (р, aw) и 8 (q, aw) — это та же пара состояний, что и 8 (г, w) и 8 (s, и>).

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

В базисном случае, поскольку С— единственное допускающее состояние, записыва­ем х в каждую пару состояний, в которую входит С. Зная некоторые пары различимых состояний, можно найти другие. Например, поскольку пара {С, Я} различима, а состоя­ния £ и F по входу 0 переходят в Я и С, соответственно, то пара {Е, F} также различима. Фактически, все х на рис. 4.9, за исключением пары {A, G}, получаются очень просто: посмотрев на переходы из каждой пары состояний по символам 0 или 1, обнаружим (для одного из этих символов), что одно состояние переходит в С, а другое — нет. Различи­мость пары состояний {A, G} видна в следующем цикле, поскольку по символу 1 они пе­реходят в F и Е, соответственно, а различимость состояний {Е, F} уже установлена.

в    х

С    х х

D  ххх Е ххх

р    х х х                   х

д    х х х х х х

f] X              X X X X X

А В С D Е F G Рис. 4.9. Таблица неэквивалентности состояний

Однако обнаружить другие пары различимых состояний невозможно. Следовательно, оставшиеся три пары состояний {А, £}, {В, Я} и {Д F} эквивалентны. Выясним, почему нельзя утверждать, что пара состояний {А, £} различима. По входному символу 0 со­стояния А и £ переходят в В и Я, соответственно, а про эту пару пока неизвестно, разли­чима она, или нет. По символу 1 оба состояния А и £ переходят в F, так что нет никакой надежды различить их этим способом. Остальные две пары, {В, Я} и {Д F}, различить нельзя, поскольку у них одинаковые переходы как по символу 0, так и по 1. Таким обра­зом, алгоритм заполнения таблицы останавливается на таблице, представленной на рис. 4.9, и корректно определяет эквивалентные и различимые состояния. □

Теорема 4.20. Если два состояния не различаются с помощью алгоритма заполнения таблицы, то они эквивалентны.

Доказательство. Снова рассмотрим ДКА А = (Q, <5, q₀, F). Предположим, что ут­верждение теоремы неверно, т.е. существует хотя бы одна пара состояний {р, q), для ко­торой выполняются следующие условия.

1. Состояния р и q различимы, т.е. существует некоторая цепочка w, для которой толь­ко одно из состояний 8 (p,w) и 8 (q,w) является допускающим.
2. Алгоритм заполнения таблицы не может обнаружить, что состоянияр и q различимы. Назовем такую пару состояний плохой парой.

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

I

I

[p, q\ — плохая, a w = aja₂. ,.a„ — кратчайшая из всех цепочек, различающих р и q. То­гда только одно из состояний 8 (p,w) и 8 (q, и>) является допускающим.

Заметим, что цепочка w не может быть е, так как, если некоторая пара состояний раз­личается с помощью е, то ее можно обнаружить, выполнив базисную часть алгоритма заполнения таблицы. Следовательно, п > 1.

Рассмотрим состояния г = 8(р, aj)\is = 8(q, а,). Эти состояния можно различить с по­мощью цепочки а₂а₃…а„, поскольку она переводит г и s в состояния 8 {р, w) и 8 (q, w). Однако цепочка, отличающая г от s, короче любой цепочки, различающей плохую пару. Следовательно, {г, 5} не может быть плохой парой, и алгоритм заполнения таблицы дол­жен был обнаружить, что эти состояния различимы.

Но индуктивная часть алгоритма заполнения таблицы не остановится, пока не придет к выводу, что состояния р и q также различимы, поскольку уже обнаружено, что состоя­ние 8(р, а{) = г отличается от 8(q, aj) = s. Получено противоречие с предположением о том, что существуют плохие пары состояний. Но если плохих пар нет, то любую пару различимых состояний можно обнаружить с помощью алгоритма заполнения таблицы, и теорема доказана. □

4.4.2. Проверка эквивалентности регулярных языков

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

Далее проверяем эквивалентность начальных состояний двух заданных ДКА, используя алгоритм заполнения таблицы. Если они эквивалентны, то L = М, а если нет, то ЬФМ.

Пример 4.21. Рассмотрим два ДКА (рис. 4.10). Каждый ДКА допускает пустую це­почку и все цепочки, которые заканчиваются символом 0, т.е. язык регулярного выраже­ния е+(0 + 1)*0. Можно представить, что на рис. 4.10 изображен один ДКА, содержа­щий пять состояний от А до Е. Если применить алгоритм заполнения таблицы к этому автомату, то в результате получим таблицу, представленную на рис. 4.11.

Чтобы заполнить эту таблицу, начнем с размещения х в ячейках, соответствующих тем парам состояний, из которых только одно является допускающим. Оказывается, что больше делать ничего не нужно. Остальные четыре пары {А, С}, {A, D}, {С, D} и {В, Е) являются парами эквивалентных состояний. Необходимо убедиться, что в индуктивной части алгоритма заполнения таблицы различимые состояния не обнаружены. Например, с помощью такой таблицы (см. рис. 4.11) нельзя различить пару {A, D}, так как по сим­волу 0 эти состояния переходят сами в себя, а по 1 — в пару состояний {В, Е}, которая

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

Рис. 4.10. Два эквивалентных ДКА

о                             1

В х С х

D х

Е х хх

А В С D

Рис. 4.11. Таблица различимости для автоматов, представленных на рис. 4.10

Время заполнения таблицы, а значит и время проверки эквивалентности двух состоя­ний, полиномиально относительно числа состояний. Если число состояний равно п, то количество пар состояний равно Ц), или п(п- 1)/2. За один цикл рассматриваются все пары состояний, чтобы определить, является ли одна из пар состояний-преемников раз­личимой. Значит, один цикл занимает время не больше 0(п²). Кроме того, если в некото­ром цикле не обнаружены новые пары различимых состояний, то алгоритм заканчивает­ся. Следовательно, количество циклов не превышает 0{п²), а верхняя граница времени заполнения таблицы равна О(п).

Однако с помощью более аккуратно построенного алгоритма можно заполнить таб­лицу за время 0{п²). С этой целью для каждой пары состояний {г, 5} необходимо соста­вить список пар состояний {р, q}, «зависящих» от {г, 5}, т.е., если пара {г, 5} различима, то {р, q\ также различима. Вначале такие списки создаются путем рассмотрения каждой
пары состояний {p,q}, и для каждого входного символа а (а их число фиксировано) пара {р, q} вносится в список для пары состояний-преемников {S(p, a), 5(q, а)}.

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

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

4.4.3. Минимизация ДКА

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

Основная идея минимизации ДКА состоит в том, что понятие эквивалентности со­стояний позволяет объединять состояния в блоки следующим образом.

1. Все состояния в блоке эквиваленты.
2. Любые два состояния, выбранные из разных блоков, неэквивалентны.

Пример 4.22. Рассмотрим рис. 4.9, на котором представлены эквивалентность и раз­личимость для состояний, изображенных на рис. 4.8. Эти состояния разбиваются на эк­вивалентные блоки следующим образом: ({А, £}, {В, Н}, {С}, {D, F}, {G}). Заметим, что каждая пара эквивалентных состояний помещена в отдельный блок, а состояния, отли­чимые от всех остальных, образуют отдельные блоки.

Для автомата, представленного на рис. 4.10, разбиение на блоки имеет вид ({А, С, D}, {В, £}). Этот пример показывает, что в блоке может быть более двух состояний. Может показаться случайностью, что состояния А, С и D помещены в один блок потому, что каждые два из них эквивалентны и ни одно из этих состояний не эквивалентно еще како­му-нибудь состоянию, кроме этих. Однако следующая теорема утверждает, что такая си­туация следует из определения эквивалентности состояний. □

Теорема 4.23. Эквивалентность состояний транзитивна, т.е., если для некоторого ДКА А = (Q, Е, 5, q₀, F) состояние р эквивалентно q, a q — г, то состояния риг также эквивалентны.

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

Предположим, что {р, q} и {q, г} — пары эквивалентных состояний, а пара {р, г} — различима. Тогда должна существовать такая цепочка w, для которой только одно из со­стояний 8 (p,w) и 8 {г, и>) является допускающим. Используя симметрию, предположим, что 8 (p,w) — допускающее.

Теперь посмотрим, будет ли состояние 8 (q, w) допускающим. Если оно допускаю­щее, то пара {q, г} различима, так как состояние 8 (q, w) —допускающее, а 8 (г, vi>) — нет. Если 8 (q, w) не допускающее, то по аналогичным причинам пара {р, q} различима. Полученное противоречие доказывает неразличимость пары {р, г}, т.е. состояния риг эквивалентны. □

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

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

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

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

Теорема 4.24. Если для каждого состояния q некоторого ДКА создать блок, состоя­щий из q и эквивалентных ему состояний, то различные блоки состояний образуют раз­биение множества состояний.^[6] Это значит, что каждое состояние может принадлежать только одному блоку. Состояния из одного блока эквивалентны, а любые состояния, вы­бранные из разных блоков, не эквивалентны. □

Теперь можно кратко сформулировать алгоритм минимизации ДКА А = (Q, Е, 8, q₀, F).

1. Для выявления всех пар эквивалентных состояний применяем алгоритм заполнения таблицы.
2. Разбиваем множество состояний Q на блоки взаимно эквивалентных состояний с помощью описанного выше метода.
3. Строим ДКА В с минимальным числом состояний, используя в качестве его состоя­ний полученные блоки. Пусть у— функция переходов автомата В. Предположим, что S — множество эквивалентных состояний автомата А, а — входной символ. То­гда должен существовать один блок состояний Т, содержащий y(q, а) для всех со­стояний q из S. Если это не так, то входной символ а переводит два состояния р и q из 5 в состояния, принадлежащие разным блокам согласно теореме 4.24. Из этого можно сделать вывод, что состояния р и q не были эквивалентными и не могли вместе принадлежать S. В результате определяется функция переходов ){S, а) = Т. Кроме того:

а)   начальным состоянием ДКА В является блок, содержащий начальное со­стояние автомата А;

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

Пример 4.25. Минимизируем ДКА, представленный на рис. 4.8. В примере 4.22 уста­новлены блоки разбиения состояний. На рис. 4.12 изображен ДКА с минимальным чис­лом состояний. Пять состояний этого автомата соответствуют пяти блокам эквивалент­ных состояний автомата на рис. 4.8.

Начальным состоянием минимизированного автомата является {А, £}, так как А было начальным на рис. 4.8. Единственным допускающим — {С}, поскольку С—■ это единст­венное допускающее состояние на рис. 4.8. Заметим, что переходы на рис. 4.12 правиль­но отражают переходы на рис. 4.8. Например, на рис. 4.12 есть переход из {А,Е} в {В, Н} по символу 0. Это очевидно, так как А на рис. 4.8 переходит в В при чтении 0, а Е— в Я. Аналогично, при чтении 1 {А, £} переходит в {D, F}. По рис. 4.8 легко увидеть, что оба состояния А и Е переходят в F по 1, так что для {А, Е} состояние-преемник по 1 также выбрано правильно. Тот факт, что ни А, ни £ не переходят в D по 1, неважен. Чи­татель может проверить, что и все остальные переходы изображены правильно. □

Рис. 4.12. ДКА с минимальным числом состояний, эквивалентный автомату, изображенному на рис. 4.8

4.4.4. Почему минимизированный ДКА невозможно улучшить

Предположим, что задан ДКА А, и мы минимизируем его до ДКА М с помощью ме­тода разбиения из теоремы 4.24. Эта теорема показывает, что невозможно получить эк­вивалентный ДКА, группируя состояния автомата А в еще меньшее число групп. Но все же, может ли существовать другой ДКА N, не связанный с А, который допускал бы тот же язык, что и автоматы А и М, но имел бы состояний меньше, чем автомат Ml Методом от противного докажем, что такого автомата не существует.

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

Начальные состояния автоматов М я N неразличимы, так как L(M) = L{N). Далее, если состояния {р, q} неразличимы, то для любого входного символа их преемники также неразличимы. Если бы преемников можно было различить, то р и q также мож­но было различить.

Минимизация состояний НКА

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

Пример приведен на рис. 4.13. Никакие из трех состояний не являются эквивалентными. Очевидно, что допускающее состояние В отличается от не допускающих состояний А и С. Состояния А и С различаются входным символом 0. С переходит в {А} (недопускающее), тогда как А переходит в {А, В), которое включает допускающее состояние. Таким обра­зом, группирование состояний не уменьшает количества состояний на рис. 4.13. Однако можно построить меньший НКА для этого же языка, просто удалив состояние С. Заметим, что А и В (без С) допускают все цепочки, которые заканчиваются нулем, а добавление С не позволяет допускать другие цепочки.

0,1

Начало

Рис. 4.13. НКА, который невозможно минимизировать с помощью эквивалентности состояний

Ни М, ни N не могут иметь недостижимых состояний, иначе, исключив это состояние, можно было бы получить еще меньший ДКА для того же языка. Следовательно, каждое со­стояние автомата М неотличимо хотя бы от одного состояния автомата N. Выясним, поче­му это так. Пусть р— состояние автомата М. Тогда существует цепочка а,а₂. ,.а_ь перево­дящая М из начального состояния в р. Эта цепочка также переводит N из начального в не­которое состояние q. Из того, что начальные состояния этих автоматов неразличимы, следует, что состояния-преемники, соответствующие входному символу a_h также неразли­чимы. Состояния, следующие за этими состояниями при чтении а₂, также будут неразли­чимыми, и так далее, пока мы не придем к заключению, что состояния р и q неразличимы.

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

Теорема 4.26. Если из некоторого ДКА А с помощью алгоритма, описанного в тео­реме 4.24, построен ДКА М, то М имеет наименьшее число состояний из всех ДКА, эк­вивалентных/1. □

Можно сформулировать более сильное утверждение, чем теорема 4.26. Между состоя­ниями любого минимального ДКА N и состояниями ДКА М должно существовать взаимно однозначное соответствие. Как уже доказано, каждое состояние М эквивалентно одному состоянию N, и ни одно состояние М не может быть эквивалентным двум состояниям N. Аналогично можно доказать, что ни одно состояние N не может быть эквивалентным двум состояниям М, хотя каждое состояние автомата ./V должно быть эквивалентно одному из со­стояний ДКА Л/. Следовательно, существует только один ДКА с минимальным количест­вом состояний, эквивалентный А (с точностью до обозначений состояний).

4.4.5. Упражнения к разделу 4.4

4.4.1. (*) На рис. 4.14 представлена таблица переходов некоторого ДКА:

а)   составьте таблицу различимости для этого автомата;

б)   постройте эквивалентный ДКА с минимальным числом состояний.

	0	1
->А	В	А
В	А	С
С	D	Е
*D	D	А
Е	D	F
F	G	Е
G	F	G
Н	G	D

Рис. 4.14. ДКА, который нужно минимизировать Выполните упражнение 4.4.1 для ДКА, представленного на рис. 4.15.

	0	1
->А	В	Е
В	С	F
*С	D	Н
D	Е	Н
Е	F	I
*р	G	В
G	Н	В
Н	I	С
*1	А	Е

Рис. 4.15. Еще один ДКА, который нужно минимизировать

4.4.3. (!!) Пусть р и q — пара различимых состояний заданного ДКА А с п состояния­ми. Какой может быть самая точная верхняя граница длины кратчайшей цепоч­ки, различающей р и q, как функция от п?

Резюме

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

Литература

За исключением очевидных свойств замкнутости регулярных выражений (относительно объединения, конкатенации и итерации), которые были доказаны Клини [6], почти все ре­зультаты свойств замкнутости воспроизводят аналогичные результаты, полученные для контекстно-свободных языков (этому классу языков посвящены следующие главы). Таким образом, лемма о накачке для регулярных языков является упрощением соответствующего результата для контекстно-свободных языков (Бар-Хиллел, Перлес и Шамир [1]). Из ре­зультатов этой работы следуют некоторые другие свойства замкнутости, представленные в данной главе, а замкнутость относительно обратного гомоморфизма обоснована в [2].

Операция деления (см. упражнение 4.2.2) представлена в [3]. В этой работе обсуждается более общая операция, в которой вместо одиночных символов находятся регулярные языки. Ряд операций «частичного удаления», начиная с упражнения 4.2.8, в котором говорилось о первых половинах цепочек регулярного языка, был определен в [8]. Сейферас и Мак-Нотон [9] изучили общий случай, когда операция удаления сохраняет регулярность языков.

Алгоритмы разрешения, такие как проверка пустоты и конечности регулярных язы­ков, а также проверка принадлежности к регулярному языку, берут свое начало в [7]. Ал­горитмы минимизации числа состояний ДКА появились в [5]. В работе [4] предложен наиболее эффективный алгоритм нахождения минимального ДКА.

1. Bar-Hillel, М. Perles, and Е. Shamir, «On formal properties of simple phrase-structure grammars,» Z Phonetik. Spachwiss. Kommunikations-forsch. 14 (1961), pp. 143-172.
2. Ginsburg and G. Rose, «Operations which preserve definability in languages,» J. ACM 10:2 (1963), pp. 175-195. (Гинзбург С., Роуз Дж. Об инвариантности классов языков относительно некоторых преобразований. — Кибернетический сборник, Новая се­рия, вып. 5. — М.: Мир, 1968. — С. 138-166.)
3. Ginsburg and Е. Н. Spanier, «Quotients of context-free languages,» J. ACM 10:4 (1963), pp. 487-492.
4. E. Hopcroft, «An n log n algorithm for minimizing the states in a finite automaton,» in Z. Kohavi (ed.) The Theory of Machines and Computations, Academic Press, New York, pp. 189-196. (ХопкрофтДж. Алгоритм для минимизации конечного автомата.— Кибернетический сборник, Новая серия, вып. 11. — М.: Мир, 1974. — С. 177-184.)
5. A. Huffman, «The synthesis of sequential switching circuits,» J. Franklin Inst. 257:3-4 (1954), pp. 161-190 and 275-303.
6. C. Kleene, «Representation of events in nerve nets and finite automata,» in С. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 3-42. (Клини С.К. Представление событий в нервных сетях. — сб. «Автоматы». — М.: ИЛ, 1956, — С. 15-67.)
7. Е. Moore, «Gedanken experiments on sequential machines,» in С. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 129-153. (Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. — сб. «Авто­маты».— М.: ИЛ, 1956, —С. 179-210.)
8. Е. Stearns and J. Hartmanis, «Regularity-preserving modifications of regular expressions,» Information and Control 6:1 (1963), pp. 55-69.
9. I. Seiferas and R. McNaughton, «Regularity-preserving modifications,» Theoretical Computer Science 2:2 (1976), pp. 147-154.