Как считать слова?

Дмитрий Пионтковский, Максим Прасолов, Григорий Рыбников

Решения

1 Главная задача

1. См. задачу 24.

2. См. задачи 18 и 48.

3. Один из вариантов решения дан в задаче 46, а другой может быть получен с помощью задач 59 и 61.

4. В задаче 1 алфавит состоит из = 100 слов языка племени, роль слов языка играют фразы языка племени Винни-Пухов, а запретные слова языка — это два магических заклинания. В задаче 2 алфавит состоит из = 256 команд компьютера, а роль слов языка играют программы. Единственное запретное слово — программа, ломающая компьютер.

2 Как записывать ответ?

5. Слово из букв получается выбором на каждом из мест любой из букв. Перемножая количество возможностей на каждом месте, получаем слов.

6. Если в допустимом слове первая буква, то вторая тоже. Аналогично остальные. Значит, допустимое слово имеет вид..., где – одна из букв алфавита. Следовательно допустимых слов из фиксированного количества букв штук.

7. Пусть в допустимом слове первая буква. Так как – запрещённое слово, то вторая буква данного допустимого слова. Продолжаем рассуждения и получаем, что на нечётном месте стоит буква, а на чётном – буква. Если первая буква, то на чётном месте стоит буква, а на нечётном –. Значит, ряд размеров данного языка таков: 1 + 2 + 22 + 23 +...

3 Арифметика языков 8. Набор запретных слов таков: всевозможные слова из двух букв, в которых одна буква из первого алфавита, а другая – из второго, и запретные слова обоих языков. Очевидно, что допустимое слово каждого языка не содержит запретных слов в сумме языков. Если в не содержащем запретное подслово слове суммы языков первая буква принадлежит первому алфавиту, то вторая тоже, и аналогично остальные. Другими словами такое слово состоит из букв одного алфавита. Но тогда оно является допустимым в языке с этим алфавитом, а значит, допустимым в сумме языков.

9. Свободные члены рядов () и 1 () + 2 () 1 равны единице. При > 0 коэффициент при ряда 1 () + 2 () 1 равен сумме количеств слов длины в языках 1 и 2, то есть количеству слов длины в языке, то есть коэффициенту при в ряде ().

10. Имеем (1 )(1 + + 2 + 3 +... ) = 1 + (1 ) · + (1 ) · 2 + (1 ) · 3 + · · · = = 1 + 2 + 2 3 + 3 4 + · · · = 1, что и требовалось.

11. Набор запретных слов таков: все слова из двух букв, в которых первая буква из второго алфавита, а вто­ рая – из первого, и все запретные слова языков произведения. Рассмотрим допустимое слово произведения.

В нём буквы второго алфавита следуют после букв первого алфавита, и это слово не содержит запретных слов языков-множителей. Значит, допустимое слово произведения не содержит указанных запретных слов.

Теперь возьмём слово, не содержащее указанных запретных слов. В нём буквы второго алфавита следуют после букв первого алфавита, поэтому такое слово имеет вид 1 2, где 1 – слово из букв первого алфавита, а 2 – из букв второго. Слово 1 2 не содержит запретных слов языков-множителей, поэтому слова 1 и 2 допустимы в своих языках, то есть слово 1 2 допустимо в произведении языков.

12. Коэффициент при в ряде 1 () · 2 () = 1 () · 0 + 1 () · 1 + · · · = (0 · 0 + 0 1 +... ) + (1 0 + 1 1 2 +... ) +... равен 0 + 1 1 + · · · + 0. Количество слов длины в множестве слов 1 · 2 равно числу способов выбрать пару слов из языка 1 и из языка 2, суммарное количество букв которых равно. Если в слове букв, то в слове букв, а количество таких пар равно ·.

Суммируя такие выражения для всех, получаем 0 + 1 1 + · · · + 0. Поэтому коэффициенты при в рядах 1 () · 2 () и 1 · 2 () совпадают, следовательно сами ряды совпадают.

13.

а) В решении этой задачи нам потребуются тот факт, что стандартные свойства умножения и сложения многочленов (ассоциативность, коммутативность, дистрибутивность) выполняются и для рядов. Рассмотрим, например, ассоциативность умножения — ( · ) · = · ( · ). Чтобы вычислить коэффициент при в левой и правой части, достаточно его вычислить для рядов, у которых отброшены члены более высокой степени, то есть для многочленов. Поэтому указанное тождество для рядов следует из того же тождества для многочленов. Аналогично доказываются остальные свойства.

Заметим теперь, что поскольку ряд начинается с первой степени, в ряд · не входят степени 2 от нулевой до 1-й. Именно поэтому бесконечные суммы вида · + · · +... имеют смысл — для вычисления -го коэффициента можно заменить эту сумму конечной. По той же причине для бесконечных сумм такого вида выполняется свойство дистрибутивности · (1 + 2 + 3 +... ) = · 1 + · 2 + · 3 +....

Имея это в виду, мы легко получаем тождество 2 (1 + )(1 + +... ) = 1.

Отсюда 2 3 2 · = · ( · + · · +... ) = · · (1 + +... ) = б) Согласно утверждению a), Предположим, что ряд ( ) ненулевой. Так как ряд начинается с единицы, то первый ненулевой коэффициент ряда ( ) равен первому ненулевому коэффициенту ряда · ( ). Значит, ряд ( ) нулевой и =.

14.

а) Рассуждая аналогично задаче 10, получаем б) Получаем 15. Следует из задач 59 и 61.

4 Свободное слово 16. Как следует из задачи 17 ниже, получаем () = 126+5. Можно и непосредственно получить эту формулу, проведя рассуждения, аналогичные решению задачи 17.

17. Пусть — число допустимых слов длины. Ясно, что 0 = 1. Докажем, что при > 0 выполнено рекуррентное соотношение = 1 (мы считаем, что = 0 при < 0, так как слов отрицательной длины не существует).

Действительно, приписывая к началу каждого допустимого слова из 1 буквы каждую букву алфавита, мы получаем 1 слов, среди которых все допустимые слова длины. Посмотрим, какие недопустимые слова длины получаются таким образом, то есть имеют вид, где — буква, а — допустимое слово длины 1. Ясно, что запретное подслово должно стоять в начале, то есть =, где — запретное слово, а — допустимое. Из того, что — свободное слово, следует, что для любого допустимого слова слово, получающееся отбрасыванием первой буквы в слове, допустимо (в противном случае имело бы зацепление с самим собой). Поэтому множество всех слов вида, где — буква, а — допустимое слово длины 1, является объединением двух непересекающихся множеств: множества допустимых слов длины и множества слов вида, где — допустимое слово длины. Отсюда следует нужное нам рекуррентное соотношение.

Рассмотрим сумму соотношения 0 = 1 и всех соотношений = 1 для = 1, 2, 3,....

Получится Решая это уравнение относительно (), получаем нужную нам формулу.

18. Согласно задаче 17, Коэффициент при 7 равен 2567 4 · 2563. Поэтому вероятность поломки компьютера равна что примерно равно 1010.

5 Преобразования слов 19. Первая стрелка определена однозначно; вторая сопоставляет каждому слову из то же самое слово, рассматриваемое как элемент ; третья сопоставляет каждому из оставшихся слов его же, как элемент ; последняя стрелка тривиальна, как и первая.

20. Каждый из школьников съедает поровну конфет, бывших у мальчиков, и конфет, бывших у девочек.

Последняя девочка доест все конфеты, бывшие у мальчиков. Поэтому и конфеты, бывшие у девочек, она тоже доест, и учительнице ничего не достанется.

21.

а) Пусть odd = 1 3 5... и even = 2 4 4.... Каждое преобразование устанавливает взаимно-однозначное соответствие между некоторым подмножеством odd и even, причём, поскольку по краям стоят пустые множества, каждый элемент участвует ровно в одном из этих взаимно-однозначных соответствий. Поэтому во множествах odd и even поровну элементов.

б) Для каждого множество слов из длины конечно; применяя к конечным множествам с данным утверждение пункта а), получаем, что коэффициенты при в левой и правой частях доказываемой формулы совпадают. Поскольку — любое, это означает, что формула верна.

22. Проверим, что множество · является объединением двух непересекающихся множеств: множества и множества ·. Доказательство этого опирается на то, что множество — свободное, и почти буквально повторяет соответствующее рассуждение в решении задачи 17.

Теперь точная последовательность строится очевидным образом: первая и последняя стрелки триви­ альны, вторая переводит каждый элемент · в себя (мы пользуемся тем, что · · ), а третья переводит в себя каждый из оставшихся элементов · (мы пользуемся тем, что · · = ). В частности, ядром второго преобразования является пустое множество, а ядром третьего преобразования (и образом второго) — множество · ; образом третьего преобразования является.

23. По задаче 21б), из точной последовательности задачи 22 получаем Заметим, что каждый элемент · записывается в виде, где,, однозначно. Поэтому (·)() = ()(). Далее, каждый элемент · записывается в виде, где,, однозначно (поскольку запрещённое слово не может быть подсловом другого запрещённого слова). Поэтому ( · )() = ()().

Мы имеем () =, () = (), () = () 1 = () 1. Отсюда Решая это уравнение относительно (), получаем требуемую формулу.

24. Обозначим встречающиеся в фразах слова буквами: “земля” — A, “стоять” — B, “на” — C, “великий” — D, “крокодил” — E, “каждый” — F, “вечер” — G, “глотать” — H, “солнце” — I. Тогда заклинаниям отвечают запретные слова “ABCDE” и “FGEHI”. Эти слова свободны (потому что в каждом все буквы различны) и не имеют зацеплений друг с другом (потому что первая и последняя буквы второго слова не встречаются в первом). Следовательно, множество заклинаний свободно, и ряд размеров языка имеет вид Из этой формулы легко вывести (обращая рассуждения в решении задачи 17), что числа (количество фраз из слов) можно вычислить из начального условия 0 = 1 и рекуррентного соотношения = 1001 25.

Вычисления приводят к ответу 20 = 1040 32 · 1030 + 264 · 1020 448 · 1010 + 16.

25. В каждом запретном слове буква встречается только на первом месте и все слова имеют длину 4, поэтому множество запретных слов свободно. По задаче 23, мы имеем 26. Если множество запретных слов свободно, то, в частности, нет простых сцепок. Докажем обратное:

если нет простых сцепок, то множество запретных слов свободно. Предположим противное: пусть множество запретных слов свободным не является. Тогда найдётся зацепление двух запретных слов, то есть найдутся такие три непустых слова,,, что слова и — запретные. Выберем такую тройку (,, ) так, чтобы она имела минимально возможную суммарную длину. Если это не простая сцепка, то содержит запретное подслово, отличное от и. Заметим, что конец не совпадает с концом, поскольку иначе либо является подсловом, либо является подсловом, что невозможно, так как никакое запретное слово не содержит другое запретное в качестве подслова. Аналогично, начало не совпадает с началом. Из тех же соображений, подслово имеет общую часть как с подсловом, так и с подсловом. Обозначим через общую часть подслов и, через — остаток подслова, а через — остаток подслова. Эти слова непусты, их суммарная длина меньше суммарной длины слов,,, а слова = и = — запретные.

Получено противоречие. Таким образом, из отсутствия простых сцепок следует, что множество запретных слов — свободное.

27. Будем строить преобразования последовательно, начиная с конца (с самой правой стрелки). Так как последнее множество пусто, то и область определения последнего преобразования — пустое множество. По­ этому предпоследнее преобразование имеет образом всё множество. Так как ·, мы можем взять в качестве области определения предпоследнего преобразования и считать, что каждый элемент пере­ водится этим преобразованием в себя. Ядро этого преобразования состоит из не являющихся допустимыми слов вида, где — буква и слово является допустимым. Ясно, что для любого такого слова найдутся запретное слово и допустимое слово такие, что = (мы уже использовали это соображение при ре­ шении задач 17 и 22). Это позволяет построить третью с конца стрелку (это преобразование также переводит каждый элемент своей области определения в себя). Рассмотрим ядро этого преобразования. Оно состоит из тех слов вида, где — запретное, а — допустимое, которые имеют вид, где — буква, а слово допустимым не является. Выберем в самое первое (начинающееся левее всех) запретное подслово. Легко видеть, что подслово слова = имеет общую часть с подсловом и образует вместе с ним простую сцепку. Таким образом, ядро третьей с конца стрелки целиком содержится в ·, что позволяет построить преобразование · = · (также переводящее каждый элемент своей области определения в себя).

28. Из решения предыдущей задачи получаем, что язык является незапутанным тогда и только тогда, когда допустимы все слова вида, где — хвост простой сцепки, а — допустимое слово. Эквивалентное условие на множество запретных слов звучит так: не существует таких слов,,,,, где слова,,, непусты, слова,, — запретные, причём — простая сцепка.

Заметим, что любой элемент множества · однозначно представляется в виде произведения простой сцепки на допустимое слово (это легко следует из определения простой сцепки и того, что никакое запретное слово не является подсловом другого запретного слова). Аналогично решению задачи 23, для незапутанного языка из точной последовательности мы получаем уравнение откуда и получается искомая формула 29. Простые сцепки имеют вид,, их хвосты —,. Видно, что ни один из этих хвостов не окан­ чивается на непустое начало запретного слова. Поэтому язык является незапутанным. Соответственно, ряд размеров имеет вид 30. Простые сцепки имеют вид, где 1,,, их хвосты. Так как ни одно запретное слово не начинается на, язык является незапутанным. Соответственно, ряд размеров имеет вид 31. Пусть — единственное запретное слово, и пусть — его длина. Предположим, что оно не является свободным, и, = =, — простая сцепка. Мы имеем = =. Следовательно, конечный участок длины у каждого из слов =, = =, = =,... равен. Возьмём из этих слов первое, имеющее длину не меньше 2. Мы получим, что слово вида... имеет конечный участок, равный. Но тогда у слова есть непустое окончание, являющееся началом слова. Следовательно наш язык не является незапутанным (см. решение задачи 28).

6 Ещё о свободных множествах 32. Например, если алфавит состоит из букв и, то свободным будет множество слов вида, где 2. Докажем это. Очевидно, что никакие два разных слова такого вида не являются подсловами друг друга. Осталось доказать, что между ними нет нетривиальных зацеплений (т.е. что любое зацепление есть просто зацепление слова с самим собой по всей длине). Действительно, если — зацепление слов и, то легко видеть, что содержит не менее трёх букв. Как конец слова, оно имеет вид либо, либо, где 1. Поскольку оно также должно быть началом слова, получаем, что 33. Лемма. Если () = 1 + 1 + — многочлен с единичным свободным членом степени 1, то ряд () = 1/() не может быть многочленом (т.е. этот ряд содержит бесконечное множество ненулевых членов).

Доказательство леммы. Предположим, от противного, что ряд () — многочлен, т.е. () = 0 + 1 +..., где старший коэффициент ненулевой. Согласно задаче 13 a), получаем 1 = ()() = 1+(0 1 + 1 0 ) + · · · + + — противоречие.

Перейдём к решению задачи. Согласно задаче 23, имеем Если бы язык был конечным, то ряд () был бы многочленом, что невозможно согласно доказанной лемме. Следовательно, множество допустимых слов языка бесконечно.

34. Очевидно, для любых рядов неравенство равносильно неравенству 0, т.е. условию, что коэффициенты ряда неотрицательны. Обозначим ряд через = 0 + 1 + 2 2..., а ряд как = 0 + 1 + 2 2... Тогда произвольный -й коэффициент ряда, вычисляемый по формуле 0 + 1 1 + · · · + 0, представим в виде суммы неотрицательных числе, и потому сам неотрицательный.

Это означает, что выполняется неравенство 0, равносильное неравенству 0, или.

35. По формуле из задачи 23, Согласно задаче 27, существует точная последовательность где — ядро отображения · = ·, а — множество допустимых слов языка. Из этой последо­ вательности получаем (зад. 21) равенство откуда (т.к. () = (), () = () и () 0) Умножая это неравенство на ряд () 0, получаем (ввиду зад. 33) т. е.

36. Пусть алфавит = {, }. Обозначим второе слово через. Очевидно, чтобы слова и не были сво­ бодными, необходимо, чтобы их начальные и конечные буквы были различные. Если при этом начинается на одну букву, а — на другую, то последняя буква слова совпадает с первой буквой слова, и эти слова зацепляются, так что множество не будет свободным. Итак, осталось рассмотреть случай, когда оба слова и начинаются на одну букву (скажем, ), а заканчиваются на другую ().

а) Имеем = и =.... Очевидно, если первая буква в слове находится на -м месте, то его подслово из букв на ( 1)-м и -м местах равно, так что множество не свободно.

b) Ответ: нет. Пусть = (случай = аналогичен, с точностью до левой-правой симметрии и замены букв). Поскольку слово не является подсловом в, то в слове за парой букв всегда следует ещё одна. Так как слова и не зацепляются, то не может начинаться на, т. е. оно начинается на.

Следовательно, третья буква в снова, затем четвёртая и т. д., откуда =... — противоречие.

37. Достаточно показать, что существует свободное множество из = 2 /4 двухбуквенных слов. Пусть Тогда в случае четного = 2 множество насчитывает 2 = 2 /4 элементов, а в случае нечётного = 2+ оно содержит ( + 1) = ( 1)( + 1)/4 = 2 /4 1/4 = 2 /4 элементов, что и требовалось.

38. Достаточно показать, что существует свободное множество из (1)1 слов длины. Разобьём основной алфавит = {1,..., } на два подмножества = {1,..., } и = {+1,..., }. Тогда легко видеть, что множество = {|, — слово длины 1} — искомое.

39.

а) Согласно задаче 23, 1+() = () 1.

б) Ответ: неверно. Например, в случае двухбуквенного алфавита такого множества не существует при () = 3 + 10 (это доказано в задаче 36 b). Осталось убедиться, что ряд имеет неотрицательные коэффициенты (поскольку свободный член этого ряда единичный, это условие рав­ носильно требуемому неравенству () 1). Оказывается, для этих коэффициентов справедливо даже более сильное неравенство (3/2). Доказательство последнего неравенства можно провести по индукции, воспользовавшись рекуррентным соотношением +10 = 2+9 +7, которое следует из равенства Другой подобный пример — случай () = 46, снова над алфавитом из двух букв.

40. Решение содержится в теореме 5.1 (эквивалентность AB) и предложении 5.6 в статье: David Anick, Generic algebras and CW–complexes, Proceedings of 1983 Conference on algebra, topology and K–theory in honor of John Moore. Princeton University, 1988, p. 247–331.

41. Вопрос остаётся открытым.

7 Слова и цепи 42. Слово “of” не участвует в построении цепей длины больше 1, потому что данные слова не начинаются на букву f и не заканчиваются на букву o. Буквы нет в слове tournament, поэтому цепь может содержать слово towns только в конце. Буква t в слове tournament стоит лишь на первом и последних местах, поэтому это слово может зацепляться с собой только по одной букве. Исходя из сказанного, мы находим все цепи:

tournament, of, towns; tournamentournament, tournamentowns;... Цепей длины больше 1 будет ровно две.

43. Рассмотрим цепь длины. От его правого конца можно строить антицепь по направлению к левому концу единственным образом. Будем присоединять звенья слева по очереди. Докажем по индукции, что начало -го звена антицепи лежит между началом -го справа звена цепи и концом +1-го справа звена цепи. Для = 1 утверждение верно, потому что в этом случае соответствующие звенья цепи и антицепи совпадают. Проверим базу также для = 2. Второе звено антицепи лежит правее второго справа звена цепи, потому что между первым и вторым звеном нет запретных слов. Начало второго звена антицепи лежит левее конца третьего справа звена цепи, потому что правее третьего справа конца звена цепи нет запретных слов по определению цепи. Таким образом для = 2 утверждение верно. Докажем шаг. По предположению индукции -е справа звено цепи пересекает 1-е звено антицепи, но (+1)-е звено антицепи не пересекает (1)-го звена антицепи, поэтому (+1)-е звено антицепи левее -го справа звена цепи. Между концом (+2)-го и началом -го справа звена цепи не начинается никакое запретное слово, поэтому начало (+1)-го звена антицепи левее конца (+2)-го звена цепи. Так как (1)-е звено антицепи не левее 1-го звена цепи, то (+1)-е звено цепи не пересекает (1)-е звено антицепи, но пересекает -е звено, поэтому (+1)-е звено антицепи не левее (+1)-го звена цепи.

44. Пусть цепь – подслово цепи. Докажем по индукции, что -е звено цепи не правее -го звена цепи. База = 1 очевидна. Если первые звенья цепей совпадают, и одна является подсловом другой, то все остальные звенья также совпадают, и, в частности, если такие цепи имеют одинаковую длину, то они сов­ падают. Поэтому цепь начинается не с начала, а поэтому первое звено цепи правее или совпадает со вторым звеном цепи. Если бы второе звено цепи было правее первого звена цепи, то тогда бы первое звено цепи можно было бы выбрать в качестве второго звена цепи. Значит, второе звено цепи левее второго звена цепи, и база индукции верна для = 2. Перейдём к шагу индукции. Если (+1)-е звено цепи не пересекается с -ым звеном цепи, то (+1)-е звено цепи правее (+1)-го звена цепи. Также добавленное звено цепи не пересекается с (1)-м звеном цепи, а значит, по предположению индукции с (1)-м звеном цепи. Поэтому, если +1-е звено цепи пересекает -е звено цепи, то +1-е звено цепи всё равно не правее (+1)-го звена цепи, потому что иначе то звено можно было бы выбрать вместо этого.

Шаг доказан. Значит, последние звенья цепей совпадают, но по прошлой задаче данная пара цепей является также парой антицепей одинаковой длины с совпадающими первыми звеньями, откуда они совпадают.

45. Пусть слово представлено в виде, где – допустимое слово, а – цепь длины не менее двух. По задаче 43 цепь также является антицепью. Если при убирании первого звена цепи появляется запретное слово, не зацепленное с укороченной цепью, то антицепь можно продолжить влево и получить новое представление, где длина цепи увеличилась. Если такого запретного слова не появилось, то антицепь можно укоротить на самое левое звено и получить новое представление, в котором длина цепи уменьшилась. Если есть ещё одно представление, то заметим, что дуги антицепей,, совпадают, а значит, длина каких-то двух цепей отличается минимум на два, но тогда допустимое слово перед короткой антицепью содержит самое левое звено более длинной антицепи, противоречие.

46. Для решения этой задачи мы применим задачу 21 для точной последовательности Построим эту последовательность. Возьмём слово из ·. Хвост цепи припишем в начало слова и получим. Если допустимое слово, то слово принадлежит 1 ·. Если слово содержит запретное слово, то цепь можно продолжить вправо до цепи, остаток обозначим. Тогда слово принадлежит +1 ·. Цепь можно единственным образом продолжать внутри слова, поэтому построенные отображения взаимно-однозначны на частях языков ·.

Стрелки 1 · = · = = мы берём из задачи 27. По задаче Откуда получаем требуемое.

47. По задаче 42 1 () = 2 + 5 + 10, () = 9(1) (5 + 10 ). По формуле из задачи 48. Рассмотрим четыре варианта запретного слова из четырёх букв с точностью до замены букв.

1) Запретное слово имеет вид aaaa. В этом случае 2 = 4+1, 21 = 4. По формуле задачи Коэффициент при 7 равен 2567 3 · 2562 · 255 2563 = 2567 4 · 2563 + 3 · 2562.

2) Запретное слово имеет вид abca и хотя бы две различные буквы. В этом случае = 3+1.

Коэффициент при 7 равен 2567 4 · 2563 + 3) Запретное слово имеет вид abab. В этом случае = 2(+1).

Коэффициент при 7 равен 2567 4 · 2563 + 2 · 4) Запретное слово свободно. А случай свободного запретного слова разобран в задаче 18.

49. Из задачи 46 следует, что (Бесконечная сумма имеет смысл, поскольку степени начальных членов слагаемых растут.) В левой части равенства стоит ряд размеров множества недопустимых слов. В правой части равенства стоит знакоперемен­ ная сумма рядов размеров множеств · ·. Определено отображение для каждого из этих языков в множество недопустимых слов, и наоборот, каждое недопустимое слово можно представить в виде 1, где – допустимое, 1 – запретное слово. Но недопустимое слово может быть представлено в виде, где – допустимое, а – цепь длины, несколькими способами. Пусть для слова число таких способов равно.

Тогда сумма чисел (1 2 + 3 4 +... ) по всем словам длины равна коэффициенту при в правой части равенства выше, а значит, и в левой, что равно количество недопустимых слов длины.

Заметим, что из представления слова в виде можно получить другое представление с длиной цепи на единицу меньше, отбросив хвост цепи в остаток. Поэтому два таких варианта сократятся в сумме (1 2 + 3 4 +... ). Другими словами рассматриваемая сумма равна числу представлений слова в виде, где подслово – это максимальная подцепь слова, причём цепь имеет нечётную длину.

Рассмотрим представление слова в виде, где – максимальная цепь с самым правым последним звеном. По задаче 45 либо в слове есть максимальная цепь длины 1, либо оно представимо в виде, где – допустимо, а – цепь, которая либо длиннее, либо короче цепи на одно звено. Заметим, что – также максимальная подцепь слова. Одна из цепей и имеет нечётную длину. Тем самым мы показали, что сумма (1 2 + 3 4 +... ) не меньше единицы. Но сумма таких величин по всем недопустимым словам длины равна их количеству. Значит, каждая величина равна единице, и в каждом недопустимом слове максимальных цепей нечётной длины ровно одна.

50. Применим формулу задачи 46.

51. Применим формулу задачи 46.

52. Допустимые слова языка – это цепи языка. Цепи длины этих языков состоят из +1-й буквы, 8 Дополнительные задачи 53. Существование свободного множества при условии (1)1 доказано в задачах 37 и 38. Осталось доказать, что при > ( 1)1 искомого свободного множества не существует.

a) Если задано > 2 /4 слов из двух букв, то они могут составлять свободное множество лишь при условии, что первая буква никакого слова не совпадает со второй буквой никакого другого слова, т.е. есть два непересекающихся множества букв, и, элементы которых могут служить, соответственно, только начальными или только вторыми буквами слова из. Обозначим = | | + || и = | | · || || = > 2 /4. По теореме Виета, натуральные числа | | и || являются корнями квадратного уравнения 2 + = 0, дискриминант которого = 2 4 отрицателен при выполнении указанных ограничений на и — противоречие.

б) Пусть — свободное множество слов длины 3. Поскольку в свободном множестве никакая первая буква слова не может быть также и последней буквой какого-либо слова, в алфавите есть два непересека­ ющихся подмножества и, элементы которых встречаются, соответственно, только в начале и только в конце слов из. Если есть буквы, которые не встречаются ни в конце, ни в начале слова, присоединим их произвольным образом к одному из множеств и. Пусть, для определённости, число элементов множе­ ства = {1,..., } не превосходит количество элементов множества = {1,..., }. Каждый элемент множества имеет вид 1 2 1 или 1 1 2, причём никакое финальное подслово вида элемента пер­ вого типа не может быть началом элемента второго типа. Проведём преобразование множества, заменив для каждого финального подслова все слова первого типа, оканчивающиеся на него, на слова второго типа, по правилу, где 1. Легко видеть, что при таком преобразовании никакие элементы не переходят в другие элементы множества и никакие различные элементы не переходят в один и тот же, причём получившееся множество останется свободным. При этом в все элементы имеют вид 1 1 2. Следовательно, количество элементов множества (равное по-прежнему числу ) не превосходит 2, откуда что и требовалось.

в) Для доказательства потребуется следующая аналитическая Лемма. Пусть () = 1+1 +2 2 +... — ряд с натуральными коэффициентами такой, что () = 1/() для некоторого многочлена () с единичным свободным членом. Обозначим () = 1+1 +2 2 +· · ·+.

Если для всех [0, 0 ], где 0 > 0, выполняется условие () > 0, то для всех > 0 справедливы неравенства (0 ) 1/.

Не доказывая лемму, перейдём к решению задачи. Обозначим = ( 1)(1) ; требуется доказать, что при > 0 свободного множества не существует. Предположим, что это не так. Тогда, согласно задаче 39 a), ряд 1/(), где () = 1 +, имеет натуральные коэффициенты (нулевых коэффициентов быть не может, поскольку этот ряд бесконечен согласно задаче 33). Отметим, что при > 0 многочлен () положителен на отрезке [0, 1] (доказательство: минимум этого многочлена на отрезке [0, 1] достигается либо в концах отрезка, где () положителен, либо в такой точке 0, в которой (0 ) = 0, т. е. при 0 = (1) ;

при этом (0 ) = 0 > 0). Это означает, что существует такое число > 0, что () при [0, 1].

Согласно лемме, это означает, что для всех количество слов длины не выше, равное (1), ограничено константой 1/.

54. a) По определению, запретными словами языка ! являются все двухбуквенные слова, не запретные в. Следовательно, запретными словами языка (! )! будут все двухбуквенные слова, не запретные в !, т. е. в точности запретные слова языка. Таким образом, и алфавиты, и наборы запретных слов языков и (! )!

совпадают, а потому и сами языки равны.

б) Поскольку множество запретных слов языка = (1 + 2 )! есть объединение множеств запретных слов языков ! и !, а алфавит языка представляет собой объединение их (непересекающихся) алфавитов, то язык есть свободное произведение (см. определение в зад. 51) языков ! и !.

в) Запретными словами языка (1 · 2 )! будут разрешённые двухбуквенные слова языков 1 и 2, а также слова вида, где — буква из алфавита языка 1, а — буква из алфавита языка 2. Это означает, что 55. Пусть — слово длины (где 1) над алфавитом языка, () — соответствующее ему слово языка (). Разобьём на подслова = 1..., каждое из которых соответствует букве языка (). Легко видеть, что слово содержит какое-то запретное подслово (состоящее, по определению, из не более чем букв) в том и только том случае, когда в каком-то подслове =... +1 каждое из подслов либо содержится в подслове, либо пересекается с ним, так что количество -буквенных фрагментов в подслове удовлетворяет неравенству, где Таким образом, любое недопустимое слово () языка () содержит недопустимое подслово из не более чем букв, т. е. язык () задаётся конечным множеством запретных слов, причём длины запретных слов этого языка не превосходят. Это доказывает утверждение а).

б) Ответ: не всегда.

Докажем, что при 3 и 2 длины запретных слов языка () всегда меньше ; в частности, этот язык не может быть -определённым, т. е. ответ на вопрос из п. б) отрицательный. Достаточно доказать неравенство <, или Последнее неравенство равносильно неравенству ( 2)(1 1/) > 0, которое, очевидно, верно при заданных ограничениях на и.

в) Ответ: = 1. По доказанному выше, язык () является квадратичным или свободным (т. е. длины запретных слов не превосходят 2) при условии 2, которое равносильно неравенству 2 + 2 < 3, или > 2, т. е. 1. Если же 2, то существуют такие -определённые языки, для которых язык () имеет запретные слова из более чем трёх букв: примером служит язык с трёхбуквенным алфавитом {,, } и единственным запретным словом 2.

56. См. решение задачи 58.

57. Ответ: да. Например, пусть — алфавит из 2 букв. Рассмотрим язык = ·. Поскольку язык имеет экспоненциальный рост (для него в задаче 55 c) можно выбрать 1 = + 1 и 2 = ), причём 2 () () (), то язык также имеет экспоненциальный рост. Согласно задаче 53 в), имеем ! = ( )! · =, так что оба языка и ! имеют экспоненциальный рост.

58. Докажем сначала следующее утверждение (при решении задачи 56 без него можно обойтись).

Лемма. Пусть = {0, 1, 2,... } — последовательность натуральных чисел, в которой 0 = 1 и для некоторого натурального имеем 1 2,..., 2. Тогда последовательность имеет полиномиальный (соответственно, экспоненциальный) рост в том и только том случае, когда соответствующие неравенства из утверждений b) и с) выполняются для всех при.

Доказательство леммы. Пусть = max{ }. Очевидно, если для некоторых многочленов, степени выполняются неравенства () () при, то выполняются также и неравенства () + () при всех, что доказывает лемму в случае полиномиального роста. Аналогично, если при, то ( + 1 ) при всех, что полностью доказывает лемму.

Перейдём к решению задачи. Очевидно, все допустимые слова длины 1 получаются, если, начиная со слова в вершине графа, приписывать к нему справа буквы, которые прочитываются при прохождении какого-либо маршрута, начинающегося в этой вершине, причём разные слова соответствуют разным марш­ рутам. Очевидно, язык конечен тогда и только тогда, когда никакой маршрут не возвращается в начальную вершину, т.е. в графе нет циклов (что доказывает утверждение а)). Осталось рассмотреть случай, когда язык бесконечен и в графе есть цикл. В этом случае количество слов длины равно числу маршрутов длины + 1.

Предположим, что есть два пересекающихся цикла; пусть их длины суть 1 и 2, и — общая вершина, исходящие из которой ребра различны для обоих циклов (скажем, отвечающие буквам и ). Слова, которые прочитываются на ребрах -звенных маршрутов, начинающихся в и проходящим по каждому из циклов, различны, поэтому 2 при всех 0. Кроме того, для любого = ( 1) + (1 + 2 ) +, где < 1 + — остаток от деления числа + 1 на 1 + 2, существует по крайней мере 2 различных маршрутов длины + 1 (на каждом из шагов проходим оба цикла в произвольном порядке, а затем делаем шагов в произвольном цикле), так что при 2 имеем 2 = 2 1 +2, где = 21/2(1 +2 ). Поскольку всегда, из доказанной леммы (при = 2) следует, что рост экспоненциальный.

Осталось разобрать случай, когда в графе циклы есть, но они не пересекаются между собой. Доста­ точно проверить условия полиномиальности для количеств маршрутов = +1 длины в графе (т.к.

если соответствующие неравенства выполняются для чисел, то они выполняются и для при при замене многочленов () и () на многочлены той же степени 1 () = ( + 1) и 1 () = ( + 1)).

Мы докажем, что каждый член последовательности равен значению некоторого многочлена () с поло­ жительным старшим коэффициентом (будем называть такие последовательности полиномиальными).

Рассмотрим другой граф, вершинами которого служат циклы графа и вершины графа, не вхо­ дящие в циклы (назовём их обособленными), а ребра соответствуют ребрам, соединяющим соответствующие компоненты (вершины или циклы) графа. Очевидно, в графе циклов нет, т.е. множество маршрутов — количество маршрутов длины, которое им соответствует в графе. Поскольку =, достаточно доказать, что последовательность { } для каждой вершины полиномиальна. Воспользуемся индукцией по длине = () максимального маршрута, исходящего из. Если = 0, то либо = 0 при > 0 (если — обособленная вершина), либо = 1 для всех (если — цикл), т. е. соответствующая последователь­ ность всегда полиномиальна. Пусть теперь — какая-то начальная вершина графа, из которой исходят стрелок 1,..., к вершинам 1,..., (возможно, повторяющимся). По индукции, считаем () — многочлен с положительным старшим коэффициентом. Если — обособленная вершина, то = =1 1, т.е. эта последовательность полиномиальна как сумма полиномиальных последовательностей. Если же — цикл, то перед переходом к вершинам по ребрам 1,..., возможно слово любой длины в цикле, поэтому фициентами. Утверждение доказано.

Примечание. Аналогичным образом можно определить тип роста любого регулярного множества. Для этого используется отвечающий этому множеству конечный автомат.

59. Обозначим множество допустимых слов через. Пусть язык является -определённым. Докажем, что каждое слово -эквивалентно слову не более чем из букв.

Действительно, если слово не является допустимым, то какое слово к нему не припиши, результат не будет допустимым. Поэтому все недопустимые слова эквивалентны. В частности, любое из них эквивалентно какому-нибудь запретному слову, то есть слову длины не большей.

Пусть слово допустимо и имеет длину, большую. Обозначим через подслово слова, состоящее из его последних букв. Пусть — произвольное слово. Если слово содержит запретное подслово, то это подслово содержится в, так как длина запретного подслова не больше. Поэтому слова и эквивалентны.

Пусть в алфавите букв. Тогда число слов длины не большей не превосходит ( + 1). Положим = ( + 1) + 1. В любом наборе из слов найдутся два, -эквивалентные одному и тому же слову длины не большей и, тем самым, эквивалентные друг другу. Поэтому множество допустимых слов регулярно.

60. а) Пусть — максимальное множество слов, из которых никакие два не -эквивалентны. Тогда любое другое слово эквивалентно какому-то слову из. Построим конечный автомат. Возьмём в качестве мно­ жества вершин графа. Для всех,, проведём из вершины стрелку, помеченную, в вершину, -эквивалентную. В полученном графе назовём начальной вершиной ту, которая -эквивалентна пу­ стому слову, а принимающими вершинами — все слова из, которые принадлежат. Легко видеть, что построенный конечный автомат принимает те и только те слова, которые принадлежат.

б) Любому слову отвечает путь по стрелкам конечного автомата. Ясно, что если для двух слов такие пути заканчиваются в одной вершине, то слова -эквивалентны, где — множество принимаемых автоматом слов. Поэтому в качестве из определения регулярного множества можно взять число, на единицу большее числа вершин в автомате.

61. Рассмотрим конечный автомат (, 0, ), принимающий множество. Для каждой вершины этого конечного автомата обозначим через множество слов, для которых соответствующие пути по графу заканчиваются в.

Далее, для каждой вершины и каждой буквы обозначим через (, ) множество таких вершин графа, что из в идёт стрелка, помеченная. Тогда выполнены следующие равенства:

Перенумеруем вершины графа, начиная с 0 : = {0, 1, 2..., }. Заметим, что каждое из равенств (1), (2) можно воспринимать как уравнение вида где (), (), () — некоторые известные многочлены, относительно неизвестных рядов 0 (),..., ().

Попробуем решить уравнения (3). Выразим из последнего уравнения () через остальные неизвестные ряды, подставим это выражение вместо () в остальные уравнения, и домножим их все на (1 + ()). Мы по­ лучим уравнения того же вида, но число их (как и число неизвестных) станет на единицу меньше. Проделав то же самое для 1 (), 2 (), и т. д., мы получим в конце концов выражение для 0 () в виде отно­ шения двух многочленов. Подставив его в выражение для 1 (), получаем, что и этот ряд есть отношение двух многочленов. Продолжая этот процесс, получаем выражения того же вида для всех (). Осталось заметить, что () = ().

62. Для каждого слова обозначим через слово, состоящее из тех же букв в противоположном порядке.

Для каждого множества слов положим = { | }. Ясно, что () = () для любого.

Если — язык с множеством запретных слов, то через мы обозначаем язык с множеством запретных слов.

Вернёмся к задаче. Очевидно, что — это множество допустимых слов языка, начинающихся с подслова, равного. Это множество регулярно (доказательство аналогично решению задачи 59). Поэтому ряд () = () равен отношению двух многочленов.

На самом деле, множество тоже регулярно, но доказательство этого заняло бы больше места.