4.4. Множества совпадения и их регулярность

Для двух заданных морфизмов g и h, отображающих ∑* в ∑^*₁ (где ∑ и ∑₁ - алфавиты и не исключено, что ∑₁ = ∑), определим язык совпадения (множество совпадения):

Например, если g и h определены на {a, b}^* равенствами

то E (g,h) состоит из всех таких слов w, что число вхождений a в w равно числу вхождений b в w. Легко видеть, что в этом случае множество E (g,h) не регулярно.

Для морфизмов g и h, определенных равенствами

имеем E(g, h) = {a²b²}^*. Для морфизмов g и h, определенных равенствами

имеем E(g, h) = {λ}. (Мы предоставляем читателю проверить эти факты.) Поскольку слово λ всегда содержится в множестве совпадения, в дальнейшем мы будем называть множество совпадения пустым, если оно содержит только λ. Таким образом, в последнем из приведенных выше примеров множество совпадения пусто.

Множества совпадения часто оказываются полезными в теории языков, как будет показано в гл. 5 и 6. Что касается результатов о разрешимости, то здесь желательно, чтобы рассматриваемые множества совпадения были регулярны. Первый из приведенных выше примеров свидетельствует о том, что это условие не всегда выполняется. Следующая теорема указывает класс морфизмов, для которого оно имеет место. Эта теорема чрезвычайно важна для решения проблемы эквивалентности DOL-систем¹.

¹ (Интересное исследование регулярности языков совпадения содержится в статье [Ka*].- Прим. перев.)

λ Пусть морфизмы g и h - конечные коды с ограниченной задержкой в одном и том же направлении. Тогда язык E(g,h) регулярен.

Прежде чем перейти к доказательству теоремы 4.9, введем одно вспомогательное понятие, которое представляет интерес и само по себе. Будем говорить, что пара (g, h) морфизмов обладает свойством единственного продолжения, если существует константа k, такая, что выполняется следующее условие: если слово x является префиксом какого-либо w∈E(g, h) и

то найдется в точности одна буква а, такая, что ха является префиксом некоторого слова из E(g,h).

Свойство единственного продолжения имеет место, в частности, в том случае, когда неравенство (4.19) с некоторой константой k не выполняется ни для одного префикса слов из E(g,h). В этом случае говорят, что пара (g,h) имеет ограниченный баланс (ср. также с упр. 8). Из трех рассмотренных выше примеров две последние пары (g, h) имеют ограниченный баланс, тогда как пара из первого примера не обладает даже свойством единственного продолжения.

Лемма 4.10. Каждая пара (g, h) конечных кодов с ограниченной задержкой в одном и том же направлении обладает свойством единственного продолжения.

Доказательство. Предположим, что g и h имеют ограниченную задержку слева (в случае ограниченной задержки справа доказательство будет аналогичным). Пусть p равно максимуму из двух задержек, а q равно максимуму длин |g(a)| и |h(a)|, где a пробегает алфавиты, на которых определены g и h. (Очевидно, можно считать, что эти алфавиты совпадают.) Выберем теперь k = pq и докажем, что это k удовлетворяет условию в определении свойства единственного продолжения.

В самом деле, пусть (4.19) выполняется для префикса x некоторого слова из E(g,h). Из этого предположения следует, что

Будем считать, что имеет место первое из приведенных выше равенств. Теперь воспользуемся тем обстоятельством, что h имеет задержку p. (При рассмотрении альтернативного равенства аналогичным образом используется то, что g имеет задержку p.) Допустим, что найдутся различные буквы a₁ и a₂, такие, что xa₁ и xa₂ являются префиксами слов из E(g,h). В силу равенства g(x) = h(x) и отсюда вытекает, что существуют такие слова y₁ и y₂, что и является префиксом как h(a₁y₁), так и h(a₂y₂). Так как |u|>pq, то |y₁|≥p и существует префикс y₁' слова y₁ такой, что |y₁'| = p-1 и h (a₁y₁') является префиксом слова u. Значит, h (a₁y₁') является также префиксом слова h(a₂y₂). Поскольку a₁≠a₂, последнее утверждение противоречит тому, что h имеет задержку p слева. ▫

Доказательство теоремы 4.9. Без потери общности предположим, что g и h имеют ограниченную задержку слева и общие входной и выходной алфавиты ∑ и ∑₁. В силу леммы 4.10 пара (g, h) обладает свойством единственного продолжения. Пусть k - соответствующая константа из (4.19).

Теперь можно следующим образом доказать, что некоторый конечный детерминированный автомат представляет язык E(g, h). (Будет установлено только существование такого автомата. В действительности известно, что соответствующее построение нельзя провести эффективно.)

Автомат А имеет "буфер" длины k. Читая входное слово, автомат помнит, какой из двух морфизмов "движется быстрее", а также "обгоняющую" (или выступающую) часть образа, ограниченную длиной буфера. Вход x немедленно отвергается, если для некоторого префикса x₁ слова x ни одно из слов g(x₁) и h(x₁) не является префиксом другого. В случае выхода за границу буфера, т. е. когда один из морфизмов движется настолько быстрее, что выступающая часть его образа длиннее k, воспользуемся свойством единственного продолжения: существует не более одной последовательности букв

ведущей снова k-ограниченному буферу, т. е. к ситуации, в которой выступающая часть образа имеет длину ≤k.

Более формально, у автомата A есть вершина s, одновременно начальная и единственная заключительная, и "мусорная" вершина r, однажды попав в которую автомат никогда не покидает ее. Имеются также вершины, помеченные (w, g) и (w, h), где w - непустое слово над ∑₁ длины ≤k. (Вершина (w, g) содержит информацию о том, что ведущее в нее слово x удовлетворяет условию g(x) = h(x)w.) Кроме того, в автомате A имеется последовательность из t-1 вершин для каждой (из конечного множества) последовательности (4.20).

Укажем наиболее существенные переходы для A. Если g(a) = h(a)w и |w|≤k, то существует помеченная буквой a стрелка, ведущая из вершины s в (w, g). Если h(a) = wg(a), то существует помеченная буквой а стрелка, ведущая из (w, g) в s. Если wg(a) = h(a)w₁ и |w₁|≤k, то найдется помеченная а стрелка, ведущая из (w, g) в (w₁, g). Если h(a) не является префиксом wg(a), то существует помеченная а стрелка, ведущая из (w, g) в r. Если wg(a) = h(a)w₁ и |w₁|> k, то некоторая помеченная буквой a стрелка ведет из (w, g) в первую из вершин последовательности, определенной соответствующей последовательностью букв (4.20). (Заметим, что эта последовательность зависит только от пары (w₁, g), т. е. только от информации о том, какой из морфизмов движется быстрее и какова выступающая часть образа. Мы не можем эффективно указать верхнюю границу длины этой последовательности; в этом и состоит причина неэффективности построения автомата A.)

Для читателя теперь не составит особого труда дополнить определение автомата A и показать, что A представляет язык E(g, h). ▫

Следующая модификация теоремы 4.9 в дальнейших рассмотрениях не потребуется.

▫ Предположим, что g - произвольный морфизм, а h - конечный код с ограниченной задержкой в обоих направлениях. Тогда язык E(g,h) регулярен.

Доказательство. Единственное отличие от предыдущего доказательства состоит в том, что нам надо показать, что пара (g, h) на этот раз также обладает свойством единственного продолжения. В ситуациях, когда g "движется быстрее", т. е. g(x) = h(x)u, мы воспроизводим доказательство леммы 4.10, используя ограниченность задержки морфизма h слева. Рассмотрим ситуацию, когда h движется быстрее, т. е. h(x) = g(x)u, где u - достаточно длинное слово. Пусть хау (где а - некоторая буква) является словом из E(g,h). Тогда g(y) = vh(y), где v - достаточно длинное слово. Отсюда следует единственность а в силу того, что h имеет ограниченную задержку справа. ▫

Теоремы 4.9 и 4.11 нельзя усилить так, чтобы распространить их на тот случай, когда g и h имеют ограниченную задержку в разных направлениях (ср. упр. 9).