Регулярные языки и регулярные выражения
В замкнутом полукольце всех языков в алфавите рассмотрим подалгебру, порожденную множеством, которое состоит из пустого языка, языка , всех языков (каждый из которых содержит единственную однобуквенную цепочку ), и замкнутую относительно итерации. Эта подалгебра, обозначаемая , есть полукольцо с итерацией. Оно играет важнейшую роль в теории формальных языков. Его называют полукольцом регулярных языков. Далее будет доказано, что элементы полукольца являются в точности регулярными языками, т.е. языками, порождаемыми регулярными грамматиками.
Теорема 7.4. Язык в алфавите регулярен тогда и только тогда, когда он является элементом полукольца .
Здесь мы не будем доказывать эту теорему, а выведем ее позже, опираясь на другие теоремы о регулярных языках.
Таким образом, множество регулярных языков в алфавите есть не что иное, как замыкание конечного множества относительно операций объединения, соединения и итерации. Следовательно, как и всякое Ω-замыкание, оно может быть описано индуктивно, а именно:
1) пустое множество , множество (состоящее из одной пустой цепочки) и множество для каждого считаем регулярным языком в алфавите ;
2) если известно, что и — регулярные языки в алфавите , то к множеству регулярных языков в алфавите следует добавить объединение и соединение ;
3) если известно, что — регулярный язык в алфавите , то к множеству регулярных языков в алфавите следует добавить его итерацию ;
4) никаких других регулярных языков, кроме определенных в пунктах 1-3, не существует.
Из определения регулярного языка, теоремы 7.4 и следствия 7.1 немедленно вытекает, что и позитивная итерация регулярного языка регулярна.
Далее мы зачастую будем говорить просто о регулярных языках (или регулярных множествах), подразумевая, что фиксирован некоторый алфавит .
Алгебраические операции над регулярными языками удобно представлять с помощью так называемых регулярных выражений. Каждое регулярное выражение представляет (или обозначает) некоторый (однозначно определяемый) регулярный язык, причем языки и , где , обозначаются выражениями и соответственно, и если регулярное выражение обозначает регулярный язык , а регулярное выражение обозначает регулярный язык , то регулярные выражения и обозначают регулярные множества и соответственно. Таким образом, в регулярных выражениях для обозначения операции объединения языков используют знак "+" (плюс).
Условимся также для регулярного выражения или использовать обозначение и называть это выражение позитивной итерацией выражения .
Замечание 7.4. Введенные выше обозначения регулярных выражений создают при использовании символа некий "конфликт" обозначений. А именно мы можем, в зависимости от контекста, понимать этот символ и как обозначение самой пустой цепочки, и как обозначение языка, состоящего из одной пустой цепочки (это и будет собственно регулярное выражение ). Эти интерпретации символа следует тщательно разграничивать. В то же время (и такова традиция изложения теории формальных языков) вряд ли целесообразно вводить для регулярного выражения, обозначающего язык , какое-то новое обозначение.
Можно сократить количество скобок в регулярных выражениях, приняв следующее соглашение о приоритетах: самый высокий приоритет имеет операция итерации, затем — соединения и, наконец, — объединения. Так, регулярное выражение обозначает множество цепочек, состоящее из цепочек вида , и цепочек вида , где . Использование регулярных выражений позволяет получать более наглядную и простую нотацию для регулярных языков. Так, вместо рассмотренного выше регулярного выражения мы должны были бы использовать гораздо менее выразительную и более громоздкую формулу: .
Соответствие между регулярными множествами и регулярными выражениями не является взаимно однозначным: одно и то же регулярное множество может представляться многими регулярными выражениями. Продемонстрируем это на таком примере.
Рассмотрим регулярное выражение
Используя аксиомы полукольца, преобразуем следующим образом:
Все регулярные выражения, фигурирующие в этих преобразованиях, эквивалентны, т.е. все они обозначают один и тот же регулярный язык. Проблемы распознавания эквивалентности двух произвольных регулярных выражений, автоматизации тождественных преобразований регулярных выражений и поиск самого короткого ("оптимального") регулярного выражения, обозначающего данный регулярный язык, весьма трудны и здесь не обсуждаются. В целом соотношение между регулярными выражениями и регулярными языками вполне аналогично соотношению между формулами и булевыми функциями. В частности, если переход от формулы к эквивалентной формуле в теории булевых функций совершается согласно аксиомам булевой алгебры и другим тождествам, выводимым из этих аксиом, то переход от заданного регулярного выражения к эквивалентному регулярному выражению производится согласно аксиомам полукольца и тождествам, выводимым из них.
Зачастую в дальнейшем, если это не повлечет непонимания, мы будем отождествлять регулярный язык с обозначающим его регулярным выражением (любым!), что позволит не вводить новых обозначений и пояснений. Так, для рассмотренного выше примера мы можем написать , что, строго говоря, обозначает факт принадлежности цепочки языку, обозначенному регулярным выражением . Разумеется, следует воздерживаться, например, от употребления такой записи: , хотя, если подумать, и здесь все понятно: пустая цепочка принадлежит языку , обозначаемому регулярным выражением .
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|