Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2007/notes/prr/task-4-sem.pdf
Дата изменения: Tue Jul 24 14:57:12 2007
Дата индексирования: Sat Dec 22 19:35:24 2007
Кодировка: koi8-r
Определение 1. Пусть p | это разреженное слово в конечном алфавите A, то есть слово из букв алфавита A, в котором на некоторых местах разрешены пропуски, о бозначаемые . Примеры: ab a , a b, a . По разреженному слову u можно построить последовательность следующим о бразом: запишем периодически слово u: uuuu : : : . В оставшиеся пропуски (то есть в последовательность, о бразованную значками ) мы опять впишем последовательность uuuu : : : , после чего с оставшимися пропусками сделаем то же самое, и так далее до бесконечности. Полученное бесконечное слово называется словом Тёплица и о бозначается Tu . Например, последовательность Ta b строится следующим о бразом: сначала записываем a ba ba ba ba ba ba ba ba b : : : , после следующего шага aaba babbaaba babbaaba babb : : : , потом aabaababbaaba babbaababbabb : : : , и так далее. Другие примеры: Ta = aaaaaaaa · · · = a , Tab a = abaababaaaabbaaabbaaabaaaabaababbaaabaaaabbababaaa : : : 2. Докажите, что слово Тёплица всегда почти периодично. 3. а) Докажите, что если в слове u один пропуск, то Tu чисто морфическая. б) Докажите, что если количество пропусков в слове u делит его длину, то последовательность Tu морфическая. 4 . Найдите подсловную сложность слова Тёплица. (Указание: она зависит только от количества пропусков и длины порождающего слова, если только результат не периодический.) Определение 5. Последовательность называется квазипериодической с квазипериодом u, если её можно целиком покрыть (возможно, перекрывающимися) вхождениями слова u. Пример: последовательность abaabababaabaabaabaabababababa : : : квазипериодична с квазипериодом aba. Последовательность называется сильно квазипериодической, если у неё найдётся бесконечное множество квазипериодов. 6. Докажите, что сильно квазипериодическая последовательность почти периодична. Определение 7. Мы говорим, что частота вхождения символа a в последовательность x |x[0; n - 1]|a = , где x[0; n - 1] | префикс длины n последовательности равна , если limn n x, а |u|a | количество вхождений символа a в слово u. 8. а) Докажите, что в заключительно периодической последовательности существует частота вхождения для любого символа. б) Верно ли, что в каждой почти периодической последовательности существует частота вхождений любого символа? в) Верно ли это для квазипериодических последовательностей? г) А для слов Тёплица? 9. Для каждой пары из следующих классов последовательностей постройте последовательность, принадлежащую одному из них, но не принадлежащую другому (если это возможно): автоматные, морфические, почти периодические, слова Тёплица, квазипериодические последовательности, сильно квазипериодические последовательности. Определение 10. (См. определение 22 из листка 3.) Последовательность Колакоски начинается следующим о бразом: 22112122122112112212112122112112122122112. . . Определяется она следующим о бразом. Рассмотрим прео бразование, которое переводит последовательность a1 a2 a3 : : : из чисел 1 и 2 в последовательность, в которой идёт a1 двоек, a2 единиц, a3 двоек, a4 единиц, и так далее, попеременно. Последовательность Колакоски | это неподвижная точка этого прео бразования.