Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2007/notes/prr/task-2-sem.pdf Дата изменения: Sat Jul 21 08:36:36 2007 Дата индексирования: Sat Dec 22 19:34:31 2007 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п п п п п п п п

Последовательности, близкие к периодическим. Занятие 2
Определение 1. Блочное произведение двух слов из нулей и единиц зада?тся соотношениями: a 0 = a, a 1 = a (отражение a), a uv = (a u)(a v ). Другими словами, во втором сомножителе заменяем 0 на первый сомножитель, а 1 на его отражение. 2. Ассоциативно ли блочное произведение? Коммутативно ли? 3. Определите бесконечное блочное произведение слов из нулей и единиц, начинающихся с нулей. Докажите, что оно почти периодично. 4. Любая ли почти периодическая последовательность может быть получена как блочное произведение? 5. Найдите 5, 5047 и 4473 символ блочного произведения 01 011 0101 00110 010010 0010001 01101001 000111000. (На все три вопроса можно ответить, пользуясь только ручкой и одним тетрадным листом.) 6. а) Представьте последовательность Туэ-Морса в виде блочного произведения. б) Оцените подсловную сложность последовательности Туэ-Морса. Определение 7. Декартовым произведением двух последовательностей x, y символов конечных алфавитов A, B называется последовательность x Ч y символов алфавита A Ч B , такая что (x Ч y )k = xk Ч yk . 8. а) Докажите, что декартово произведение последовательностей x, y P периодично. б) Докажите, что декартово произведение x P и y AP почти периодично. 9. Пусть x, y AP . а) Может ли быть так, что x Ч y E AP \ AP ? б) Может ли быть так, что x Ч y G AP \ E AP ? в) Может ли быть так, что x Ч y G AP ? / Определение 10. Рассмотрим конечные множества A, B и назов?м их входным и выходным алфавитом, соответственно. Рассмотрим конечное множество Q и назов?м его множеством состояний. Конечным автоматом называется набор из отображений S : QЧA Q, O : Q Ч A B и начального состояния q0 Q. Смысл: сначала автомат находится в состоянии q0 , потом ему на вход подаются по одному символы из входного алфавита, S по старому состоянию и поступившему символу выда?т новое состояние, а O символ, подаваемый на выход. Пример: пусть A = B = Q = {0, 1}, q0 = 0, и пусть S (s, q ) = O(s, q ) = s + q (mod 2). Тогда этот автомат на каждом шаге выда?т на выход сумму всего поданного на вход к этому моменту по модулю два. 11. Постройте конечный автомат, осуществляющий сложение в столбик в двоичной системе счисления на вход подаются пары цифр одна над другой (предполагается, что так подаются складываемые числа, прич?м с конца), а на выход должны выдаваться цифры суммы. Можно ли построить такой автомат для сложения в десятичной системе счисления? А в унарной (число n записывается как слово из n единиц)? 12. Можно ли построить конечный автомат, умножающий числа в двоичной системе счисления, если числа подаются на вход так же, как в предыдущей задаче? 13. Сколько существует различных конечных автоматов с двумя состояниями и двоичными входным и выходным алфавитами? Сколько из них, начиная из первого состояния, хотя бы при одном входе хоть раз выводят 1? Сколько существует различных конечных автоматов с тремя состояниями и двоичными входным и выходным алфавитами? 14. а) Постройте конечный автомат со входным и выходным алфавитом {0, 1}, который выда?т 0 до того момента, пока среди поданных на вход символов не встретится слово из символов 01100, идущих подряд, и выдавать 1 после этого? б) Докажите, что конечный автомат со входным алфавитом {(, )} и выходным алфавитом {0, 1} не может выдавать 1, пока число поданных на вход закрывающих скобок не
1


больше числа открывающих и выдавать всегда 0 после того, как хотя бы один раз число закрывающих скобок превысит число открывающих. 15. Рассмотрим периодическую последовательность с периодом 7 и конечный автомат с 5 состояниями. а) Докажите, что образ последовательности при соответствующем автоматном преобразовании заключительно периодичен. б) Оцените сверху период и предпериод. в) Может ли каждая из этих оценок достигаться? г) Могут ли они достигаться одновременно? д) Какие пары периода и предпериода возможны? 16. а) Докажите, что выход конечного автомата при подаче на вход последовательности из G AP лежит в G AP б) Докажите, что выход конечного автомата при подаче на вход последовательности из E AP лежит в E AP .

2