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

ÃËÀÂÀ 4ÑâîéñòâàðåãóëÿðíûõÿçûêîâВ этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагаетсяинструмент для доказательства нерегулярности некоторых языков — теорема, котораяназывается “леммой о накачке” (“pumping lemma”)1.Одними из важнейших свойств регулярных языков являются “свойства замкнутости”.Эти свойства позволяют создавать распознаватели для одних языков, построенных издругих с помощью определенных операций. Например, пересечение двух регулярныхязыков также является регулярным.

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

Изучение этих свойств позволяет ответить на важнейшие вопросы, связанные с автоматами. Так, можно выяснить, определяют ли два различных автомата один и тот же язык.Разрешимость этой задачи позволяет “минимизировать” автоматы, т.е. по данному автомату найти эквивалентный ему с наименьшим возможным количеством состояний. Задачаминимизации уже в течение десятилетий имеет большое значение при проектировании переключательных схем, поскольку стоимость схемы (площади чипа, занимаемого схемой)снижается при уменьшении количества состояний автомата, реализованного схемой.4.1. Äîêàçàòåëüñòâî íåðåãóëÿðíîñòè ÿçûêîâВ предыдущих разделах было установлено, что класс языков, известных как регулярные, имеет не менее четырех различных способов описания.

Это языки, допускаемыеДКА, НКА и ε-НКА; их можно также определять с помощью регулярных выражений.Не каждый язык является регулярным. В этом разделе предлагается мощная техникадоказательства нерегулярности некоторых языков, известная как “лемма о накачке”. Ни1В русскоязычной литературе в свое время был принят термин “лемма о разрастании”. Однако, на наш взгляд, “накачка” точнее отражает суть происходящего. — Прим.

ред.же приводится несколько примеров нерегулярных языков. В разделе 4.2 лемма о накачкеиспользуется вместе со свойствами замкнутости регулярных языков для доказательстванерегулярности других языков.4.1.1. Ëåììà î íàêà÷êå äëÿ ðåãóëÿðíûõ ÿçûêîâРассмотрим язык L01 = {0n1n | n ≥ 1}. Этот язык состоит из всех цепочек вида 01, 0011,000111 и так далее, содержащих один или несколько нулей, за которыми следует такоеже количество единиц. Утверждается, что язык L01 нерегулярен. Неформально, если быL01 был регулярным языком, то допускался бы некоторым ДКА А, имеющим какое-точисло состояний k. Предположим, что на вход автомата поступает k нулей.

Он находитсяв некотором состоянии после чтения каждого из k + 1 префиксов входной цепочки, т.е. ε,0, 00, …, 0k. Поскольку есть только k различных состояний, то согласно “принципу голубятни”, прочитав два различных префикса, например, 0i и 0j, автомат должен находится водном и том же состоянии, скажем, q.Допустим, что, прочитав i или j нулей, автомат А получает на вход 1. По прочтении iединиц он должен допустить вход, если ранее получил i нулей, и отвергнуть его, получивj нулей. Но в момент поступления 1 автомат А находится в состоянии q и не способен“вспомнить”, какое число нулей, i или j, было принято.

Следовательно, его можно“обманывать” и заставлять работать неправильно, т.е. допускать, когда он не долженэтого делать, или наоборот.Приведенное неформальное доказательство можно сделать точным. Однако к заключению о нерегулярности языка L01 приводит следующий общий результат.Теорема 4.1 (лемма о накачке для регулярных языков). Пусть L — регулярный язык.Существует константа n (зависящая от L), для которой каждую цепочку w из языка L,удовлетворяющую неравенству |w| ≥ n, можно разбить на три цепочки w = xyz так, чтовыполняются следующие условия.1.y ≠ ε.2.|xy| ≤ n.3.Для любого k ≥ 0 цепочка xykz также принадлежит L.Это значит, что всегда можно найти такую цепочку y недалеко от начала цепочки w, которую можно “накачать”. Таким образом, если цепочку y повторить любое число раз илиудалить (при k = 0), то результирующая цепочка все равно будет принадлежать языку L.Доказательство.

Пусть L — регулярный язык. Тогда L = L(A) для некоторого ДКА A.Пусть A имеет n состояний. Рассмотрим произвольную цепочку w длиной не менее n,скажем, w = a1a2…am, где m ≥ n и каждый ai есть входной символ. Для i = 0, 1, 2, …, n∧определим состояние pi как δ (q0, a1a2…ai), где δ — функция переходов автомата A, аq0 — его начальное состояние. Заметим, что p0 = q0.144ÃËÀÂÀ 4.

ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂРассмотрим n + 1 состояний pi при i = 0, 1, 2, …, n. Поскольку автомат A имеет n различных состояний, то по “принципу голубятни” найдутся два разных целых числа i и j(0 ≤ i < j ≤ n), при которых pi = pj. Теперь разобьем цепочку w на xyz.1.x = a1a2…ai.2.y = ai+1ai+2…aj.3.z = aj+1aj+2…am.Таким образом, x приводит в состояние pi, y — из pi обратно в pi (так как pi = pj), аz — это остаток цепочки w. Взаимосвязи между цепочками и состояниями показаны нарис. 4.1.

Заметим, что цепочка x может быть пустой при i = 0, а z — при j = n = m. Однакоцепочка y не может быть пустой, поскольку i строго меньше j.НачалоРис. 4.1. Каждая цепочка, длина которой больше числа состояний автомата,приводит к повторению некоторого состоянияТеперь посмотрим, что происходит, когда на вход автомата A поступает цепочка xykzдля любого k ≥ 0. При k = 0 автомат переходит из начального состояния q0 (которое естьтакже p0) в pi, прочитав x. Поскольку pi = pj, то z переводит A из pi в допускающее состояние (см. рис. 4.1).Если k > 0, то по x автомат A переходит из q0 в pi, затем, читая yk, k раз циклически проходит через pi, и, наконец, по z переходит в допускающее состояние. Таким образом, длялюбого k ≥ 0 цепочка xykz также допускается автоматом A, т.е.

принадлежит языку L. †4.1.2. Ïðèìåíåíèå ëåììû î íàêà÷êåРассмотрим несколько примеров использования леммы о накачке. В каждом примере эталемма применяется для доказательства нерегулярности некоторого предлагаемого языка.Ëåììà î íàêà÷êå êàê èãðà äâóõ ïðîòèâíèêîâВ разделе 1.2.3 говорилось о том, что любую теорему, утверждение которой содержитнесколько чередующихся кванторов “для всех” (“для любого”) и “существует”, можнопредставить в виде игры двух противников. Лемма о накачке служит важным примеромтеорем такого типа, так как содержит четыре разных квантора: “для любого регулярного языка L существует n, при котором для всех w из L, удовлетворяющих неравенству|w| ≥ n, существует цепочка xyz, равная w, удовлетворяющая …”. Применение леммы онакачке можно представить в виде игры со следующими правилами.4.1. ÄÎÊÀÇÀÒÅËÜÑÒÂÎ ÍÅÐÅÃÓËßÐÍÎÑÒÈ ßÇÛÊÎÂ1451.

Игрок 1 выбирает язык L, нерегулярность которого нужно доказать.2. Игрок 2 выбирает n, но не открывает его игроку 1; первый игрок должен построить игру для всех возможных значений n.3. Игрок 1 выбирает цепочку w, которая может зависеть от n, причем ее длина должна быть не меньше n.4. Игрок 2 разбивает цепочку w на x, y и z, соблюдая условия леммы о накачке, т.е.y ≠ ε и |xy| ≤ n.

Опять-таки, он не обязан говорить первому игроку, чему равны x, yи z, хотя они должны удовлетворять условиям леммы.5. Первый игрок “выигрывает”, если выбирает k, которое может быть функцией от n,x, y и z и для которого цепочка xykz не принадлежит L.Пример 4.2. Покажем, что язык Leq, состоящий из всех цепочек с одинаковым числомнулей и единиц (расположенных в произвольном порядке), нерегулярен.

В терминах игры, описанной во врезке “Лемма о накачке как игра двух противников”, мы являемся игроком 1 и должны иметь дело с любыми допустимыми ходами игрока 2. Предположим,что n — это та константа, которая согласно лемме о накачке должна существовать, еслиязык Leq регулярен, т.е. “игрок 2” выбирает n. Мы выбираем цепочку w = 0n1n, котораянаверняка принадлежит Leq.Теперь “игрок 2” разбивает цепочку w на xyz. Нам известно лишь, что y ≠ ε и |xy| ≤ n.Но эта информация очень полезна, и мы “выигрываем” следующим образом. Поскольку|xy| ≤ n, и цепочка xy расположена в начале цепочки w, то она состоит только из нулей.Если язык Leq регулярен, то по лемме о накачке цепочка xz принадлежит Leq (при k = 0 влемме)2.