Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 23
Текст из файла (страница 23)
В то же время, в отличие от автоматов, регулярные выражения позволяют определять допустимые цепочки декларативным способом. Поэтому регулярные выражения используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим два примера. 1. Команды поиска, например, команда дгер операционной системы 1Лч1Х или аналогичные команды для поиска цепочек, которые можно встретить в %'еЬ-броузерах или системах форматирования текста.
В таких системах регулярные выражения используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют регулярное выражение либо в ДКА, либо в НКА и применяют этот автомат к файлу, в котором производится поиск. 2. Генераторы лексических анализаторов, такие как Ьех или Е!ех. Напомним, что лексический анализатор — это компонент компилятора, разбивающий исходную про- грамму на логические единицы (лексемы), которые состоят из одного или нескольких символов и имеют определенный смысл, Примерами лексем являются ключевые слова (например ъз(з21е), идентификаторы (любая буква, за которой следует нуль или несколько букв и/или цифр) и такие знаки, как + или <=. Г'енератор лексических анализаторов получает формальные описания лексем, являющиеся по существу регулярными выражениями, и создает ДКА, который распознает, какая из лексем по- является на его входе.
3.1.1. Операторы регулярных выражений Регулярные выражения обозначают (задают, или представляют) языки. В качестве простого примера рассмотрим регулярное выражение 01 ь10 . Оно определяет язык всех цепочек, состоящих либо из одного нуля, за которым следует любое количество единиц, либо из одной единицы, за которой следует произвольное количество нулей. В данный момент мы не рассчитываем, что читатель знает, как интерпретируются регулярные вы- ражения, поэтому наше утверждение о языке, задаваемом этим выражением, пока должно быть принято на веру. Чтобы понять, почему наша интерпретация заданного регулярного выражения правильна, необходимо определить все использованные в этом выраже- нии символы, поэтому вначале познакомимся со следующими тремя операциями над языками, соответствующими операторам регулярных выражений .
1. Объединение двух языков Е и М, обозначаемое Е () М, — это множество цепочек, которые содержатся либо в Е, либо в М, либо в обоих языках. Например, если Е = (001, 1О, 111) и М вЂ” — (е, 001), то Е 0 М = (е, !О, 001, 111). 2. Конканзенация языков Е и М вЂ” это множество цепочек, которые можно образовать путем дописывания к любой цепочке из Е любой цепочки из М. Выше в разделе 1.5.2 было дано определение конкатенации двух цепочек: результатом ее является запись одной цепочки вслед за другой. Конкатенация языков обозначается либо точкой, либо вообще никак не обозначается, хотя оператор конкатенации часто называют "точкой". Например, если Е = (001, 10,! 11) и М= (Е 001), то Е.М, или просто ЕМ, — это (001, 10, 111, 001001, 10001, 111001). Первые три цепочки в ЕМ вЂ” это цепочки из Е, соединенные с е.
Поскольку е является единицей (нейтральным элементом) для операции конкатенации, результирующие цепочки будут такими же, как и цепочки из Е. Последние же три цепочки в ЕМ образованы путем соединения каждой цепочки из Е со второй цепочкой из М, т.е. с 001. Например, 1О из Е, соединенная с 001 из М, даст 10001 для ЕМ. Будем употреблять также термины "рееилярные операции" и "регулярные операторы", принятые в русскоязычной литературе. — Прил. ред ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 102 3. Итераггия (" звездочка", или замыкание Клини ) языка Е обозначается Е и представг ляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества цепочек из Е.
При этом допускаются повторения, т.е. одна и та же цепочка из Е может быть выбрана для конкатенации более одного раза. Например, если Е = (О, 1), то Š— это все цепочки, состоящие из нулей и единиц. Если Е = (О, 11), то в Е входят цепочки из нулей и единиц, содержащие четное количество единиц, например, цепочки 011, 11110 или а, и не входят цепочки О! 011 или 101. Более форлгально язык Е можно представить как бесконечное объединение О,соЕ', где Е' = (а), Е' = Е и Е' для! > 1 равен ЕЕ...Е (конкатенация ! копий Е). Пример ЗЛЕ Поскольку идея итерации языка может показаться довольно сложной, рассмотрим несколько примеров.
Для начала возьмем Е = (О, 11). Е = (а) независимо от языка Е; нулевая степень означает выбор нулевого количества цепочек из языка Е. Е = Е, ! что означает выбор одной цепочки из Е. Таким образом, первые два члена в разложении Е дают (я,О, 11). Далее рассмотрим Е'. Выберем две цепочки из Е и, поскольку их можно выбирать с повторениями, получим четыре варианта, которые дают Е' = (00, 011, 110, 1111). Аналогично, Е представляет собой множество цепочек, образованных троекратным выбором из двух цепочек языка Е.
Следовательно, Ез имеет вид (000, 0011, 0110, 1100, 01111, 11011, 11110, 111111) Для вычисления Е необходимо вычислить Е' для каждого г и объединить все эти языки. Язык Е' содержит 2' элементов. Хотя каждое множество Е конечно, обьединение бесконечного числа множеств Е' образует, как правило, бесконечный язык, что справедливо, в частности, и для нашего примера.
Пусть теперь Š— множество всех цепочек, состояцгих из нулей. Заметим, что такой язык бесконечен, в отличие от предыдущего примера, где был рассмотрен конечный язык. Однако нетрудно увидеть, что представляет собой Е . Как всегда, Е' = (а), Е' = Е. Е' — это множество цепочек, которые люжно образовать, если взять одну цепочку из нулей и соединить ее с другой цепочкой из нулей. В результате получим цепочку, также состоящую из нулей. Фактически, любую цепочку из нулей можно записать как конкатенацию двух цепочек из нулей (не забывайте, что а — тоже "цепочка из нулей"'; она всегда может быть одной из двух соединяемых цепочек).
Следовательно, Е2 = Е. Аналогично, Е' = Е и так далее. Таким образом, бесконечное объединение Е = Е'() Е () Е 0 ... совпадает с Е в том особом случае, когда язык Е является множеством 1 2 всех нулевых цепочек. 2 Термин "замыкание Клини" связан с именем С. К.
Капни. который ввел понятие регулярного выражения и, в частности, зту операцию. 3.1. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 103 В качестве последнего примера рассмотрим И = (в). Заметим, что И' = (к), тогда как И' лля любого ! > 1 будет пустым множеством, поскольку мы не можем выбрать ни одной цепочки из пустого множества. Фактически, И является одним из всего двух языков, итерация которых ле является бесконечным множеством.
П 3.1.2. Построение регулярных выражений Все алгебры начинаются с некоторых элементарных выражений. Обычно это константы и/или переменные. Применяя определенный набор операторов к этим элементарным выражениям и уже построенным выражениям, можно конструировать более сложные выражения. Обычно необходимо также иметь некоторые методы группирования операторов и операндов, например, с помощью скобок. К примеру, обычная арифметическая алгебра начинается с констант (целые и действительные числа) и переменных и позволяет нам строить более сложные выражения с помощью таких арифметических операторов, как е или х. Использование оператора "звездочка'* Впервые оператор "звездочка" появился в разделе 1.5.2, где применялся к алфавиту, например Х .
С помощью этого оператора образуются все цепочки, символы которых принадлежат алфавиту Х. Оператор итерации в значительной мере похож на "звездочку", хотя существует несколько тонких отличий в типах. Предположим, что Š— это язык, содержащий цепочки длины 1, и для каждого символа а из Х существует цепочка а в Е.
Тогда, хотя Е и Х "выглядят*' одинаково, они принадлежат к различным типам; Е представляет собой множество цепочек, а Х— множество символов. С другой стороны, Е обозначает тот же язык, что и Х . Алгебра регулярных выражений строится по такой же схеме: используются константы и переменные для обозначения языков и операторы для обозначения трех операций из раздела 3.!.1 — объединение, точка и звездочка. Регулярные выражения можно определить рекурсивно. В этом определении не только характеризуются правильные регулярные выражения, но и лля каждого регулярного выражения Е описывается представленный им язык, который обозначается через Е(Е).
Базис. Базис состоит из трех частей. 1. Константы я и И являются регулярными выражениями, определяющими языки (в) и И, соответственно, т.е. Цк) = (я) и ЦИ) =- И. 2. Если а — произвольный символ, то а — регулярное выражение, определяющее язык (и), т.е.
Ца) = (а). Заметим, что для записи выражения, соответствующего символу, используется жирный шрифт. Это соответствие, т.е. что а относится к и, должно быть очевидным. 104 ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 3. Переменная, обозначенная прописной курсивной буквой, например, Ц представляет произвольный язык. Индукции.
Индуктивный шаг состоит из четырех частей, по одной для трех операторов и для введения скобок. 1. Если Е и Š— регулярные выражения, то Е+ Š— регулярное выражение, определяющее объединение языков Е(Е) и ЦЕ), т.е. Е(Е + Е) = Е(Е) () ЦЕ). 2. Если Е и Š— регулярные выражения, то ЕŠ— регулярное выражение, определяющее конкатенацию языков Е(Е) и Е(Е). Таким образом, Е(ЕЕ) = ЦЕ)ЦЕ). Заметим, что для обозначения оператора конкатенации — как операции над языками, так и оператора в регулярном выражении — можно использовать точку. Например, регулярное выражение 0.1 означает то же, что и 01, и представляет язык (О!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
