4.3. Коды с ограниченной задержкой

Среди отдельных исследованных в литературе классов кодов коды с ограниченной задержкой привлекают интерес в связи с многими проблемами теории языков, в частности с проблемой DOL-эквивалентности, которая будет рассматриваться в следующей главе. Прежде чем дать определение, рассмотрим в качестве примера код C = {a, ab, bb}. Пусть нам надо декодировать слово вида abⁱ, читая слово слева направо. Тогда, прежде чем начать декодирование, надо прочесть все слово целиком, так как первый декодируемый символ зависит от четности числа символов b. Подобная ситуация невозможна, если данный код имеет ограниченную задержку при чтении слева направо: в этом случае всегда достаточно заглянуть вперед на некоторое фиксированное число символов. Экстремальным примером могут служить коды, подобные C₁ = {aa, ab, ba}, где для декодирования вовсе не требуется заглядывать вперед. Так обстоит дело и для кода C, если слова декодировать справа налево!

Определение. Код C имеет задержку p≥1 слева если из того, что

где x_v суть слова из C, следует, что x_i1 = x_j1. Задержка справа определяется аналогично при помощи суффиксов. Код имеет ограниченную задержку слева (соответственно справа или в обоих направлениях), если существует такое p, что C имеет задержку p слева (соответственно справа или в обоих направлениях).

Таким образом, в рассмотренных выше примерах оба кода C и C₁ имеют задержку 1 справа (коды с таким свойством называются суффиксными), а C₁ имеет также задержку 1 слева (коды с этим свойством называются префиксными). Код C не является кодом с ограниченной задержкой слева.

Код с задержкой p имеет также задержку p₁ для любого p₁≥p. Заметим также, что условие, определяющее понятие задержки, выполняется только для кодов. Поэтому мы могли бы дать следующее эквивалентное определение: "Язык C есть код с задержкой p ...".

Очевидно, код C является префиксным (соответственно суффиксным) кодом тогда и только тогда, когда не существует таких непустых слов x и y, что оба слова x и xy (соответственно x и yx) принадлежат C. Коды, одновременно являющиеся и префиксными, и суффиксными, называются бипрефиксными кодами.

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

Лемма 4.7. Код C над алфавитом ∑ имеет задержку p слева тогда и только тогда, когда для всех x∈C^*, y∈C^p-1 и w∈C^*

Доказательство. Предположим, что C имеет задержку p слева, и рассмотрим слово xyw∈C^* из (4.15). Если γ= λ, то (4.15) верно; в противном случае можно записать

xy = x_i1 ,.. x_iq, q≥p, xyw = x_j1 ... x_jn.

Так как xy является префиксом слова xyw, то x_i1 = x_j1. Следовательно, если удалить из xyw префикс x_i1, то образовавшееся слово также будет принадлежать C^*. Повторяя операцию удаления префиксов, мы придем к тому, что yw∈C^*. Обратно, предположим, что (4.15) имеет место и что (4.14) выполняется для некоторых x_v из C. Тогда для некоторого w∈∑^*

Полагая в (4.15) x = x_i1 и y = x_i2 ... x_ip, заключаем, что слово, получающееся из x_j1 ... x_jn удалением префикса x_i1, принадлежит C^*, т. е.

x_j1 ... x_jn = x_i1y₁, где y₁ ∈C^*.

Так как C является кодом, то x_j1 = x_i1, откуда видно, что C имеет задержку p слева. ▫

Введем теперь понятие композиции двух кодов. Для этого будет полезно отождествить коды и некоторые морфизмы^*. Будем говорить, что морфизм h: ∑^*₁→∑^* является кодом, если язык {h(a)|a∈∑₁} является кодом. (Здесь ∑ - алфавит, a ∑₁ - алфавит или бесконечное множество символов.) Очевидно, что в этом смысле каждый код можно рассматривать как морфизм, причем как инъективный морфизм (ср. с леммой 4.1). Композиция двух кодов - это просто композиция соответствующих морфизмов (если она существует).

^* (Связь между свойствами кодов и морфизмами DOL-систем исследуется в недавней статье [HW*].- Прим. перев.)

Для того чтобы существовала композиция, число символов в алфавите первого кода должно равняться числу символов в алфавите второго кода. Если это имеет место, то композиция зависит еще от выбора биекции, используемой в том случае, когда коды заданы как языки, а не как морфизмы. Например, код {a, aba, baba, bb, bbba) является композицией двух кодов {a, ba, bb} и {0, 01, 11, 2, 21}, полученной из биекции φ(0) = a, φ(1) = ba, φ(2) = bb.

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

Лемма 4.8. Композиция двух кодов с ограниченной задержкой слева (соответственно справа) является кодом с ограниченной задержкой слева (соответственно справа).

Доказательство. Пусть при i = 1, 2 код C_i имеет задержку p_i слева. Докажем, что композиция C₁ и C₂ имеет задержку p₁ + p₂ - 1.

Предположим, что C_i определяется морфизмом h_i (i = 1, 2) и что

h₁(h₂(au)) является префиксом слова h₁(h²(bv)), (4.16)

где a и b - буквы, а u и v - такие слова, что |u| = (p₁ + p₂ - 1) - 1. Нам надо доказать, что a = b.

Запишем u в виде u = u₂u₁, причем

Представим h₂(au₂) и h₂(u₁) в следующем виде:

где c₁, ..., c_t+t' суть буквы. Согласно (4.17), t'≥p₁-1. (Очевидно, что h₁ и h₂ являются нестирающими морфизмами.) Далее обозначим первые t букв в h₂(bv) через c₁', ..., c_t'. (Согласно (4.16), такие буквы должны существовать.) Достаточно показать, что

Действительно, из (4.18) следует, что h₂(au₂) есть префикс слова h₂(bv), и поэтому a = b, ибо h₂ имеет задержку p₂. Чтобы доказать (4.18), заметим сначала, что в силу (4.16) h₁(c₁, ... c_t+t') является префиксом слова h₁h₂(bv), откуда c₁ =c'₁, поскольку h₁ имеет задержку p₁ и t+t'-1≥t'≥p₁-1. Рассматривая теперь слово c₂ ... c_t+t' и слово, полученное из h₂(bu) удалением первой буквы c₁' = c₁, мы подобным же образом заключаем, что c₂ = c'₂. Эту процедуру можно продолжить, и, поскольку t'≥p₁-1, то c_t = c_t'.

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