НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

Упражнения

  1. В тексте был приведен пример таких DOL-систем G1 и G2 с алфавитом из двух букв, что первые три слова в последовательностях S(G1) и S(G2) совпадают, а четвертые слова уже различны. Обобщите этот пример на системы с алфавитами из 2n букв. В этом случае в последовательностях должны совпадать первые 3n слов.
  2. Постройте алгоритм, позволяющий выяснять, является ли морфизм g:∑*→∑*1 элементарным. (Прямой метод или непосредственный алгоритм решения этой проблемы состоит в систематической проверке всех алфавитов мощности, меньшей мощности ∑ с перебором для каждого алфавита всех возможных декомпозиций. Попробуйте построить алгоритм, более эффективный, чем описанный выше.)
  3. Вычислите верхнюю границу для числа m в лемме 5.4.
  4. Докажите существование числа C(G1, G2), вычислимого по данным DOL-системам G1 и G2 и такого, что G1 и G2 последовательностно эквивалентны тогда и только тогда, когда в S(G1) и S(G2) совпадают первые C(G1, G2) слов. (При желании за деталями можно обратиться к работе [EhR3]. Отметим, что наше доказательство теоремы 5.5, использующее два работающих параллельно полуалгоритма, непосредственно не дает никакого такого числа C(G1, G2).)
  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-систем. Даны два набора морфизмов (g1, ..., gn) и (h1, ..., hn), где каждый морфизм отображает ∑* в ∑*, и слово w, принадлежащее ∑*. Надо выяснить, выполняется ли равенство
    gi1 ... gik(w) = hi1 ... hik(w)
    одновременно для всех последовательностей i1 ..., ik чисел из множества (1, ..., n). Докажите, что эта проблема разрешима тогда и только тогда, когда она разрешима в частном случае n = 2.
  13. Исследуйте вопрос о разрешимости следующей проблемы. (В то время, когда писались эти строки, он еще оставался открытым.) Рассмотрим OL-систему G = (∑, σ, w). Каждая конечная последовательность слов
    w0, w1, ... , wn, n≥0.
    где w0 = w и wi+1 принадлежит σ(wi) для 0≤i≤n-1, называется историей развития, соответствующей G. Обозначим через DH(G) множество всех историй развития, соответствующих G. Построить алгоритм, выясняющий, верно ли, что DH(G1) = DH(G2) для заданных OL-систем G1 и G2.

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

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

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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru