6. Представления посредством морфизмов

6.1. Локальные и регулярные языки

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

Теория языков изобилует такими результатами характеризации. В этой главе будут рассматриваться характеризации, в которых операциями являются морфизмы и инверсные морфизмы. Особенно интересен случай, когда важный класс языков, как, например, класс из иерархии Хомского, порождается из единственного языка применением в точности одной морфической операции.

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

Рассмотрим морфизм h: ∑^*→∑^*₁. Отображение g языка ∑^*₁ в множество подмножеств ∑^*, такое, что

называется обращением или инверсией h и обозначается g = h^-1. Вообще отображения вида (6.1) называются инверсными морфизмами. Для языка L над алфавитом ∑₁ положим

g(L) = h^-1(L) = {w|h (w)∈L}.

Пусть - некоторый алфавит, A и B - подмножества ∑, а C - подмножество ∑². Тогда по теореме 2.7 язык

регулярен. Языки вида (6.2) с некоторыми ∑, A, B, C называются локальными.

Название "локальный" связано с тем, что если язык L имеет вид (6.2), то для того, чтобы выяснить, принадлежит ли произвольное слово w данному языку, достаточно локально просмотреть это слово. Действительно, предположим, что слово w записано на ленте, разделенной на клетки, по одной букве в клетке, и что имеется линейка с отверстием величиной в две ленточные клетки. Тогда, передвигая линейку, можно решить вопрос о принадлежности слова w языку L, не зная ничего, кроме A, B, C и ∑. В самом деле, размер отверстия позволяет определить, где начинается и кончается слово w, и тем самым проверить, стоят ли в начале и конце допустимые буквы. Можно также проверить, нет ли в слове w запрещенных подслов длины 2 (т. е. слов из C).

Локальные языки также называются "2-проверяемыми", что отражает интервал локального считывания, т. е. размер отверстия. Аналогичное определение можно дать для k-проверяемых языков: и в этом случае имеется в виду отверстие, через которое можно обозревать k соседних клеток^*.

^* (k-проверяемые языки образуют довольно узкий подкласс класса R всех регулярных языков. Интересная содержательная классификация R приводится в обзоре [Br^*].- Прим. перев.)

Локальные языки тесно связаны с конечными детерминированными автоматами, как видно из доказательства следующего простого результата.

Теорема 6.1. Каждый регулярный язык R, не содержащий пустого слова λ, можно представить в виде

где язык L локален, а h является побуквенным (т. е. отображающим каждую букву в букву) морфизмом. Каждый регулярный язык R₀, содержащий λ, можно представить в виде R₀ = h(L∪{λ}), где h и L удовлетворяют указанным условиям.

Доказательство. Очевидно, что второе утверждение является следствием первого. (Заметим, что локальный язык никогда не содержит λ.) Чтобы доказать первое утверждение, рассмотрим конечный детерминированный автомат G, представляющий язык R⊆∑^*₁. Пусть ∑ - алфавит, буквами которого являются помеченные стрелки автомата G. Таким образом, элементами 2 являются тройки (s, a, s'), такие, что в G есть стрелка, помеченная буквой a и ведущая из s в s'.

Рассмотрим теперь язык (6.2), где A (соответственно B) состоит из тех троек (s, a, s'), в которых s является начальной, а s' - заключительной вершиной, и

Пусть h: ∑^*→∑^*₁ - побуквенный морфизм, заданный равенством h((s, a, s')) = a. Теперь из нашего определения непосредственно следует, что (6.3) выполняется.

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

Основные результаты этой главы сводятся к тому, что каждый контекстно-свободный (соответственно рекурсивно перечислимый) язык L может быть представлен в виде L = h^-1_L(L₀), где L₀ - фиксированный контекстно-свободный (рекурсивно перечислимый) язык, а h_L - морфизм, зависящий от L. (Если L содержит пустое слово, то это утверждение нужно слегка видоизменить.) Сходный результат имеет место для контекстных языков. Мы покажем теперь, что никакое аналогичное утверждение не может иметь места для четвертого семейства языков в иерархии Хомского, а именно для семейства регулярных языков. В действительности установленный нами результат будет несколько сильнее. Морфическая характеризация для регулярных языков, использующая множества совпадения, будет дана в упр. 12.

Теорема 6.2. Не существует регулярного языка R₀, такого, что каждый регулярный язык R (не содержащий пустого слова) может быть представлен в виде R = h₁(h^-1₂ (R₀)), где h₁ и h₂ - морфизмы.

Доказательство. Мы будем рассуждать от противного, предположив, что такой язык R₀ существует. Пусть R₀ представим конечным детерминированным автоматом с п вершинами. Тогда и каждый язык вида h^-1₂ (R₀) представим конечным детерминированным автоматом с n вершинами. (Вспомним построение автомата A(h) в доказательстве леммы 5.2.) Но язык, представимый конечным детерминированным автоматом с п вершинами, имеет звездную высоту ≤n. (Это видно, например, из рассмотрения языков L(i, j, k) в доказательстве теоремы 2.9.) Следовательно, все языки вида h₂^-1(R₀) имеют звездную высоту ≤n. Очевидно, что морфический образ языка звездной высоты m сам имеет звездную высоту ≤m. (Заметим, что если язык задается регулярным выражением α, то его морфический образ задается регулярным выражением, полученным из α заменой каждой буквы ее морфическим образом.) Из этого в конечном итоге следует, что каждый язык вида h₁ (h₂^-1(R₀)) имеет звездную высоту ≤n, что противоречит теореме 3.2. ▫