2.3. Регулярные выражения

Важную роль в теории формальных языков играют разные операции над языками. Поскольку языки являются множествами, для них естественно определены булевы операции объединения, пересечения и дополнения. Для двух языков L₁ и L₂ L₁∪L₂ и L₁∩L₂ обозначают теоретико-множественное объединение и пересечение соответственно. Если L₁ есть язык над алфавитом ∑, но не над каким-либо собственным подалфавитом алфавита ∑ (т. е. ∑ является минимальным алфавитом для L₁), то дополнение ~L₁ языка L₁ состоит из всех слов из ∑*, не принадлежащих языку L₁. (Если мы хотим обеспечить единственность дополнения, то надо указать алфавит, поскольку любой язык над ∑ является также языком над произвольным алфавитом, содержащим ∑. В доказательстве теоремы 2.5 молчаливо предполагалось, что алфавит заранее задан.)

Катенация (или произведение) двух языков L₁ и L₂ определяется как

Катенация, очевидно, является ассоциативной операцией, и, следовательно, для i≥1 можно использовать обычное определение степени U. Кроме того, L0 определяется как язык Щ.

Катенативным замыканием L* языка L называется объединение всех степеней Lⁱ для i≥0. Таким образом, слово w принадлежит языку L^* тогда и только тогда, когда или w = λ, или w является катенацией любого конечного числа слов из L.

Эти три операции - объединение, катенация и катенативное замыкание - называются регулярными. Для данного алфавита ∑ пустой язык ∅ и каждый язык {а}, где a∈∑, называются атомарными языками над ∑. Язык над ∑ называется регулярным, если он может быть получен из атомарных языков с помощью конечного числа применений регулярных операций. Регулярное выражение - это формула, показывающая, как определяемый ею язык получается из атомарных языков посредством регулярных операций.

Более точно регулярное выражение над ∑ рекурсивно определяется следующим образом:

(i) ∅ и каждая буква а из 2 являются регулярными выражениями над ∑;

(ii) если α и β - регулярные выражения над ∑, то таковыми являются (α∪β), (αβ) и α^*;

(iii) все регулярные выражения над ∑ получаются по (i) и (ii).

Каждое регулярное выражение над ∑, очевидно, задает некоторый язык над ∑: ∅ задает пустой язык, a - язык {a}, (α∪β) - объединение языков, обозначенных α и β, (αβ) - их катенацию, а а* - катенативное замыкание языка, обозначенного через а. Например, регулярное выражение a(bb)^* задает язык {ab²ⁱ|i≥0}. (Необязательные скобки в регулярных выражениях мы опускаем. Порядок следования операций тот же, что и в алгебре: катенативное замыкание сильнее катенации, а катенация сильнее объединения.)

Регулярные операции и языки иногда называются рациональными, поскольку регулярные операции напоминают обычные рациональные операции. В теории формальных степенных рядов (см. [Sal S]) это сходство выражено особенно отчетливо.

Мы определили два семейства языков - представимые и регулярные языки - совершенно разными способами: первые посредством распознающего устройства, а вторые посредством рекурсивного построения. Теорема Клини утверждает, что в действительности эти семейства совпадают. Сначала мы установим, что семейство регулярных языков входит в семейство представимых языков.

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

Доказательство. Второе утверждение следует из первого, поскольку представимость каждого атомарного языка очевидна.

Рассмотрим первое утверждение. Предположим, что языки L₁ и L₂ представимы. В силу леммы 2.2 можно предполагать, что L_i = L(G_i), где G_i является грамматикой типа 3 для i = 1, 2. Поскольку нетерминалы всегда можно переименовать, не изменяя порождаемого языка, то в дальнейшем можно считать, что нетерминальные алфавиты грамматик G₁ и G₂ не пересекаются.

Теперь для каждого из языков

легко построить грамматику G_i типа 3, порождающую язык L_i (i = 3, 4, 5). Действительно, для построения G₃ достаточно взять объединения соответствующих компонент грамматик G₁ и G₂: нетерминалов, терминалов, начальных символов и систем подстановок.

Терминальный (соответственно нетерминальный) алфавит G₄ является объединением терминальных (нетерминальных) алфавитов грамматик G₁ и G₂. Начальными символами грамматики d являются начальные символы грамматики G₁. Множество продукций грамматики G₄ состоит из

(i) продукций грамматики G₂;

(ii) продукций грамматики G₁, за исключением тех, которые имеют вид A→λ, и

(iii) продукции A→α для каждой продукции A→λ грамматики G₁ и каждой продукции В→α грамматики G₂, где B - начальный символ.

Наконец, множество продукций грамматики G₃ состоит из продукций грамматики G₁ и, кроме того, из

(i) продукции A→α для каждой продукции A→λ и каждой продукции B→α из G₁, где B - начальный символ в G₁;

(ii) продукции B'→λ, где B' - новый начальный символ, добавляемый к алфавиту G₁.

(Заметим, что (ii) необходимо для того, чтобы обеспечить вхождение λ в порождаемый язык.)

Теперь утверждение леммы 2.6 следует из леммы 2.2. □

Используя теорему 2.5 и лемму 2.6 (а также тот факт, что пересечение можно выразить через объединение и дополнение), мы приходим к следующему результату.

Теорема 2.7. Семейство представимых языков замкнуто относительно булевых операций.

Заметим, что наше доказательство теоремы 2.7 конструктивно: если язык L получен посредством булевых операций из представимых языков L₁, ..., L_n и заданы конечные автоматы, представляющие L₁, ..., L_n, то можно построить автомат, представляющий L.

Ясно, что для произвольных L₁ и L₂ равенство L₁ = L₂ выполняется тогда и только тогда, когда

В силу теоремы 2.5 проблема пустоты представимого языка разрешима. Отсюда мы получаем следующий результат.

Теорема 2.8. Существует алгоритм, выясняющий, представляют ли два данных конечных автомата один и тот же

Теорема 2.8 замечательна, потому что обычно нет алгоритмов проверки эквивалентности устройств, определяющих 1зыки. Например, в гл. 5 будет показано, что для контекстно-свободных грамматик такого алгоритма не существует.