Свойства регулярных языков

Множество называется замкнутым относительно некоторой операции, если в результате выполнения этой операции над любыми элементами, принадлежащими данному множеству, получается новый элемент, принадлежащий тому же множеству.

Например, множество целых чисел замкнуто относительно операций сложения, умножения и вычитания, но оно не замкнуто относительно операции деления — при делении двух целых чисел не всегда получается целое число.

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

Например, регулярные языки замкнуты относительно следующих операций:

• -пересечения;
• -объединения;
• -дополнения;
• -итерации;
• -конкатенации;
• -гомоморфизма (изменения имен символов и подстановки цепочек вместо символов).

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

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

Например, доказано, что разрешимыми являются следующие проблемы.

Проблема эквивалентности. Даны два регулярных языка L1(V) и L2(V). Необходимо проверить, являются ли эти два языка эквивалентными.

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

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

Эти проблемы разрешимы вне зависимости от того, каким из трех способов задан регулярный язык. Следовательно, эти проблемы разрешимы для всех способов представления регулярных языков: регулярных множеств, регулярных грамматик и конечных автоматов. На самом деле достаточно доказать разрешимость любой из этих проблем хотя бы для одного из способов представления языка, тогда для остальных способов можно воспользоваться алгоритмами преобразования, рассмотренными выше. (Возможны и другие способы представления регулярных множеств, а для них разрешимость указанных проблем будет уже не очевидна.).

Для регулярных грамматик также разрешима проблема однозначности — доказано, что для любой регулярной грамматики можно построить эквивалентную ей однозначную регулярную грамматику. Это очевидно, поскольку для любой регулярной грамматики можно однозначно построить регулярное выражение, определяющее заданный этой грамматикой язык.

Существует простой метод проверки, является или нет заданный язык регулярным. Этот метод основан на проверке так называемой леммы о разрастании языка. Доказано, что если для некоторого заданного языка выполняется лемма о разрастании регулярного языка, то этот язык является регулярным; если же лемма не выполняется, то и язык регулярным не является.

Лемма о разрастании для регулярных языков формулируется следующим образом: если дан регулярный язык и достаточно длинная цепочка символов, принадлежащая этому языку, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким способом новые цепочки будут принадлежать тому же регулярному языку. (Если найденную подцепочку повторять несколько раз, то исходная цепочка как бы «разрастается» — отсюда и название «лемма о разрастании языков»).

Формально эту лемму можно записать так: если дан язык L, то константа р > 0, такая, что если L и || р, то цепочку можно записать в виде =, где 0 < || < р, и тогда ' = i, 'L i 0.

Используя лемму о разрастании регулярных языков, докажем, что язык L = {аnЬn | n > 0} не является регулярным.

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка = аnЬn и запишем ее в виде =. Если a+ или b+ то тогда для i = 0 цепочка 0 = не принадлежит языку L, что противоречит условиям леммы; если же a+b+, тогда для i = 2 цепочка 2 = не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.