Упражнения

1. В тексте был приведен пример таких DOL-систем G₁ и G₂ с алфавитом из двух букв, что первые три слова в последовательностях S(G₁) и S(G₂) совпадают, а четвертые слова уже различны. Обобщите этот пример на системы с алфавитами из 2n букв. В этом случае в последовательностях должны совпадать первые 3n слов.
2. Постройте алгоритм, позволяющий выяснять, является ли морфизм g:∑^*→∑^*₁ элементарным. (Прямой метод или непосредственный алгоритм решения этой проблемы состоит в систематической проверке всех алфавитов мощности, меньшей мощности ∑ с перебором для каждого алфавита всех возможных декомпозиций. Попробуйте построить алгоритм, более эффективный, чем описанный выше.)
3. Вычислите верхнюю границу для числа m в лемме 5.4.
4. Докажите существование числа C(G₁, G₂), вычислимого по данным DOL-системам G₁ и G₂ и такого, что G₁ и G₂ последовательностно эквивалентны тогда и только тогда, когда в S(G₁) и S(G₂) совпадают первые C(G₁, G₂) слов. (При желании за деталями можно обратиться к работе [EhR3]. Отметим, что наше доказательство теоремы 5.5, использующее два работающих параллельно полуалгоритма, непосредственно не дает никакого такого числа C(G₁, G₂).)
5. Проведите подробное доказательство теоремы 5.6, опираясь на теорему 5.5. (Сведение языковой эквивалентности к последовательностной эквивалентности и обратное сведение были впервые описаны в [Nie]. Более простое доказательство проведено в [RS].)
6. Предположим, что известен алгоритм, позволяющий устанавливать, порождают ли две данные DOL-системы, удовлетворяющие некоему дополнительному условию для порождения ω-слов, одно и то же ω-слово (см. упр. 1.15). Покажите, как можно применить этот алгоритм к решению проблемы последовательностной эквивалентности для DOL-систем^*.
7. В общем случае разрешимость проблемы включения языков влечет разрешимость проблемы языковой эквивалентности, но не обратно. Покажите, что для DOL-систем разрешима и проблема включения языков (см. [Ru2]).
8. Соображения, приведенные в доказательстве леммы 5.7, могут быть использованы для установления некоторых других результатов о неразрешимости. Действуя в этом направлении, докажите неразрешимость следующих проблем, (i) Регулярен ли данный OL-язык? (ii) Регулярен ли данный контекстно-свободный язык? (iii) Равен ли данный контекстно-свободный язык данному регулярному языку? (iv) Пусто ли дополнение К данному контекстно-свободному языку? (v) Пусто ли пересечение двух данных контекстно свободных языков? (vi) Конечно ли пересечение двух данных контекстно-свободных языков? (vii) Регулярно ли пересечение двух данных контекстно-свободных языков? [См. [G1].- Перев.] (viii) Проблемы (v) - (vii), поставленные для OL-языков.
9. Покажите, что разрешима каждая из следующих проблем, (i) Равен ли данный контекстно-свободный язык данному DOL-языку? (ii) Является ли данный DOL-язык контекстно-свободным? (iii) Является ли данный контекстно-свободный язык DOL-языком? (В связи с проблемами (i) - (iii) см. [Sa4] и [Li2].) (iv) Равен ли данный OL-язык данному DOL-языку? (См. [Rul].) Разрешимость проблемы (iv) означает значительное усиление теоремы 5.6. Проблемы разрешения, в которых сравниваются два класса языков, такие, как (i) и (iv), из этого упражнения и (iii) из упр. 8, часто исследуются для уточнения границы между разрешимым и неразрешимым. Проблемы (ii) и (iii) из этого упражнения и проблемы (i) и (ii) из упр. 8 являются примерами проблем разрешения другого типа: рассматриваются два класса языков, и надо решить, принадлежит ли язык одного класса другому классу.
10. Покажите, что проблема конечности OL-языков разрешима. (Проблемы пустоты и конечности разрешимы и для контекстно-свободных языков. См. [Sa2], где также дан обзор разрешимых и неразрешимых проблем применительно к иерархии Хомского [см. также [G1]. - Перев.].)
11. Докажите, что проблема равенства двух заданных (произвольных) морфизмов g и h на данном контекстно-свободном языке L разрешима (см. [CuS]^**). Докажите, что в этой постановке проблема равенства образов g(L) = h(L) для произвольных g, h и L неразрешима.
12. Пока остается открытым вопрос о разрешимости следующего обобщения проблемы последовательностной эквивалентности для DOL-систем. Даны два набора морфизмов (g₁, ..., g_n) и (h₁, ..., h_n), где каждый морфизм отображает ∑^* в ∑^*, и слово w, принадлежащее ∑^*. Надо выяснить, выполняется ли равенство
    g_i1 ... g_ik(w) = h_i1 ... h_ik(w)
    одновременно для всех последовательностей i₁ ..., i_k чисел из множества (1, ..., n). Докажите, что эта проблема разрешима тогда и только тогда, когда она разрешима в частном случае n = 2.
13. Исследуйте вопрос о разрешимости следующей проблемы. (В то время, когда писались эти строки, он еще оставался открытым.) Рассмотрим OL-систему G = (∑, σ, w). Каждая конечная последовательность слов
    w₀, w₁, ... , w_n, n≥0.
    где w₀ = w и w_i+1 принадлежит σ(w_i) для 0≤i≤n-1, называется историей развития, соответствующей G. Обозначим через DH(G) множество всех историй развития, соответствующих G. Построить алгоритм, выясняющий, верно ли, что DH(G₁) = DH(G₂) для заданных OL-систем G₁ и G₂.

^* (См. примечание на с. 23, а также статью [MaY*].- Прим. перев.)

^** (См. также послесловие.- Прим. перев.)

Замечание переводчика. Интересное обобщение леммы 5.1 на регулярные ω-языки получено в статье [CuP*]. Проблема равенства преобразований вида h₁^-1h₂ (здесь h₁ и h₂ - морфизмы) на регулярных языках также разрешима, тогда как аналогичная проблема для преобразований вида h₂h₁^-1 неразрешима; см. [KaK*].