4.5. Элементарные морфизмы

Морфизм h: ∑^*→∑^*₁ (где ∑ и ∑₁ - алфавиты и не исключено, что ∑ = ∑_{1) называется упрощаемым, если существует алфавит ∑2, в котором число букв меньше, чем в ∑, и морфизмы}

такие, что h равен композиции gf. В противном случае морфизм называется элементарным.

Мы используем элементарные морфизмы в решении проблемы DOL-эквивалентности в гл. 5. Легко видеть, что элементарный морфизм всегда является нестирающим. Композиция двух упрощаемых морфизмов также представляет собой упрощаемый морфизм, тогда как композиция элементарных морфизмов может не быть элементарным морфизмом (см. также упр. 10).

Наиболее существенным средством исследования элементарных морфизмов является следующая теорема.

Теорема 4.12. Каждый элементарный морфизм является кодом с ограниченной задержкой в обоих направлениях.

Доказательство. Назовем морфизм h: ∑^*→∑^*атомарным, если в ∑ существуют разные буквы a и b, такие, что

Если имеет место (4.21), то очевидно, что h является префиксным кодом. Если же выполняется (4.22), то h имеет задержку слева, равную двум. Аналогично рассуждая в случае задержки справа, заключаем, что атомарные морфизмы имеют ограниченную задержку в обоих направлениях.

Пусть теперь морфизм h: ∑^*→∑^*₁ элементарен. Мы утверждаем, что существуют натуральное число t≥0, атомарные морфизмы g_i: ∑^*→∑^* i = 1, ..., t, и бипрефиксный код f: ∑^*→∑^*₁, такие, что

В силу леммы 4.8 из этого утверждения непосредственно следует теорема 4.12.

Утверждение доказывается индукцией по S (h) = ∑_a∈∑|h(a)|. Так как морфизм h представляет собой элементарный и, значит, нестирающий морфизм, то S(h) больше числа букв в ∑ или равняется ему. Если S(h) равняется числу букв в ∑, то сам h является бипрефиксным кодом, и, следовательно, (4.23) выполняется при t = 0. (Очевидно, что из элементарности h следует, что h (a) и h (b) суть различные буквы, если a и b различны.) Таким образом, базис индуктивного предположения очевиден.

В качестве индуктивного предположения примем, что наше утверждение выполняется для всех S(h)≤n. Рассмотрим произвольный элементарный морфизм h: ∑^*→∑^*₁ с S(h) = n+1. Если h - бипрефиксный код, то доказывать нечего, поэтому (без потери общности) предположим, что h не является префиксным кодом. Из этого предположения следует, что существуют различные буквы a и b и слово x, такие, что h(a) = h(b)x.

Рассмотрим атомарный морфизм g: ∑^*→∑^*, заданный равенствами

и морфизм h': ∑^*→∑^*₁, заданный равенствами

(Если h не является суффиксным кодом, то надо использовать атомарный морфизм вида (4.21).)

Ясно, что h = h'g и S(h')≤n. Кроме того, морфизм h' должен быть элементарным, поскольку в противном случае морфизм h был бы упрощаемым. Следовательно, согласно предположению индукции, для h должно иметь место разложение вида (4.23). ▫

Заметим, что в разложении (4.23) морфизм f в действительности также элементарен. Итак, каждый элементарный морфизм можно представить в виде fg, где f - элементарный бипрефиксный код, а g - произведение атомарных морфизмов. Можно показать также, что, обратно, каждая декомпозиция этого вида элементарна.

Как непосредственное следствие теорем 4.9 и 4.12 мы получаем теперь следующий важный результат.

Теорема 4.13. Если g и h - элементарные морфизмы, то язык E (g, h) регулярен.

Если вместо теоремы 4.9 применить теорему 4.11, го по теореме 4.12 получим следующий результат; если один из морфизмов g и h элементарен, то язык E (g,h) регулярен.