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

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

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

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

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


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

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Так, вместо рассмотренного выше регулярного выражения мы должны были бы использовать гораздо менее выразительную и более громоздкую формулу: [math]\{a\}%^{\ast}\cup (\{b\}\cdot \{c\})^{\ast}[/math].


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


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


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

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


[math](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}.[/math]

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


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


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


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

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