Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 32
Текст из файла (страница 32)
Гишер [2). В его отчете, который считается устным, продемонстрировано, как добавление нескольких других операций, например, пересечения или перемешивания (см. упражнение 7.3.4), приводит к ошибочности данной проверки, хотя класс задаваемых языком при этом не изменяется. Еще до появления системы 1)Х1Х К.
Томпсон исследовал возможность применения регулярных выражений в таких командах, как утер, и придуманный им алгоритм выполнения таких команд можно найти в [5!. На ранней стадии развития 1)Х1Х появились другие команды, в которых активно использовались расширенные регулярные выражения, например, команда 1ех, предложенная М. Леском. Описание этой команды и других технологий, связанных с регулярными выражениями, можно найти в !1). 1. А. У. А1ю, К. Бег!11, апг! 3.
13. 1)!!шап, Сотрйеггк Ргшс!р!ед Тесйтдиег, апИ Твой, Аг1- Йзоп-'1тез!еу, Кеаб!п8 МА, 1986. (Ахи А. В., Сети Р., УльманДж. Компиляторы: принципы, технологии и инструменты. — Ме Издательский дом "Вильямс", 2001.) 2. 1. 1.. О!з!1ег, ЗТАХ-СБ-ТК-84-1033 (!984) 3. Б. С. К1еепе, "Кергезепгайоп оТ етепгв !п пегие пега апг! Вппе аигогпага", 1п С. Е.
Зпаппоп апй 1. МсСаггпу, А иготага Егае!!ед Рппсегоп 1)и!ч. Ргезз, ! 956, рр. 3-42. (Клини С.К. Представление событий в нервных сетях. ! сб. "Автоматы". — Мс ИЛ, 1956. — С. 15-67.) 4. К. МсХаийпгоп апг! Н. Уашаг!а, "Кейп!аг ехргезгйопз апг! ага!с 8гарпз Тог аигогпага", !ЕЕЕ Тгавж Е!ееггокйс Сотригегв 9:1 ()ап., 1960), рр. 39-47. 5. К. Тпошрзоп, "Кейп!аг ехргеввюп веагсп а!8ог!!пап", Сотт АСлг 11:6 ()ипе, 1968), рр. 419-422. 142 ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ ГЛАВА 4 Свойства регулярных языков В этой главе рассматриваются свойства регулярных языков.
В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков — теорема, которая называется "леммой о накачке" ("риптр!пя !енина") . Одними из важнейших свойств регулярных языков являются "свойства замкнутости". Эти свойства гюзволяют создавать распознаватели для одних языков, построенных из других с помощью определенных операпий. Например, пересечение двух регулярных языков также является регулярным. Таким образом, при наличии автоматов для двух различных регулярных языков можно (механически) построить автомат, который распознает их пересечение. Поскольку автомат для пересечения языков может содержать намного больше состояний, чем любой из двух данных автоматов, то "свойство замкнутости" может оказаться полезным инструментом для построения сложных автоматов.
Конструкпия для пересечения уже использовалась в разделе 2.!. Еще одну важную группу свойств регулярных языков образуют "свойства разрешимости". Изучение этих свойств позволяет ответить на важнейшие вопросы, связанные с автоматами. Так, можно выяснить, определяют ли два различных автомата один и тот же язык. Разрешимость этой задачи позволяет "минимизировать' автоматы, т.е. по данному автомату найти эквивалентный ему с наименьшим возможным количеством состояний. Задача минимизапни уже в течение десятилетий имеет большое значение при проектировании переключательных схем, поскольку стоимость схемы (плющадн чипа, занимаемого схемой) снижается при уменьшении количества состояний автомата, реализованного схемой.
4.1. Доказательство нерегулярности языков В предыдугцих разделах было установлено, что класс языков, известных как регулярные, имеет не менее четырех различных способов описания. Это языки, допускаемые ДКА, НКА и в-НКА; их можно также определять с помощью регулярных выражений. Не каждый язык является регулярным В этом разделе предлагается мощная техника доказательства нерегулярности некоторых языков, известная как "лемма о накачке". Ни- ' В русскоязычной литературе в свое время быя принят термин "лемма о р прастаиии". Однако, на наш взгляд, накачка'* точнее отражает суть оронсхоляшего.
-- 11рнн ре~). же приводится несколько примеров нерегулярных языков, В разделе 4.2 лемма о накачке используется вместе со свойствами замкнутости регулярных языков для доказательства нерегулярности других языков. 4.1.1. Лемяаа о накачке для регулярных языков Рассмотрим язык Е„=- 10" 1" ! п > 1) . Этот язык состоит из всех цепочек вида 01, 0011, 0001!1 и так далее, содержащих один или несколько нулей, за которыми следует такое же количество единиц. Утверждается, что язык Ел, нере~улярен. Неформально, если бы Е„, был ре~улярным языком, то допускался бы некоторым ДКА А, имеющим какое-то число состояний )г.
Предположим, что на вход автомата поступает Е нулей. Он находится в некотором состоянии после чтения каждого из 4 + 1 префиксов входной цепочки, т.е. е, О, 00, ..., 0~. Поскольку есть только 4 различных состояний, то согласно *'принципу голубятни", прочитав два различных префикса, например, 0' и 0', автомат должен находится в олном и том же состоянии, скажем, а.
Допустим, что, прочитав ! или У нулей, автомат А полу щет на вход 1. По прочтении ! единиц он должен допустить вход, если ранее получил ! нулей, и отвергнуть его, получив У нулей. Но в момент поступления 1 автомат А находится в состоянии а и не способен "вспомнить", какое число нулей, ! или ~', было принято. Следовательно, его можно "обманывать" и заставлять работать неправильно, т.е. допускать, когда он не должен этого делать, или наоборот.
Приведенное неформальное доказательство можно сделать точным. Однако к заключению о нерегулярности языка Еги приводит следующий общий результат. Теорема 4.1 Елея,иа о накачке для регулярных языков). Пусть Š— регулярный язык. Существует константа п (зависящая от Е), для которой каждую цепочку и из языка Е, удовлетворяющую неравенству )эе! > и, можно разбить на три цепочки в =хуе так, что выполняются следующие условия. 1. уке. 2, !ху! < л. 3. Дяя любого 1 > 0 цепочка ху также принадлежит Е.
Это значит, что всегда можно найти такую цепочку у недалеко от начала цепочки и, которую можно 'накачать". Таким образом, если цепочку у повторить любое число раз нли удалить (при Е =- 0), то результирующая цепочка все равно будет принадлежать языку Е. Доказательство. Пусть Š— ре~улярный язык.
Тогда Е = ЦА) для некоторого ДКА А. Пусть А имеет и состояний. Рассмотрим произвольную цепочку ж длиной не менее п, скажем, и = а~а> ..а, где т > л и каждый а, есть входной символ. Для ! = О, 1, 2, ..., п определим состояние р, как д (сул, а,а>..а,), где 6 — функция переходов автомата А, а аа — его начальное состояние.
Заметим, что р„= аа. 144 ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 1. Игрок 1 выбирает язык Е, нерегулярность которого нужно доказать. 2. Игрок 2 выбирает л, но не открывает его игроку 1; первый игрок должен построить игру для всех возможных значений и. 3. Игрок 1 выбирает цепочку н, которая может зависеть от л, причем ее длина должна быть не меньше л. 4. Игрок 2 разбивает цепочку н на х, у и г, соблюдая условия леммы о накачке, т.е.
у и а и 1ху~ < л. Опять-таки, он не обязан говорить первому игроку, чему равны х, у и х, хотя они должны удовлетворять условиям леммы. 5. Первый игрок "выигрывает'*, если выбирает х, которое может быть функцией от и, х, у и г и для которого цепочка ху г не принадлежит Е. Пример 4.2. Покажем, что язык Еги состоящий из всех цепочек с одинаковым числом нулей и единиц (расположенных в произвольном порядке), нерегулярен. В терминах игры, описанной во врезке "Лемма о накачке как игра двух противников", мы являемся игроком ! и должны иметь дело с любыми допустимыми ходами игрока 2. Предположим, что и — это та константа, которая согласно лемме о накачке должна существовать, если язык Е, регулярен, т,е.
"игрок 2" выбирает п. Мы выбираем цепочку н = О"!", которая наверняка принадлежит Е, Теперь "игрок 2" разбивает цепочку н на хух. Нам известно лишь, что у и в и 1ху( < и. Но эта информация очень полезна, и мы "выигрываем" следующим образом. Поскольку )ху~ < п, и цепочка ху расположена в начале цепочки ж, то она состоит только из нулей. Если язык Е, регулярен, то по лемме о накачке цепочка хх принадлежит Е (при )г = О в лемме) .
Цепочка хз содержит л единиц, так как все единицы цепочки н попадают в г. Но г в х» нулей меньше п, так как потеряны все нули нз у. Поскольку у Ф в, то вместе х и х содержат не более и — 1 нулей. Таким образом, предположив, что язык Е, регулярен, приходим к ошибочному выводу, что цепочка хз принадлежит Е»г Следовательно, методом от противного доказано, что язык Е„нерегулярен. П Пример 4.3. Докажем нерегулярность языка Ер„образованного всеми цепочками из единиц, длины которых — простые числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
