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




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

Упражнения

  1. Каково число подслов слова до длины я, не содержащего более одного вхождения каждой буквы? Как можно точнее укажите верхнюю границу для числа подслов в общем случае, когда не все буквы слова до различны.
  2. Рассмотрим DOL-систему G = ({a, b), h, a), где h(a) = b и h(b) = ab. Покажите, что длины слов в последовательности S(G) образуют последовательность Фибоначчи.
  3. Изменив данное в тексте определение, назовем слово или ω-слово сильно бескубным, если оно не содержит подслов вида bx2, где b - последняя буква слова x. Покажите, что при этом теорема 1.9 остается в силе. (Чтобы установить этот результат, нет необходимости просматривать все доказательство теоремы 1.9.)
  4. Назовем примитивным корнем ρ(w) слова w из ∑* кратчайшее слово и, такое, что w = un для некоторого n≥1. Убедитесь в единственности слова ρ(w). Докажите, что "до = дои тогда и только тогда, когда ρ(u) = ρ(w). Сравните этот результат с леммой 1.10.
  5. Докажите, что из равенства umvn = wp, где m, n, p≥2, следует, что ρ(u) = ρ(v) = ρ(w). (Этот результат содержится в [LyS].) Конструкция Туэ применима во многих ситуациях, возникающих в самых разных областях математики; типичный пример - ее использование для доказательства существования непериодических рекуррентных траекторий в динамике (см. [MoH1]). Общим моментом в таких ситуациях, по-видимому, оказывается необходимость создать нечто нерегулярное из нескольких заданных элементов. Дальнейшие примеры будут приведены в упр. 6-8.
  6. Среди обычных правил игры в шахматы есть правила о ничьей, утверждающие, в частности, что каждая игра должна содержать лишь конечное число ходов. Предлагались различные модификации этих правил о ничьей, и одна из них состояла в следующем. Множество пешек и фигур на доске перед ходом образует конфигурацию, причем возможно лишь конечное число различных конфигураций. (Ясно, что конфигурация содержит также информацию о том, чей сейчас ход.) Ничья объявляется в том случае, когда некоторая последовательность конфигураций повторилась два раза подряд. (При этом опускается обычное правило о том, что после некоторого числа ходов должна быть сдвинута пешка или взята фигура.) Покажите, что при таких правилах о ничьей возможна бесконечная игра. Ограничьтесь рассмотрением лишь таких конфигураций, в которых у каждого игрока остался только король.
  7. Элемент z называется нулем полугруппы S, если для каждого элемента а полугруппы S имеет место za = az = z. Полугруппа S называется нильпотентной, если существует такое натуральное k, что Sk = {z}. Постройте порожденную тремя элементами полугруппу S, не являющуюся нильпотентной и такую, что квадрат каждого элемента S равен нулю.
  8. Покажите, что существуют конечно-порожденные бесконечные группы, в которых каждый элемент имеет конечный порядок, являющийся делителем некоторого фиксированного числа n (см. [H]). (Фактически последовательность Туэ используется лишь в одной части доказательства.)1.
  9. Рассмотрим идемпотентную полугруппу (т. е. такую, в которой для каждого элемента а имеет место a2 = a). Докажите, что каждая конечно-порожденная идемпотеитная полугруппа является полугруппой конечного порядка (см. |[Mc]). Сопоставьте этот результат с упр. 7 и 8.
  10. Рассмотрите ω-слово a0a1a2 ... над алфавитом {a, b}, определенное следующим образом: an = a (соответственно an = b), если в двоичной записи числа n имеется четное (соответственно нечетное) число единиц. Докажите, что это ω-слово равно ω-слову из теоремы 1.5.
  11. Рассмотрим "дважды бесконечные" слова
    ...c-2c-1c0c1c2... .
    Приведите пример бесквадратного дважды бесконечного слова над алфавитом {a, b, c) и сильно бескубного дважды бесконечного слова над алфавитом {a, b).
  12. Порождается ли ω-слово у из теоремы 1.8 какой-либо DOL-системой? (Напомним, что у получено применением сохраняющего длину гомоморфизма к ω-слову β, порожденному некоторой DOL-системой. Будем говорить, что ω-слово, построенное таким способом, порождается CDOL-системой.)
  13. Рассмотрим алфавит ∑ = {0, 1, 2} и отображения f1 и f2 алфавита ∑ в ∑3, заданные равенствами
    f1(0) = 012, f1 (1) = 120, f1(2) = 201, f2(0) = 210, f2 (1) = 021, f2(2) = 102.
    Расширим область определения f1 и f2 на ∑*, полагая для всех a из ∑ и w из ∑*
    f1 (λ) = f2(λ) = λ.
    f1 (aw) = f1(a) f2(w), f2 (aw) = f2 (a)f1 (w).
    Покажите, что последовательность {fi1 (0), i = 0, 1, 2, ...} определяет бесквадратное ω-слово. Покажите также, что это ω-слово не порождается никакой CDOL-системой (см. [Be2]).
  14. ω-язык, порождаемый DOL-системой (∑, h, w), состоит из всех ω-слов δ, таких, что δ порождается некоторой DOL-системой
    (∑, hi, hj(w)), i≥1, j≥0.
    Рассмотрим DOL-систему G из упр. 2. Покажите, что, хотя сама G не порождает никакого ω-слова, ω-язык системы G состоит из двух ω-слов, ни одно из которых не является бескубным. Содержат ли эти ω-слова подслова вида x*, где x - непустое слово?
  15. Предположим, что проблема равенства ω-слов, порождаемых двумя заданными DOL-системами, удовлетворяющими дополнительному условию о порождении ω-слов, разрешима. (В действительности эта проблема остается пока открытой2.) Покажите, что при этом предположении проблема равенства ω-языков, порождаемых двумя DOL-системами, также разрешима. (Здесь очень полезен результат, установленный в |Li3], в соответствии с которым проблема пустоты ω-языка, порожденного DOL-системой, разрешима.)
  16. DOL-система G называется локально-катенативной, если ее последовательность
    S(G): w0, w1, w2, ...
    удовлетворяет следующему условию. Существуют положительные целые числа t, i1, ..., it, такие, что равенство
    wn = wn-i1 ... wn-it
    выполняется для всех достаточно больших n. (Например, DOL-система из упр. 2 локально-катенативна, если
    wn = wn-2wn-1.)
    Докажите, что w-язык, порождаемый локально-катенативной DOL-системой, всегда непуст и что проблема равенства со-языков, порождаемых двумя локально-катенативными DOL-системами, разрешима.

1 (Эта задача является знаменитой ("большой") проблемой Бернсайда, решенной П. С. Новиковым и С. И. Адяном (см. послесловие).- Прим. перев.)

2 (Разрешимость этой проблемы и решение задачи 15 указываются в недавно опубликованной статье [CuH*]. (Здесь и далее звездочкой отмечены работы, включенные в составленный при переводе список дополнительной литературы.) В статье [CuS3*] доказывается, что из разрешимости этих проблем следует разрешимость обычной проблемы последовательностной эквивалентности для DOL-систем, а также решается ряд других задач для DOL-систем (см. гл. 5 книги) и для их обобщений DTOL-. систем. - Прим. перев.)

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








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