Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2007/notes/prr/task-3-sem.pdf Дата изменения: Mon Jul 23 01:25:34 2007 Дата индексирования: Sat Dec 22 19:34:36 2007 Кодировка: koi8-r Поисковые слова: m 65

Определение 1. Пусть дан автомат со входным алфавитом {0; : : : ; k - 1}, в состояниях которого написаны буквы некоторого конечного алфавита A. Последовательность x строится следующим о бразом: автомат получает на вход число n, записанное в системе счисления с основанием k, о бработав которое, останавливается в состоянии q; написанная в нём буква алфавита A | это и есть символ xn последовательности. Последовательности, получаемые таким о бразом, называются k-автоматными. Автоматной называют последовательность, k-автоматную для какого-нибудь k. 2. а) Докажите, что последовательность 1-автоматна тогда и только тогда, когда она заключительно периодична. б) Докажите, что заключительно периодическая последовательность k-автоматна для любого k. 3 . а) Докажите, что если последовательность отличается от автоматной не более чем в конечном количестве символов, то она автоматна. б) Докажите, что после приписывания произвольного количества символов в начало автоматная последовательность остаётся автоматной. в) Докажите, что класс k-автоматных последовательностей замкнут относительно автоматных прео бразований. 4. Докажите, что последовательность Туэ-Морса | автоматная. 5. Докажите, что если x и y являются k-автоматными, то x в y также k-автоматна. Определение 6. Преобразование дракона двоичного слова w с параметром в виде двоичного символа x | это конкатенация слова w, символа x, и слова w, записанного в о братном порядке. Смысл такой: будем сгибать стоящую на ре бре по направлению от нас бумажную полоску при параметре 0 влево, а при параметре 1 вправо. Потом мы все сгибы развернём до прямых углов. При разворачивании полоски на ней будет последовательность сгибов, которая является результатом применения соответствующих прео бразований дракона к пустому слову. 7. а) Докажите, что если применять циклически некоторую последовательность прео бразований дракона, то результат будет автоматной последовательностью. б) Является ли полученная последовательность почти периодической? в) Докажите, что если автоматная последовательность получена из пустого слова последовательностью прео бразований дракона, то эта последовательность прео бразований дракона заключительно периодична. Определение 8. Числа k и l называются мультипликативно независимыми, если ни для каких p и q не верно kp = lq . 9. а) Докажите, что k-автоматная последовательность является kn -автоматной для любого n. б) Докажите, что если последовательность k-автоматна и l-автоматна для мультипликативно независимых k и l, то она заключительно периодична. Определение 10. Морфизм | это такое ото бражение : A B из одного конечного алфавита в другой, для которого выполнено (uv) = (u)(v) для любых слов u; v A . Ясно, что морфизм полностью определяется своими значениями на одно буквенных словах. Морфизм называется нестирающим, если о бразы всех букв непусты. Морфизм k-равномерный, если о бразы всех букв имеют длину k. 1-равномерный морфизм мы называем кодированием. 11. а) Докажите, что периодические последовательности под действием морфизмов переходят в периодические.
1

Последовательности, близкие к периодическим. Занятие 3


б) Докажите, что почти периодические последовательности под действием морфизмов переходят в почти периодические. в) Докажите, что о бо бщённо почти периодические последовательности под действием морфизмов переходят в о бо бщённо почти периодические. г) Как изменяется регулятор при морфизме? 12. Постройте две почти периодические последовательности, ни одну из которых нельзя перевести в другую морфизмом. 13. Постройте две почти периодические последовательности, такие что первую можно перевести морфизмом во вторую, но вторую нельзя перевести морфизмом в первую. Определение 14. Пусть образ морфизма на букве s начинается с s. Тогда в последовательности слов s; (s); 2 (s); 3 (s); : : : каждое следующее слово начинается с предыдущего. Если длины этих слов неограниченно растут, то естественным о бразом можно построить бесконечную последовательность (s) как предел слов n (s) (другими словами, каждое из слов n (s) является префиксом последовательности (s)). Последовательности, которые можно так построить, называются чисто морфическими. Образы чисто морфических последовательностей при кодированиях называются морфическими. 15. а) Докажите, что последовательность Фибоначчи 01001010010010100101001001. . . , являющаяся неподвижной точкой морфизма 0 01, 1 0, почти периодична. б) Докажите, что последовательность Фибоначчи является последовательностью Штурма. в) Является ли она автоматной? 16. Докажите, что последовательность Туэ-Морса чисто морфическая. 17. Докажите, что k-автоматные последовательности | это в точности морфические последовательности, полученные из k-равномерных морфизмов. 18. а) Докажите, что о браз чисто морфической последовательности под действием морфизма морфичен. б) Докажите, что о браз морфической последовательности под действием конечного автомата морфичен. 19. а) Докажите, что подсловная сложность морфической последовательности не больше O(n2 ). Докажите, что подсловная сложно сть чисто морфиче ской по следовательно сти может быть б) одного из следующих пяти типов: O(1), (n), (n log n), (n log log n), (n2 ). в ) Какой может быть подсловная сложность морфической последовательности? г) А если последовательность одновременно чисто морфическая и почти периодическая? Или одновременно морфическая и почти периодическая? 20 . Существует ли алгоритм определения по двум морфическим последовательностям (точнее, по их конечным описаниям) того, являются ли они равными? 21. Для каждой пары из следующих классов последовательностей постройте последовательность, принадлежащую одному из них, но не принадлежащую другому (если это возможно): автоматные, морфические, почти периодические, последовательности Штурма. Определение 22. Последовательность Колакоски начинается следующим о бразом: 2211212212211211221211212211211212212211212212112. . . а) Попытайтесь угадать, как она строится. б) Существует ли для неё предел доли единиц в префиксе при длине префикса, стремящейся 1 к бесконечности? Докажите, что если он существует, то равен 2 . в) Верно ли, что всякое слово, которое в ней встречается, встречается в ней хотя бы ещё раз. г) Докажите, что она не является чисто морфической. д) Является ли она морфической? 2