Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Регулярные языки и регулярные выражения

Регулярные языки и регулярные выражения


В замкнутом полукольце \mathcal{L}(V) всех языков в алфавите V рассмотрим подалгебру, порожденную множеством, которое состоит из пустого языка, языка \{\lambda\}, всех языков \{a\},~a\in V (каждый из которых содержит единственную однобуквенную цепочку a), и замкнутую относительно итерации. Эта подалгебра, обозначаемая \mathcal{R}(V), есть полукольцо с итерацией. Оно играет важнейшую роль в теории формальных языков. Его называют полукольцом регулярных языков. Далее будет доказано, что элементы полукольца \mathcal{R}(V) являются в точности регулярными языками, т.е. языками, порождаемыми регулярными грамматиками.


Теорема 7.4. Язык в алфавите V регулярен тогда и только тогда, когда он является элементом полукольца \mathcal{R}(V).


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


Таким образом, множество регулярных языков в алфавите V=\{a_1,\ldots,a_n\} есть не что иное, как замыкание конечного множества \bigl\{\varnothing,\{\lambda\}, \{a_1\},\ldots, \{a_n\}\bigr\} относительно операций объединения, соединения и итерации. Следовательно, как и всякое Ω-замыкание, оно может быть описано индуктивно, а именно:


1) пустое множество \varnothing, множество \{\lambda\} (состоящее из одной пустой цепочки) и множество \{a\} для каждого a\in V считаем регулярным языком в алфавите V;


2) если известно, что P и Q — регулярные языки в алфавите V, то к множеству регулярных языков в алфавите V следует добавить объединение P\cup Q и соединение PQ;


3) если известно, что P — регулярный язык в алфавите V, то к множеству регулярных языков в алфавите V следует добавить его итерацию P^{\ast};


4) никаких других регулярных языков, кроме определенных в пунктах 1-3, не существует.


Из определения регулярного языка, теоремы 7.4 и следствия 7.1 немедленно вытекает, что и позитивная итерация регулярного языка регулярна.


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


Алгебраические операции над регулярными языками удобно представлять с помощью так называемых регулярных выражений. Каждое регулярное выражение представляет (или обозначает) некоторый (однозначно определяемый) регулярный язык, причем языки \varnothing,\,\{\lambda\} и \{a\}, где a\in V, обозначаются выражениями \varnothing,\,\lambda и a соответственно, и если регулярное выражение p обозначает регулярный язык P, а регулярное выражение q обозначает регулярный язык Q, то регулярные выражения (p+q),\,(pq) и (p^{\ast}) обозначают регулярные множества P\cup Q,\,PQ и P^{\ast} соответственно. Таким образом, в регулярных выражениях для обозначения операции объединения языков используют знак "+" (плюс).


Условимся также для регулярного выражения \alpha\alpha^{\ast} или \alpha^{\ast}\alpha использовать обозначение \alpha^{+} и называть это выражение позитивной итерацией выражения \alpha.


Замечание 7.4. Введенные выше обозначения регулярных выражений создают при использовании символа \lambda некий "конфликт" обозначений. А именно мы можем, в зависимости от контекста, понимать этот символ и как обозначение самой пустой цепочки, и как обозначение языка, состоящего из одной пустой цепочки (это и будет собственно регулярное выражение \lambda). Эти интерпретации символа \lambda следует тщательно разграничивать. В то же время (и такова традиция изложения теории формальных языков) вряд ли целесообразно вводить для регулярного выражения, обозначающего язык \{\lambda\}, какое-то новое обозначение.


Можно сократить количество скобок в регулярных выражениях, приняв следующее соглашение о приоритетах: самый высокий приоритет имеет операция итерации, затем — соединения и, наконец, — объединения. Так, регулярное выражение a^{\ast}+(bc)^{\ast} обозначает множество цепочек, состоящее из цепочек вида a^n,\, n\geqslant0, и цепочек вида (bc)^n,\, n\geqslant0, где a,b,c\in V. Использование регулярных выражений позволяет получать более наглядную и простую нотацию для регулярных языков. Так, вместо рассмотренного выше регулярного выражения мы должны были бы использовать гораздо менее выразительную и более громоздкую формулу: \{a\}^{\ast}\cup (\{b\}\cdot \{c\})^{\ast}.


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


Рассмотрим регулярное выражение


x=(b^{+}a)^{\ast}(b^{+}a+b^{\ast}),\quad a,b,c\in V.

Используя аксиомы полукольца, преобразуем x следующим образом:


(b^{+}a)^{+}+ (b^{+}a)^{\ast}b^{\ast}= (b^{+}a)^{+}+ (b^{+}a)^{\ast}+ (b^{+}a)^{\ast} b^{+}= (b^{+}a)^{\ast}+ (b^{+}a)^{\ast}b^{+}= (b^{+}a)^{\ast}b^{\ast}.

Все регулярные выражения, фигурирующие в этих преобразованиях, эквивалентны, т.е. все они обозначают один и тот же регулярный язык. Проблемы распознавания эквивалентности двух произвольных регулярных выражений, автоматизации тождественных преобразований регулярных выражений и поиск самого короткого ("оптимального") регулярного выражения, обозначающего данный регулярный язык, весьма трудны и здесь не обсуждаются. В целом соотношение между регулярными выражениями и регулярными языками вполне аналогично соотношению между формулами и булевыми функциями. В частности, если переход от формулы к эквивалентной формуле в теории булевых функций совершается согласно аксиомам булевой алгебры и другим тождествам, выводимым из этих аксиом, то переход от заданного регулярного выражения к эквивалентному регулярному выражению производится согласно аксиомам полукольца и тождествам, выводимым из них.


Зачастую в дальнейшем, если это не повлечет непонимания, мы будем отождествлять регулярный язык с обозначающим его регулярным выражением (любым!), что позволит не вводить новых обозначений и пояснений. Так, для рассмотренного выше примера мы можем написать bbababbb\in(b^{+}a)^{\ast}b^{\ast}, что, строго говоря, обозначает факт принадлежности цепочки bbababbb языку, обозначенному регулярным выражением (b^{+}a)^{\ast}b^{\ast}. Разумеется, следует воздерживаться, например, от употребления такой записи: \lambda\in\lambda, хотя, если подумать, и здесь все понятно: пустая цепочка \lambda принадлежит языку \{\lambda\}, обозначаемому регулярным выражением \lambda.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved