%\documentstyle{article}
\documentclass{article}
\usepackage[cp1251]{inputenc}
\frenchspacing

% корректная обработка переносов, в том числе при поиске и копировании
\defaulthyphenchar=127
\lccode`\-=`\-
\usepackage{cmap}
\newcommand\softhyphen{\char127\relax}
% также в локальную копию файла t2a.cmap внесено изменение:
%  <7F> <002D>   заменено на   <7F> <00AD>


\usepackage{cmap}
\usepackage{russlh}
\usepackage{mathlh}


\unitlength = 1mm
\textwidth=17.5cm
\textheight=26.5cm
\voffset=-3truecm
\oddsidemargin=-9.6mm

\usepackage{latexsym,amsxtra,amscd,ifthen}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{verbatim}


%\renewcommand{\refname}{Список литературы}
%\renewcommand{\contentsname}{Содержание}

%\theoremstyle{plain}
%\theoremstyle{definition}
%\newtheorem{problem}{Задача}

%\theoremstyle{plain}
%\newtheorem{definition}{Определение}


\newcounter{problem}


%\newtheorem{theorema}{Теорема}
%\def\proof{{\bf Доказательство.}}

\def\d{\displaystyle}
\def\o{\overline}



\begin{document}

\author{Дмитрий~Пионтковский, Максим~Прасолов, Григорий~Рыбников}
\title{Как считать слова?}
\date{}

\maketitle

\centerline{\Large Решения}

\bigskip


\section{Главная задача}

$\phantom{x}$


\bigskip {\bf \noindent 1.} См. задачу 24.

\bigskip {\bf \noindent 2.}
См. задачи 18 и 48.



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

\bigskip {\bf \noindent 4.} В задаче 1 алфавит $A$ состоит из $N=100$ слов языка
племени, роль слов языка $L$ играют фразы языка племени
Винни-Пухов, а запретные слова языка $L$ --- это два магических
заклинания. В задаче~2 алфавит $A$ состоит из $N=256$ команд
компьютера, а роль слов языка $L$ играют программы. Единственное
запретное слово --- программа, ломающая компьютер.






\section{Как записывать ответ?}

$\phantom{x}$

\setcounter{problem}4

%5
{\bf \refstepcounter{problem} \noindent\arabic{problem}.} Слово из
$m$ букв получается выбором на каждом из $m$ мест любой из $N$
букв. Перемножая количество возможностей на каждом месте, получаем
$N^m$ слов.

%6
\bigskip {\bf \refstepcounter{problem}\label{xx...x}
\noindent\arabic{problem}}. Если в допустимом слове первая буква
$x$, то вторая тоже. Аналогично остальные. Значит, допустимое
слово имеет вид $xx\dots x$, где $x$ -- одна из $N$ букв алфавита.
Следовательно допустимых слов из фиксированного количества букв
$N$ штук.

%7
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}.} Пусть в
допустимом слове первая буква $a$. Так как $aa$ -- запрещённое
слово, то вторая буква данного допустимого слова $b$. Продолжаем
рассуждения и получаем, что на нечётном месте стоит буква $a$, а
на чётном -- буква $b$. Если первая буква $b$, то на чётном месте
стоит буква $a$, а на нечётном -- $b$. Значит, ряд размеров
данного языка таков: $1+2x+2x^2+2x^3+\dots$




\section{Арифметика языков}

$\phantom{x}$



%8
{\bf \refstepcounter{problem} \noindent\arabic{problem}.} Набор
запретных слов таков: всевозможные слова из двух букв, в которых
одна буква из первого алфавита, а другая -- из второго, и
запретные слова обоих языков. Очевидно, что допустимое слово
каждого языка не содержит запретных слов в сумме языков. Если в не
содержащем запретное подслово слове суммы языков первая буква
принадлежит первому алфавиту, то вторая тоже, и аналогично
остальные. Другими словами такое слово состоит из букв одного
алфавита. Но тогда оно является допустимым в языке с этим
алфавитом, а значит, допустимым в сумме языков.

\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}.
Свободные члены рядов $L(x)$ и $L_1(x)+L_2(x)-1$ равны единице. При
$n>0$ коэффициент при $x^n$ ряда $L_1(x)+L_2(x)-1$ равен сумме
количеств слов длины $n$ в языках $L_1$ и $L_2$, то есть
количеству слов длины $n$ в языке $L$, то есть коэффициенту при
$x^n$ в ряде $L(x)$.

%10
\bigskip {\bf \refstepcounter{problem}\label{1/(1-x)}
\noindent\arabic{problem}}. Имеем
\begin{multline*}
(1-x)(1+x+x^2+x^3+\dots) = 1-x + (1-x)\cdot x + (1-x)\cdot x^2 +
(1-x)\cdot x^3 + \dots = \\ = 1-x + x-x^2 + x^2-x^3 + x^3-x^4 +
\dots = 1, \end{multline*} что и требовалось.

\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}. Набор
запретных слов таков: все слова из двух букв, в которых первая
буква из второго алфавита, а вторая -- из первого, и все запретные
слова языков произведения. Рассмотрим допустимое слово
произведения. В нём буквы второго алфавита следуют после букв
первого алфавита, и это слово не содержит запретных слов
языков-множителей. Значит, допустимое слово произведения не
содержит указанных запретных слов. Теперь возьмём слово, не
содержащее указанных запретных слов. В нём буквы второго алфавита
следуют после букв первого алфавита, поэтому такое слово имеет вид
$w_1 w_2$, где $w_1$ -- слово из букв первого алфавита, а $w_2$ --
из букв второго. Слово $w_1 w_2$ не содержит запретных слов
языков-множителей, поэтому слова $w_1$ и $w_2$ допустимы в своих
языках, то есть слово $w_1 w_2$ допустимо в произведении языков.

%12
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}.
Коэффициент при $x^k$ в ряде $L_1(x)\cdot L_2(x) = L_1(x)\cdot
n_0+L_1(x)\cdot n_1 x+\dots=(n_0\cdot m_0 +n_0 m_1 x +\dots) +
(n_1 m_0 x+ n_1 m_1 x^2+\dots)+\dots$  равен $n_0 m_k + n_1
m_{k-1}+\dots +n_k m_0.$ Количество слов длины $k$ в множестве
слов $L_1\cdot L_2$ равно числу способов выбрать пару слов $m$ из
языка $L_1$ и $n$ из языка $L_2$, суммарное количество букв
которых равно $k$. Если в слове $m$ $i$ букв, то в слове $n$
$k{-}i$ букв, а количество таких пар равно $m_i\cdot n_{k-i}$.
Суммируя такие выражения для всех $i$, получаем $n_0 m_k + n_1
m_{k-1}+\dots +n_k m_0$. Поэтому коэффициенты при $x^k$ в рядах
$L_1(x)\cdot L_2(x)$ и $L_1\cdot L_2 (x)$ совпадают, следовательно
сами ряды совпадают.


\refstepcounter{problem}
\bigskip  {\bf \noindent 13.}

{\bf \noindent а)} В решении этой задачи нам потребуются тот факт,
что стандартные свойства умножения и сложения многочленов
(ассоциативность, коммутативность, дистрибутивность) выполняются и
для рядов. Рассмотрим, например, ассоциативность умножения ---
$(P\cdot Q)\cdot R=P\cdot(Q\cdot R)$. Чтобы вычислить коэффициент
при~$x^k$ в левой и правой части, достаточно его вычислить для
рядов, у которых отброшены члены более высокой степени, то есть
для многочленов. Поэтому указанное тождество для рядов следует из
того же тождества для многочленов. Аналогично доказываются
остальные свойства.

Заметим теперь, что поскольку ряд $\overline S$ начинается с
первой степени $x$, в ряд $R\cdot\overline S^m$ не входят степени
$x$ от нулевой до $m-1$-й. Именно поэтому бесконечные суммы вида
$R-R\cdot\overline S+R\cdot\overline S^2-R\cdot\overline
S^3+\dots$ имеют смысл --- для вычисления $k$-го коэффициента
можно заменить эту сумму конечной. По той же причине для
бесконечных сумм такого вида выполняется свойство дистрибутивности
$$
R\cdot(S_1+S_2+S_3+\dots)=R\cdot S_1+R\cdot S_2+R\cdot S_3+\dots.
$$

Имея это в виду, мы легко получаем тождество
$$
(1+\overline S)(1-\overline S+\overline S^2-\overline S^3+\dots) =
1.
$$
Отсюда
\begin{multline}\notag
S\cdot \frac RS = S\cdot (R-R\cdot\overline S+R\cdot\overline
S^2-R\cdot\overline S^3+\dots)
 = S\cdot R\cdot(1-\overline S+\overline S^2-\overline S^3+\dots)=\\
=R\cdot (1+\overline S)(1-\overline S+\overline S^2-\overline
S^3+\dots)=R.
\end{multline}

{\bf \noindent б)} Согласно утверждению a),
$$
S\cdot(T-\frac RS)=S\cdot T-S\cdot \frac RS=R-R=0
$$

Предположим, что ряд $(T-\frac RS)$ ненулевой. Так как ряд $S$
начинается с единицы, то первый ненулевой коэффициент ряда
$(T-\frac RS)$ равен первому ненулевому коэффициенту ряда
$S\cdot(T-\frac RS)$. Значит, ряд $(T-\frac RS)$ нулевой и
$T=\frac RS.$


\bigskip {\bf \noindent 14.}%14
{\bf \refstepcounter{problem}} %\noindent\arabic{problem}}.

{\bf \noindent а)} Рассуждая аналогично задаче 10, получаем
$$
   F_A(x) = 1+ Nx + N^2 x^2 +\dots = \frac{ 1}{ 1 - Nx}.
$$



{\bf \noindent б)} Получаем
$$ 1+Nx+Nx^2+Nx^3+\dots=-N+1+N\cdot(1+x+x^2+x^3+\dots)=-N+1+\frac{N}{1-x}=\frac{1+(N-1)x}{1-x} $$
и
$$ 1+2x+2x^2+2x^3+\dots = 1+2x \cdot(1+x+x^2+x^3+\dots) =1+
\frac{2x}{1-x}=\frac{1+x}{1-x}.
$$


\refstepcounter{problem}
\bigskip {\bf \noindent 15.}   Следует из задач 59 и 61.


\section{Свободное слово}


$\phantom{x}$




\bigskip {\bf \noindent 16.} Как следует из задачи 17 ниже, получаем $
   L(x) = \frac{1}{1-26x+ x^5}$. Можно и непосредственно получить
   эту формулу, проведя рассуждения, аналогичные решению
   задачи~17.




\bigskip {\bf \noindent 17.} Пусть $a_k$ --- число допустимых слов длины $k$. Ясно,
что $a_0 = 1$. Докажем, что при $k>0$ выполнено рекуррентное
соотношение $a_k = Na_{k-1} - a_{k-m}$ (мы считаем, что $a_k = 0$
при $k<0$, так как слов отрицательной длины не существует).

Действительно, приписывая к началу каждого допустимого слова из
$k-1$ буквы каждую букву алфавита, мы получаем $Na_{k-1}$ слов,
среди которых все допустимые слова длины $k$. Посмотрим, какие
недопустимые слова длины $k$ получаются таким образом, то есть
имеют вид $cg$, где $c$ --- буква, а $g$ --- допустимое слово
длины $k-1$. Ясно, что запретное подслово должно стоять в начале,
то есть $cg=wf$, где $w$ --- запретное слово, а $f$ ---
допустимое. Из того, что $w$ --- свободное слово, следует, что для
любого допустимого слова $f$ слово, получающееся отбрасыванием
первой буквы в слове $wf$, допустимо (в противном случае $w$ имело
бы зацепление с самим собой). Поэтому множество всех слов вида
$cg$, где $c$ --- буква, а $g$ --- допустимое слово длины $k-1$,
является объединением двух непересекающихся множеств: множества
допустимых слов длины $k$ и множества слов вида $wf$, где $f$ ---
допустимое слово длины $k-m$. Отсюда следует нужное нам
рекуррентное соотношение.

Рассмотрим сумму соотношения $a_0 = 1$ и всех соотношений $a_kx^k
= Na_{k-1}x^k - a_{k-m}x^k$ для $k=1,2,3,\dots$. Получится
$$
L(x) = 1 + NxL(x)-x^mL(x).
$$
Решая это уравнение относительно $L(x)$, получаем нужную нам
формулу.

%18
\bigskip {\bf \noindent 18 }. Согласно задаче 17,
$$L(x)=\frac1{1-256x+x^4} = 1 + (256x-x^4)+(256x-x^4)^2 +
(256x-x^4)^3 + \dots $$
 Коэффициент при $x^7$ равен $256^7-4\cdot
256^3$. Поэтому вероятность поломки компьютера равна $\frac{4\cdot
256^3}{256^7}=4\cdot256^{-4}$, что примерно равно $10^{-10}$.




\section{Преобразования слов}



$\phantom{x}$


\bigskip {\bf \noindent 19.}  Первая стрелка определена однозначно; вторая сопоставляет каждому
слову из $N$ то же самое слово, рассматриваемое как элемент $F_A$;
третья сопоставляет каждому из оставшихся слов $F_A$ его же, как
элемент $G$; последняя стрелка тривиальна, как и первая.


\bigskip {\bf \noindent 20.}  Каждый из школьников съедает поровну конфет, бывших у мальчиков, и
конфет, бывших у девочек. Последняя девочка доест все конфеты,
бывшие у мальчиков. Поэтому и конфеты, бывшие у девочек, она тоже
доест, и учительнице ничего не достанется.

\bigskip {\bf \noindent 21.}

{\bf \noindent а)} Пусть $M_{\mbox{\small odd}} = M_1\cup M_3\cup
M_5\cup\dots$ и $M_{\mbox{\small even}} = M_2\cup M_4\cup
M_4\cup\dots$. Каждое преобразование устанавливает
взаимно-однозначное соответствие между некоторым подмножеством
$M_{\mbox{\small odd}}$ и $M_{\mbox{\small even}}$, причём,
поскольку по краям стоят пустые множества, каждый элемент
участвует ровно в одном из этих взаимно-однозначных соответствий.
Поэтому во множествах $M_{\mbox{\small odd}}$ и $M_{\mbox{\small
even}}$ поровну элементов.

{\bf \noindent б)} Для каждого $k$ множество $M_i^{(k)}$ слов из
$M_i$ длины $k$ конечно; применяя к конечным множествам
$M_i^{(k)}$ с данным $k$ утверждение пункта а), получаем, что
коэффициенты при $x^k$ в левой и правой частях доказываемой
формулы совпадают. Поскольку $k$ --- любое, это означает, что
формула верна.

\bigskip {\bf \noindent 22.}
Проверим, что множество $A \cdot G$ является объединением двух
непересекающихся множеств: множества $\overline G$ и множества
$B\cdot G$. Доказательство этого опирается на то, что множество
$B$ --- свободное, и почти буквально повторяет соответствующее
рассуждение в решении задачи 17.

Теперь точная последовательность строится очевидным образом:
первая и последняя стрелки тривиальны, вторая переводит каждый
элемент $B\cdot G$ в себя (мы пользуемся тем, что $B\cdot
G\subseteq A \cdot G$), а третья переводит в себя каждый из
оставшихся элементов $A\cdot G$ (мы пользуемся тем, что $ A \cdot
G\setminus B\cdot G = \overline G$). В частности, ядром второго
преобразования является пустое множество, а ядром третьего
преобразования (и образом второго)
--- множество $D\cdot G$; образом третьего преобразования является $\overline
G$.

\bigskip {\bf \noindent 23.}
По задаче 21б), из точной последовательности задачи 22 получаем
$$
(B\cdot G)(x)+\overline G(x) = (A\cdot G)(x).
$$
Заметим, что каждый элемент $A\cdot G$ записывается в виде $ag$,
где $a\in A, g\in G$, однозначно. Поэтому $(A\cdot G)(x) =
A(x)G(x)$. Далее, каждый элемент $B\cdot G$ записывается в виде
$bg$, где $b\in B, g\in G$, однозначно (поскольку запрещённое
слово не может быть подсловом другого запрещённого слова). Поэтому
$(B\cdot G)(x) = B(x)G(x)$. Мы имеем $A(x) = Nx$, $G(x) = L(x)$,
$\overline G(x) = G(x) - 1 = L(x) - 1$. Отсюда
$$
B(x)L(x)+ L(x) - 1 = NxL(x).
$$
Решая это уравнение относительно $L(x)$, получаем требуемую
формулу.

\bigskip {\bf \noindent 24.}
Обозначим встречающиеся в фразах слова буквами: ``земля'' --- A, ``стоять'' ---
B, ``на'' --- C, ``великий'' --- D, ``крокодил'' --- E, ``каждый'' --- F,
``вечер'' --- G, ``глотать'' --- H, ``солнце'' --- I. Тогда заклинаниям
отвечают запретные слова ``ABCDE'' и ``FGEHI''. Эти слова свободны (потому что
в каждом все буквы различны) и не имеют зацеплений друг с другом (потому что
первая и последняя буквы второго слова не встречаются в первом). Следовательно,
множество заклинаний свободно, и ряд размеров языка имеет вид
$$
L(x)=\frac{\d 1}{\d 1 - 100 x + 2x^5}.
$$
Из этой формулы легко вывести (обращая рассуждения в решении
задачи 17), что числа $a_k$ (количество фраз из $k$ слов) можно
вычислить из начального условия $a_0=1$ и рекуррентного
соотношения $a_k=100a_{k-1}-2a_{k-5}$. Вычисления приводят к
ответу $a_{20}= 10^{40} - 32\cdot 10^{30} + 264\cdot 10^{20} -
448\cdot 10^{10} + 16$.


\bigskip {\bf \noindent 25.}
В каждом запретном слове буква $v$ встречается только на первом
месте и все слова имеют длину 4, поэтому множество запретных слов
свободно. По задаче 23, мы имеем
$$
L(x) = \frac1{1-26x+3x^4}.
$$


\bigskip {\bf \noindent 26.}
Если множество запретных слов свободно, то, в частности, нет
простых сцепок. Докажем обратное: если нет простых сцепок, то
множество запретных слов свободно. Предположим противное: пусть
множество запретных слов свободным не является. Тогда найдётся
зацепление двух запретных слов, то есть найдутся такие три
непустых слова $s$, $t$, $r$, что слова $st$ и $tr$ --- запретные.
Выберем такую тройку $(s, t, r)$ так, чтобы она имела минимально
возможную суммарную длину. Если это не простая сцепка, то $str$
содержит запретное подслово $w$, отличное от $st$ и $tr$. Заметим,
что конец $w$ не совпадает с концом $tr$, поскольку иначе либо $w$
является подсловом $tr$, либо $tr$ является подсловом $w$, что
невозможно, так как никакое запретное слово не содержит другое
запретное в качестве подслова. Аналогично, начало $w$ не совпадает
с началом $st$. Из тех же соображений, подслово $w$ имеет общую
часть как с подсловом $s$, так и с подсловом $r$. Обозначим через
$t'$ общую часть подслов $st$ и $w$, через $s'$ --- остаток
подслова $st$, а через $r'$ --- остаток подслова $w$. Эти слова
непусты, их суммарная длина меньше суммарной длины слов $s$, $t$,
$r$, а слова $s't'=st$ и $t'r'=w$ --- запретные. Получено
противоречие. Таким образом, из отсутствия простых сцепок следует,
что множество запретных слов --- свободное.

\bigskip {\bf \noindent 27.}
Будем строить преобразования последовательно, начиная с конца (с самой правой
стрелки). Так как последнее множество пусто, то и область определения
последнего преобразования --- пустое множество. Поэтому предпоследнее
преобразование имеет образом всё множество $\overline G$. Так как $\overline
G\subseteq A\cdot G$, мы можем взять $\overline G$ в качестве области
определения предпоследнего преобразования и считать, что каждый элемент
$g\in\overline G$ переводится этим преобразованием в себя. Ядро этого
преобразования состоит из не являющихся допустимыми слов вида $ag$, где $a$ ---
буква и слово $g$ является допустимым. Ясно, что для любого такого слова
найдутся запретное слово $w$ и допустимое слово $f$ такие, что $ag = wf$ (мы
уже использовали это соображение при решении задач 17 и 22). Это позволяет
построить третью с конца стрелку (это преобразование также переводит каждый
элемент своей области определения в себя). Рассмотрим ядро этого
преобразования. Оно состоит из тех слов вида $wf$, где $w$ --- запретное, а $f$
--- допустимое, которые имеют вид $av$, где $a$ --- буква, а слово $v$
допустимым не является. Выберем в $v$ самое первое (начинающееся левее всех)
запретное подслово $u$. Легко видеть, что подслово $u$ слова $av=wf$ имеет
общую часть с подсловом $w$ и образует вместе с ним простую сцепку. Таким
образом, ядро третьей с конца стрелки целиком содержится в $S\cdot G$, что
позволяет построить преобразование $S\cdot G \Longrightarrow B\cdot G$ (также
переводящее каждый элемент своей области определения в себя).


\bigskip {\bf \noindent 28.}
Из решения предыдущей задачи получаем, что язык является
незапутанным тогда и только тогда, когда допустимы все слова вида
$rg$, где $r$ --- хвост простой сцепки, а $g$ --- допустимое
слово. Эквивалентное условие на множество запретных слов звучит
так: не существует таких слов $p,q,r,s,t$, где слова $p,q,s,t$
непусты, слова $pq$, $qrs$, $st$ --- запретные, причём $pqrs$ ---
простая сцепка.

Заметим, что любой элемент множества $S\cdot G$ однозначно
представляется в виде произведения простой сцепки на допустимое
слово (это легко следует из определения простой сцепки и того, что
никакое запретное слово не является подсловом другого запретного
слова). Аналогично решению задачи 23, для незапутанного языка $L$
из точной последовательности мы получаем уравнение
$$
S(x)L(x) + NxL(x) = B(x)L(x) + L(x) - 1,
$$
откуда и получается искомая формула
$$
L(x)=\frac1{1-Nx+B(x)-S(x)}.
$$

\bigskip {\bf \noindent 29.}
Простые сцепки имеют вид $abbc, abbac$, их хвосты --- $c, ac$.
Видно, что ни один из этих хвостов не оканчивается на непустое
начало запретного слова. Поэтому язык является незапутанным.
Соответственно, ряд размеров имеет вид
$$
L(x) =\frac1{1-3x+3x^3-x^4-x^5}.
$$

\bigskip {\bf \noindent 30.}
Простые сцепки имеют вид $x_i y_j z_k$, где $1\le i,j,k \le n$, их
хвосты $z_k$. Так как ни одно запретное слово не начинается на
$z_k$, язык является незапутанным. Соответственно, ряд размеров
имеет вид
$$
L(x) =\frac1{1-3nx+2n^2x^2-n^3x^3}.
$$



\bigskip {\bf \noindent 31.}
Пусть $w$ --- единственное запретное слово, и пусть $L$ --- его
длина. Предположим, что оно не является свободным, и $pqr$,
$pq=qr=w$, --- простая сцепка. Мы имеем $wr=pqr=pw$.
Следовательно, конечный участок длины $L$ у каждого из слов
$wr=pw,wrr=pwr=ppw,wrrr=ppwr=pppw,\dots$ равен $w$. Возьмём из
этих слов первое, имеющее длину не меньше $2L$. Мы получим, что
слово вида $rrr\dots r$ имеет конечный участок, равный $w$. Но
тогда у слова $r$ есть непустое окончание, являющееся началом
слова $w$. Следовательно наш язык не является незапутанным (см.\
решение задачи 28).





\section{Ещё о свободных множествах}

$\phantom{x}$

\bigskip {\bf \noindent 32.}
Например, если алфавит состоит из букв $a$ и $b$, то свободным
будет множество слов вида $a^nb^n ab$, где $n\ge2$. Докажем это.
Очевидно, что никакие два разных слова  такого вида не являются
подсловами друг друга. Осталось доказать, что между ними нет
нетривиальных зацеплений (т.е. что любое зацепление есть просто
зацепление слова с самим собой по всей длине). Действительно, если
$w$ --- зацепление слов $a^nb^n ab$ и $a^mb^m ab$, то легко
видеть, что $w$ содержит не менее трёх букв. Как конец слова
$a^nb^n ab$, оно имеет вид либо $b^k ab$, либо $a^kb^n ab$,
где $1\le k \le n$. Поскольку оно также должно быть началом слова
$a^mb^m ab$, получаем, что  $k = m=n$ и $w = a^nb^n ab=a^mb^m ab$
--- тривиальное зацепление.

\bigskip {\bf \noindent 33.}
{\bf Лемма.} Если $p(x) = 1 + p_1 x + p_n x^n$ --- многочлен с
единичным свободным членом степени $n\ge 1$, то ряд $f(x) =
1/p(x)$ не может быть многочленом (т.е. этот ряд содержит
бесконечное множество ненулевых членов).

{\it Доказательство леммы.} Предположим, от противного, что ряд
$f(x)$ --- многочлен, т.е. $f(x) = f_0 + f_1 x + \dots f_m x^m$,
где старший коэффициент $f_m$ ненулевой. Согласно задаче 13\,a),
получаем $1 = f(x) p(x) = 1+ ( f_0p_1+f_1p_0)x +\dots + f_m p_n
x^{m+n}$ --- противоречие.

Перейдём к решению задачи.  Согласно задаче~23, имеем $$
   L (x) = \frac{\d 1}{\d 1 - N x + B(x)}.
$$
 Если бы язык $L$ был конечным, то ряд $L(x)$ был бы многочленом,
 что невозможно согласно доказанной лемме. Следовательно,
  множество допустимых слов языка бесконечно.

\bigskip {\bf \noindent 34.}
 Очевидно, для любых рядов неравенство $A\ge B$ равносильно
неравенству $A-B\ge 0$, т.е. условию, что коэффициенты ряда $A-B$
неотрицательны . Обозначим ряд $P-Q$ через $A = a_0 + a_1 x+ a_2
x^2 \dots$, а ряд $R$ как $R = r_0 + r_1 x+ r_2 x^2 \dots$ Тогда
произвольный  $n$-й коэффициент ряда $AR$, вычисляемый по формуле
$a_0 r_n + a_1 r_{n-1}+ \dots +a_n r_0$, представим в виде суммы
неотрицательных числе, и потому сам неотрицательный. Это означает,
что выполняется неравенство $AR \ge 0$, равносильное неравенству
$PR -QR\ge 0$, или $PR \ge QR$.




\bigskip {\bf \noindent 35.}
  По формуле из задачи 23, $$
   L (x) = \frac{\d 1}{\d 1 - A(x) + B(x)}.
$$
 Согласно задаче 27, существует точная
последовательность
$$
%\emptyset \Longrightarrow
  \emptyset  \Longrightarrow  K  \Longrightarrow  B'\cdot G' \Longrightarrow A \cdot G'   \Longrightarrow \overline
  G'
  \Longrightarrow \emptyset,
$$
где $K$ --- ядро отображения $B\cdot G \Longrightarrow A \cdot
G'$, а $G'$ --- множество допустимых слов языка $L'$. Из этой
последовательности получаем (зад. 21) равенство
$$
   B'(x) G'(x) - A(x) G'(x) +G'(x) -1 = K(x),
$$
откуда (т.к. $B'(x) = B(x)$,  $L'(x) = G'(x)$ и $K(x) \ge 0$)
$$
        L'(x) (B(x) -A(x) +1) \ge 1.
$$
Умножая это неравенство на ряд $L(x) \ge 0$, получаем (ввиду
зад.~33)
$$
          L'(x) (B(x) -A(x) +1) \cdot \frac{\d 1}{\d 1 - A(x) + B(x)} \ge L(x),
$$
т.~е.
$$
       L'(x)  \ge L(x).
$$





{\bigskip \bf\noindent  36.} Пусть алфавит $A=\{a,b\}$. Обозначим
второе слово через $v$. Очевидно, чтобы слова $v$ и $w$ не были
свободными, необходимо, чтобы их начальные и конечные буквы были
различные. Если при этом $w$ начинается на одну букву, а $v$ ---
на другую, то последняя буква слова $v$ совпадает с первой буквой
слова $w$, и эти слова зацепляются, так что множество $B$ не будет
свободным. Итак, осталось рассмотреть случай, когда оба слова $v$
и $w$ начинаются на одну букву (скажем, $a$), а заканчиваются на
другую ($b$).

а) Имеем  $w = ab$ и $v =a ...b$. Очевидно, если первая буква $b$
в слове $v$ находится на $k$-м месте, то его подслово из букв на
$(k-1)$-м и $k$-м местах равно $w$, так что множество  $B$ не
свободно.

b) Ответ: нет. Пусть $w=aab$ (случай $w=abb$ аналогичен, с точностью до
левой-правой симметрии и замены букв). Поскольку слово $w$ не является
подсловом в $v$, то в слове $v$ за парой букв $aa$ всегда следует ещё одна $a$.
Так как слова $v$ и $w$ не зацепляются, то $v$ не может начинаться на $ab$,
т.~е. оно начинается на $aa$. Следовательно, третья буква в $v$ снова $a$,
затем четвёртая и т.~д., откуда $v = aa\dots a$ --- противоречие.



{\bigskip \bf \noindent 37.} Достаточно показать, что существует
свободное множество $B$ из $g = \left[ n^2/4 \right]$
двухбуквенных слов. Пусть $k=\left[ n/2 \right]$, т.~е. $n=2k$ или
$n=2k+1$. Положим $B=\{x_ix_j|1\le i \le k, k+1 \le  j \le n\}$.
Очевидно, оно свободно. Тогда в случае четного $n=2k$ множество
$B$ насчитывает $k^2 = n^2/4$ элементов, а в случае нечётного
$n=2k+1$ оно содержит $k(k+1) = (n-1)(n+1)/4 = n^2/4 - 1/4 =
\left[ n^2/4 \right]$ элементов, что и требовалось.


{\bigskip \bf \noindent 38.} Достаточно показать, что существует
свободное множество $B$ из $m \le k^d (d-1)^{d-1}$ слов длины $d$.
Разобьём основной алфавит $A = \{x_1, \dots, x_n\}  $ на два
подмножества $P= \{x_1, \dots, x_k\}$  и  $Q= \{x_{k+1}, \dots,
x_n\}$. Тогда легко видеть, что множество $B=\{pq |p \in P, q \in
F_Q \mbox{ --- слово длины } d-1 \}$ --- искомое.


{\bigskip \bf \noindent 39.}

\noindent а) Согласно задаче 23, $\frac{1}{1-nx+B(x)} = L(x)\ge
1.$

\noindent б) Ответ: неверно. Например, в случае двухбуквенного
алфавита $A$ такого множества $B$ не существует при $p(x) =
x^3+x^{10}$ (это доказано в задаче~36\,b).  Осталось убедиться,
что ряд
$$f(x) =
  \frac{1}{1-2x+x^3+x^{10}}
  $$
  имеет неотрицательные коэффициенты
(поскольку свободный член этого ряда единичный, это условие
равносильно требуемому неравенству $f(x) \ge 1$). Оказывается, для
этих коэффициентов справедливо даже более сильное неравенство $a_n
\ge (3/2)^n$. Доказательство последнего неравенства можно провести
по индукции, воспользовавшись рекуррентным соотношением $a_{n+{10}} = 2a_{n+9}
- a_{n+7} - a_n $, которое следует из равенства $(1-2x+x^3+x^{10})f(x)=1$.

 Другой
подобный пример --- случай $p(x) = 4x^6$, снова над алфавитом из
двух букв.

{\bigskip \bf \noindent 40.} Решение содержится в  теореме 5.1
(эквивалентность A$\Longleftrightarrow$B) и предложении 5.6 в
статье: David Anick, {\it 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.


{\bigskip \bf \noindent 41.} Вопрос остаётся открытым.




\section{Слова и цепи}

$\phantom{x}$


%42
\setcounter{problem}{41}

{\bf \refstepcounter{problem} \label{tournament}
\noindent\arabic{problem}}. Слово ``of'' не участвует в построении
цепей длины больше 1, потому что данные слова не начинаются на букву f и не
заканчиваются на букву o. Буквы $s$ нет в слове tournament, поэтому цепь может
содержать слово towns только в конце. Буква t в слове tournament стоит лишь на
первом и последних местах, поэтому это слово может зацепляться с собой только
по одной букве. Исходя из сказанного, мы находим все цепи: tournament, of,
towns; tournamentournament, tournamentowns;... Цепей длины больше 1 будет ровно
две.

\bigskip {\bf \refstepcounter{problem}\label{antichain}
\noindent\arabic{problem}}. Рассмотрим цепь $c$ длины $n$. От его
правого конца можно строить антицепь по направлению к левому концу единственным
образом. Будем присоединять звенья слева по очереди. Докажем по индукции, что
начало $i$-го звена антицепи лежит между началом $i$-го справа звена цепи и
концом $i{+}1$-го справа звена цепи. Для $i=1$ утверждение верно, потому что в
этом случае соответствующие звенья цепи и антицепи совпадают. Проверим базу
также для $i=2$. Второе звено антицепи лежит правее второго справа звена цепи,
потому что между первым и вторым звеном нет запретных слов. Начало второго
звена антицепи лежит левее конца третьего справа звена цепи, потому что правее
третьего справа конца звена цепи нет запретных слов по определению цепи. Таким
образом для $i=2$ утверждение верно. Докажем шаг. По предположению индукции
$i$-е справа звено цепи пересекает $i{-}1$-е звено антицепи, но $(i{+}1)$-е
звено антицепи не пересекает $(i{-}1)$-го звена антицепи, поэтому $(i{+}1)$-е
звено антицепи левее $i$-го справа звена цепи. Между концом $(i{+}2)$-го и
началом $i$-го справа звена цепи не начинается никакое запретное слово, поэтому
начало $(i{+}1)$-го звена антицепи левее конца $(i{+}2)$-го звена цепи. Так как
$(i{-}1)$-е звено антицепи не левее $i{-}1$-го звена цепи, то $(i{+}1)$-е звено
цепи не пересекает $(i{-}1)$-е звено антицепи, но пересекает $i$-е звено,
поэтому $(i{+}1)$-е звено антицепи не левее $(i{+}1)$-го звена цепи.

%44
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}. Пусть
цепь $c'$ -- подслово цепи $c$. Докажем по индукции, что $i$-е
звено цепи $c$ не правее $i$-го звена цепи $c'$. База $i=1$
очевидна. Если первые звенья цепей совпадают, и одна является
подсловом другой, то все остальные звенья также совпадают, и, в
частности, если такие цепи имеют одинаковую длину, то они
совпадают. Поэтому цепь $c'$ начинается не с начала, а поэтому
первое звено цепи $c'$ правее или совпадает со вторым звеном цепи
$c$. Если бы второе звено цепи $c$ было правее первого звена цепи
$c'$, то тогда бы первое звено цепи $c'$ можно было бы выбрать в
качестве второго звена цепи $c$. Значит, второе звено цепи $c$
левее второго звена цепи $c'$, и база индукции верна для $i=2.$
Перейдём к шагу индукции. Если $(i{+}1)$-е звено цепи $c'$ не
пересекается с $i$-ым звеном цепи $c$, то $(i{+}1)$-е звено цепи
$c'$ правее $(i{+}1)$-го звена цепи $c$. Также добавленное звено
цепи $c'$ не пересекается с $(i{-}1)$-м звеном цепи $c'$, а
значит, по предположению индукции с $(i{-}1)$-м звеном цепи $c$.
Поэтому, если $i{+}1$-е звено цепи $c'$ пересекает $i$-е звено
цепи $c$, то $i{+}1$-е звено цепи $c$ всё равно не правее
$(i{+}1)$-го звена цепи $c'$, потому что иначе то звено можно было
бы выбрать вместо этого. Шаг доказан. Значит, последние звенья
цепей совпадают, но по прошлой задаче данная пара цепей является
также парой антицепей одинаковой длины с совпадающими первыми
звеньями, откуда они совпадают.

\bigskip {\bf \refstepcounter{problem}\label{gc}
\noindent\arabic{problem}}. Пусть слово представлено в виде $gc$,
где $g$ -- допустимое слово, а $c$ -- цепь длины не менее двух. По
задаче \ref{antichain} цепь $c$ также является антицепью. Если при
убирании первого звена цепи $c$ появляется запретное слово, не
зацепленное с укороченной цепью $c$, то антицепь $c$ можно
продолжить влево и получить новое представление $g'c'$, где длина
цепи увеличилась. Если такого запретного слова не появилось, то
антицепь $c$ можно укоротить на самое левое звено и получить новое
представление $g'c'$, в котором длина цепи уменьшилась. Если есть
ещё одно представление $g''c''$, то заметим, что дуги антицепей
$c$, $c'$, $c''$ совпадают, а значит, длина каких-то двух цепей
отличается минимум на два, но тогда допустимое слово перед
короткой антицепью содержит самое левое звено более длинной
антицепи, противоречие.

%46
\bigskip {\bf \refstepcounter{problem} \label{formula}
\noindent\arabic{problem}}. Для решения этой задачи мы применим
задачу 21 для точной последовательности $$ \dots \Longrightarrow
C_{n+1}\cdot G \Longrightarrow C_n\cdot G \Longrightarrow
C_{n-1}\cdot G \Longrightarrow \dots C_1\cdot G \Longrightarrow
A\cdot G \Longrightarrow \bar{G}$$

Построим эту последовательность. Возьмём слово $cg$ из $C_n\cdot G$. Хвост цепи
$c$ припишем в начало слова $g$ и получим $c'g'$. Если $g'$ допустимое слово,
то слово $c'g'$ принадлежит $C_{n-1}\cdot G$. Если слово $g'$ содержит
запретное слово, то цепь $c$ можно продолжить вправо до цепи $c''$, остаток
обозначим $g''$. Тогда слово $c''g''$ принадлежит $C_{n+1}\cdot G$. Цепь можно
единственным образом продолжать внутри слова, поэтому построенные отображения
взаимно-однозначны на частях языков $C_n\cdot G$.

Стрелки $C_1\cdot G \Longrightarrow A\cdot G \Longrightarrow
\bar{G} \Longrightarrow \emptyset$ мы берём из задачи 27. По
задаче 21 $$ 1 - L(x) (1-Nx+C_1(x)-C_2(x)+C_3(x)-\dots) = 0 .$$
Откуда получаем требуемое.

%47
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}. По
задаче \ref{tournament}
$C_1(x)=x^2+x^5+x^{10},C_n(x)=x^{9(n-1)}(x^5+x^{10})$. По формуле
из задачи \ref{formula} \begin{multline*} L(x) =
\frac1{1-26x+x^2+(x^5+x^{10})(1-x^9+x^{18}-\dots)}=\frac1{1-26x+x^2+\frac{x^5+x^{10}}{1+x^9}}
= \\ = \frac{1+x^9}{1-26x+x^2+x^5+x^9-25x^{10}+x^{11}}
\end{multline*}

%48
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}.
Рассмотрим четыре варианта запретного слова из четырёх букв с точностью до
замены букв.

{\bf 1)} Запретное слово имеет вид aaaa. В этом случае
$C_{2n}=x^{4n+1},C_{2n-1}=x^{4n}$. По формуле задачи \ref{formula}
\begin{multline*} L(x)=\frac1{1-256x+x^4-x^5+\dots} =
\frac1{1-256x+\frac{x^4-x^5}{1-x^4}} = \frac{1-x^4}{1-256x+255x^5}
= \\ =
(1-x^4)(1+(256x-255x^5)+(256x-255x^5)^2+\dots).\end{multline*}

Коэффициент при $x^7$ равен
$256^7-3\cdot256^2\cdot255-256^3=256^7-4\cdot256^3+3\cdot256^2$.

{\bf 2)} Запретное слово имеет вид abca и хотя бы две различные
буквы. В этом случае $C_n=x^{3n+1}.$ $$L(x) =
\frac1{1-256x+x^4-x^7+\dots} = 1+(256x-x^4+x^7-\dots) +
(256x-x^4+x^7-\dots)^2+\dots $$

Коэффициент при $x^7$ равен $256^7-4\cdot256^3+1$

{\bf 3)} Запретное слово имеет вид abab. В этом случае
$C_n=x^{2(n+1)}$. $$L(x)=\frac1{1-256x+x^4-x^6+x^8(\dots)}$$

Коэффициент при $x^7$ равен $256^7-4\cdot256^3+2\cdot256$

{\bf 4)} Запретное слово свободно. А случай свободного запретного
слова разобран в задаче~18.

%49
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}. Из
задачи \ref{formula} следует, что $$ \frac1{1-Nx}-L(x) = L(x)\cdot
C_1(x)\cdot\frac1{1-Nx}-L(x)\cdot
C_2(x)\cdot\frac1{1-Nx}+L(x)\cdot C_3(x)\cdot\frac1{1-Nx}-\dots $$

(Бесконечная сумма имеет смысл, поскольку степени начальных членов
слагаемых растут.) В левой части равенства стоит ряд размеров
множества недопустимых слов. В правой части равенства стоит
знакопеременная сумма рядов размеров множеств $L\cdot C_n\cdot
F_A$. Определено отображение для каждого из этих языков в
множество недопустимых слов, и наоборот, каждое недопустимое слово
можно представить в виде $gc_1u$, где $g$ -- допустимое, $c_1$ --
запретное слово. Но недопустимое слово может быть представлено в
виде $g c_n u$, где $g$ -- допустимое, а $c_n$ -- цепь длины $n$,
несколькими способами. Пусть для слова $w$ число таких способов
равно $w_n$. Тогда сумма чисел $(w_1-w_2+w_3-w_4+\dots)$ по всем
словам длины $k$ равна коэффициенту при $x^k$ в правой части
равенства выше, а значит, и в левой, что равно количество
недопустимых слов длины $k$.

Заметим, что из представления слова $w$ в виде $gc_nu$ можно получить другое
представление с длиной цепи на единицу меньше, отбросив хвост цепи $c_n$ в
остаток $u$. Поэтому два таких варианта сократятся в сумме
$(w_1-w_2+w_3-w_4+\dots)$. Другими словами рассматриваемая сумма равна числу
представлений слова $w$ в виде $g c u$, где подслово $c$ -- это максимальная
подцепь слова $w$, причём цепь $c$ имеет нечётную длину.

Рассмотрим представление слова $w$ в виде $gcu$, где $c$ --
максимальная цепь с самым правым последним звеном. По задаче
\ref{gc} либо в слове $gc$ есть максимальная цепь длины 1, либо
оно представимо в виде $g'c'$, где $g'$ -- допустимо, а $c'$ --
цепь, которая либо длиннее, либо короче цепи $c$ на одно звено.
Заметим, что $c'$ -- также максимальная подцепь слова $w$. Одна из
цепей $c$ и $c'$ имеет нечётную длину. Тем самым мы показали, что
сумма $(w_1-w_2+w_3-w_4+\dots)$ не меньше единицы. Но сумма таких
величин по всем недопустимым словам длины $k$ равна их количеству.
Значит, каждая величина равна единице, и в каждом недопустимом
слове максимальных цепей нечётной длины ровно одна.

\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}. Применим
формулу задачи \ref{formula}. $$L'(x) =
\frac1{1-(N+1)x+C_1(x)-C_2(x))+\dots} = \frac1{\frac1{L(x)}-x}$$


%51
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}. Применим
формулу задачи \ref{formula}. \begin{multline*} W(x) =
\frac1{1-(N+N')x+(C_1(x)+C_1^{'}(x))-(C_2(x)+C_2^{'}(x))+\dots} =
\frac1{\frac1{L(x)}+\frac1{L'(x)}-1} \end{multline*}

%52
\bigskip {\bf \refstepcounter{problem} \noindent\arabic{problem}}.
Допустимые слова языка $M$ -- это цепи языка $L$. Цепи длины $n$
этих языков состоят из $n{+}1$-й буквы, поэтому
$C_n(-x)=(-1)^{n+1} C_n(x).$ Имеем
$M(-x)=1-Nx+C_1(x)-C_2(x)+\dots$, то есть $L(x)M(-x)=1$.


\section{Дополнительные задачи}

$\phantom{x}$


{\bigskip  \bf \noindent53.}
  Существование свободного множества при условии $m \le
k^d (d-1)^{d-1}$ доказано в задачах~37 и~38. Осталось доказать,
что при $m > k^d (d-1)^{d-1}$ искомого свободного множества  не
существует.

a) Если задано $m> n^2/4$ слов из двух букв, то они могут
составлять свободное множество $S$ лишь при условии, что первая
буква никакого слова не совпадает со второй буквой никакого
другого слова, т.е. есть два непересекающихся множества букв, $P$
и $Q$, элементы которых могут служить, соответственно, только
начальными или только вторыми буквами слова из $S$. Обозначим
$r=|P| + |Q|\le n $ и $s = |P|\cdot |Q| \ge |S| = m > n^2/4$.  По
теореме Виета, натуральные числа $|P|$ и $|Q|$ являются корнями
квадратного уравнения $x^2-rx+s=0$, дискриминант которого $D =
r^2-4s$ отрицателен при выполнении указанных ограничений на $r$ и
$s$ --- противоречие.

б) Пусть $B$ --- свободное множество $m$ слов длины $3$. Поскольку в свободном
множестве никакая первая буква слова не может быть также и последней буквой
какого-либо слова, в алфавите $A$ есть два непересекающихся подмножества $X$ и
$Y$, элементы которых встречаются, соответственно, только в начале и только в
конце слов из $B$. Если есть буквы, которые не встречаются ни в конце, ни в
начале слова, присоединим их произвольным образом к одному из множеств $X$ и
$Y$. Пусть, для определённости, число $s$ элементов множества $X=\{x_1, \dots,
x_s\}$ не превосходит количество элементов $t$ множества $Y =
\{y_1, \dots, y_t\}$. Каждый элемент множества $B$ имеет вид $x_{i_1} x_{i_2}
y_{j_1}$ или $x_{i_1} y_{j_1} y_{j_2}$, причём никакое финальное подслово вида
$x y$ элемента первого типа не может быть началом элемента второго типа.
Проведём преобразование множества $B$, заменив для каждого финального подслова
$xy$ все слова первого типа, оканчивающиеся на него, на слова второго типа, по
правилу $x_i xy \mapsto xy y_i$, где $1 \le i
\le s \le t$. Легко видеть, что при таком преобразовании никакие элементы не
переходят в другие элементы множества $B$ и никакие различные элементы не
переходят в один и тот же, причём получившееся множество $B'$ останется
свободным. При этом в $B'$ все элементы имеют вид $x_{i_1} y_{j_1} y_{j_2}$.
Следовательно, количество элементов множества $B'$ (равное по-прежнему числу
$m$) не превосходит $st^2$, откуда
$$
m \le st^2 \le  (n-t) t^2 \le \left(n-\frac{2n}{3}\right)
\left(\frac{2n}{3}\right)^2 = \frac{4n^3}{27} = 4k^3,
$$
что и требовалось.



в) Для доказательства потребуется следующая аналитическая

{\bf Лемма.} Пусть $R(x) = 1+a_1x+a_2x^2+\dots$ --- ряд с
натуральными коэффициентами такой, что $R(x) = 1/p(x)$ для
некоторого многочлена $p(x) $ с единичным свободным членом.
Обозначим $R_n(x) = 1+a_1x+a_2x^2+\dots+a_nx^n$. Если  для всех
$x\in [0, x_0]$, где $x_0>0$,  выполняется условие $p(x) \ge m>0$,
то  для всех $n> 0$ справедливы неравенства $R_n(x_0)\le 1/m$.

Не доказывая лемму, перейдём к решению задачи. Обозначим $s = m
k^{-d} - (d-1)^{(d-1)}$; требуется доказать, что при $s>0$
свободного множества не существует. Предположим, что это не так.
Тогда, согласно задаче~39\,a), ряд $1/p(x)$, где $p(x) = 1-dk x+ m
x^d$, имеет натуральные коэффициенты (нулевых коэффициентов быть
не может, поскольку этот ряд бесконечен согласно задаче~33).
Отметим, что при $s>0$ многочлен $p(x)$ положителен на отрезке
$[0,1]$ (доказательство: минимум этого многочлена на отрезке
$[0,1]$ достигается либо в концах отрезка, где $p(x)$ положителен,
либо в такой точке $x_0$, в которой $p'(x_0) =0$, т.~е. при $x_0 =
\frac{1}{k(d-1)}$; при этом $p(x_0) = s x_0^d >0 $). Это означает,
что существует такое число $m>0$, что $p(x) \ge m$ при $x\in
[0,1]$. Согласно лемме, это означает, что для всех $n$ количество
слов длины не выше $n$, равное $L_n(1)$, ограничено константой
$1/m$.



{\bigskip \noindent\bf 54.} \noindent a) По определению, запретными словами
языка $L^!$ являются все двухбуквенные слова, не запретные в $L$.
Следовательно, запретными словами языка $(L^!)^!$ будут все двухбуквенные
слова, не запретные в $L^!$, т.~е. в точности запретные слова языка $L$. Таким
образом, и алфавиты, и наборы запретных слов языков $L$ и $(L^!)^!$ совпадают,
а потому и сами языки равны.


\noindent б) Поскольку множество запретных слов языка $M=(L_1 +
L_2)^!$ есть объединение множеств запретных слов языков $L_1^!$ и
$L_2^!$, а алфавит языка $M$ представляет собой объединение их
(непересекающихся) алфавитов, то язык $M$ есть  свободное
произведение (см. определение в зад.~51) языков $L_1^!$ и $L_2^!$.

\noindent в) Запретными словами языка $(L_1 \cdot L_2)^!$ будут
разрешённые двухбуквенные слова языков $L_1$ и  $L_2$, а также
слова вида $aB$, где $a$ --- буква из алфавита языка $L_1$, а $B$
--- буква из алфавита языка $L_2$. Это означает, что
$$
(L_1 \cdot L_2)^! = L_2^! \cdot L_1^!.
$$




{\bigskip \bf 55.} Пусть $w$ --- слово длины $nk$ (где $k\ge 1 $) над алфавитом
языка $L$, $w^{(n)}$ --- соответствующее ему слово языка $L^{(n)}$. Разобьём
$w$ на подслова $w = w_1 \dots w_k$, каждое из которых соответствует букве
языка $L^{(n)}$. Легко видеть, что слово $w$ содержит какое-то запретное
подслово $u$ (состоящее, по определению, из не более чем $d$ букв) в том и
только том случае, когда в каком-то подслове $w'=w_p \dots w_{p+m-1}$ каждое из
подслов $w_i$ либо содержится в подслове $u$, либо пересекается с ним, так что
количество $n$-буквенных фрагментов $m$ в подслове
 $w'$ удовлетворяет неравенству $ m \le s$,  где
$$
s= 2+ \left[ \frac{d-2}{n}
 \right] .
$$

Таким образом, любое недопустимое слово $w^{(n)}$ языка $L^{(n)}$ содержит
недопустимое подслово из не более чем $s$ букв, т.~е. язык $L^{(n)}$ задаётся
конечным множеством запретных слов, причём длины запретных слов этого языка не
превосходят $s$. Это доказывает утверждение а).

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

Докажем, что при $d\ge 3$ и $n\ge 2$ длины запретных слов языка
$L^{(n)}$ всегда меньше $d$; в частности, этот язык не может быть
$d$-определённым, т.~е. ответ на вопрос из п.~б) отрицательный.
Достаточно доказать неравенство $s < d$, или
$$
2+ \frac{d-2}{n}  < d.
$$
Последнее неравенство равносильно неравенству $(d-2)(1-1/n) > 0$,
которое, очевидно, верно при заданных ограничениях на $d$ и $n$.


\noindent в) Ответ: $n=d-1$. По доказанному выше, язык $L^{(n)}$
является квадратичным или свободным (т.~е. длины запретных слов не
превосходят 2) при условии $s\le 2$, которое  равносильно
неравенству $2+ \frac{d-2}{n} <3$, или $ n> d-2$, т.~е.  $n\ge
d-1$. Если же $n\le d-2$, то существуют такие $d$-определённые
языки $L$, для которых язык $L^{(n)}$ имеет запретные слова из
более чем трёх букв: примером служит язык $L$ с трёхбуквенным
алфавитом $\{ a,b,c\}$ и единственным запретным словом
$abc^{d-2}$.


{\bigskip \noindent\bf 56.} См. решение задачи 58.



{\bigskip \noindent\bf 57.} Ответ: да. Например, пусть $A$ ---
алфавит из $n \ge 2$ букв. Рассмотрим язык $L = F_A \cdot F_A^!$.
Поскольку язык $F_A$ имеет экспоненциальный рост (для него в
задаче 55\,c) можно выбрать $c_1=n+1 $ и $c_2=n$), причём $2
F_A(x) \ge L(x) \ge F_A(x)$, то язык $L$ также имеет
экспоненциальный рост. Согласно задаче~53\,в), имеем $L^! =
(F_A^!)^! \cdot F_A^! = L$, так что оба языка  $L$ и $L^!$  имеют
экспоненциальный рост.







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

{\bf  Лемма.} Пусть $a = \{a_0, a_1, a_2, \dots\}$ ---
последовательность натуральных чисел, в которой $a_0 =1$ и для
некоторого натурального $N$ имеем $a_1\ge 2, \dots, a_N \ge2$.
Тогда последовательность $a$ имеет полиномиальный (соответственно,
экспоненциальный) рост в том и только том случае, когда
соответствующие неравенства из утверждений b) и~с) выполняются для
всех $a_k$ при $k\ge N$.
%последовательность $b = \{ 1,2,2,\dots, a_{N+1}, a_{N+2}, \dots\}$
%(двойки стоят до $N$-го места включительно) имеет такой же рост.

\emph{Доказательство леммы.}\/ Пусть $M = \max\limits_{i\le
N}\{a_i\}$. Очевидно, если для некоторых многочленов $p,q$ степени
$d$ выполняются неравенства $p(k) \ge a_k \ge q(k)$ при $k\ge N$,
то выполняются также и неравенства $p(k) +M \ge a_k \ge q(k)-M$
при всех $k$, что доказывает лемму в случае полиномиального роста.
Аналогично, если $c_1^k \ge a_k \ge c_2^k $ при $k\ge N$, то
$(M+c_1)^k \ge a_k \ge g^k $ при всех $k$, что полностью
доказывает лемму.

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

Предположим, что есть два пересекающихся цикла; пусть их длины
суть $d_1$ и $d_2$, и $v$ --- общая вершина, исходящие из которой
ребра  различны для обоих циклов (скажем, отвечающие буквам $x$ и
$y$). Слова, которые прочитываются на ребрах $k$-звенных
маршрутов, начинающихся в $v$ и проходящим по каждому из циклов,
различны, поэтому $a_k\ge 2$ при всех $k\ge 0$. Кроме того, для
любого $j = (d-1) + q(d_1+d_2) +r$, где $r<d_1+d_2$ --- остаток от
деления числа $j-d+1$ на $d_1+d_2$, существует по крайней мере
$2^q$ различных маршрутов длины $j-d+1$ (на каждом из $q$ шагов
проходим оба цикла в произвольном порядке, а затем делаем $r$
шагов в произвольном цикле), так что при $j \ge 2d $ имеем $a_j
\ge 2^q = 2^{\left[ \frac{j-d+1}{d_1+d_2} \right]} \ge c^j$, где
$c = 2^{1/{2(d_1+d_2)}}$. Поскольку всегда $a_j \le n^j$, из
доказанной леммы (при $N=2g$) следует, что рост экспоненциальный.

Осталось разобрать случай, когда в графе $\Gamma_L$ циклы есть, но они не
пересекаются между собой. Достаточно проверить условия полиномиальности для
количеств маршрутов $b_k = a_{k+d-1}$ длины $k$ в графе $\Gamma_L$ (т.к. если
соответствующие неравенства выполняются для чисел $b_k$, то они выполняются и
для $a_k$ при $k\ge d-1$ при замене многочленов $p(x)$ и $q(x)$ на многочлены
той же степени $p_1(x) = p(x+d-1)$ и $q_1(x) = q(x+d-1)$). Мы докажем, что
каждый член последовательности $b_k$ равен значению некоторого многочлена
$b(k)$ с положительным старшим коэффициентом (будем называть такие
последовательности полиномиальными).


Рассмотрим другой граф $\Gamma_L'$, вершинами которого служат циклы графа
$\Gamma_L$ и вершины графа $\Gamma_L$, не входящие в циклы (назовём их
обособленными), а ребра соответствуют ребрам, соединяющим соответствующие
компоненты (вершины или циклы) графа $\Gamma_L$. Очевидно, в графе $\Gamma_L'$
циклов нет, т.е. множество маршрутов в нём конечно. Пусть $Q^v$ --- множество
маршрутов в графе $\Gamma_L'$, исходящих из данной вершины $v$, и пусть $q^v_k$
--- количество маршрутов длины $k$, которое им соответствует в графе
$\Gamma_L$. Поскольку $b_k = \sum_{v} q^v_k$, достаточно доказать, что
последовательность $\{q^v_k\}$ для каждой вершины $v$ полиномиальна.
Воспользуемся индукцией по длине $D = D(v)$ максимального маршрута, исходящего
из $v$. Если $D=0$, то либо $q^v_k = 0$ при $k>0$ (если $v$ --- обособленная
вершина), либо $q^v_k = 1$ для всех $k$ (если $v$ --- цикл), т.~е.
соответствующая последовательность всегда полиномиальна. Пусть теперь $v$ ---
какая-то начальная вершина графа $\Gamma_L'$, из которой исходят $r$ стрелок
$a_1, \dots, a_r$ к вершинам $v_1, \dots, v_r$ (возможно, повторяющимся). По
индукции, считаем $q^{v_{i}}_{k} = b_i(k)$ --- многочлен с положительным
старшим коэффициентом. Если $v$ --- обособленная вершина, то $q^v_k =
\sum_{i=1}^r q^{v_{i}}_{k-1}$, т.е. эта последовательность полиномиальна как
сумма полиномиальных последовательностей. Если же $v$ --- цикл, то перед
переходом к вершинам по ребрам $a_1, \dots, a_r$ возможно слово любой длины в
цикле, поэтому $q^v_k = \sum_{i=1}^r\left(\sum_{j=1}^k q^{v_{i}}_{k-j} \right)
= \sum_{i=1}^r\left(\sum_{j=1}^k b_i(k-j) \right)$ --- сумма многочленов с
положительными старшими коэффициентами. Утверждение доказано.

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


\bigskip {\bf \noindent 59.}
Обозначим множество допустимых слов через $M$. Пусть язык является
$d$-определённым. Докажем, что каждое слово $M$-эквивалентно слову не более чем
из $d$ букв.

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

Пусть слово $u$ допустимо и имеет длину, большую $d$. Обозначим
через $v$ подслово слова $u$, состоящее из его последних $d$ букв.
Пусть $w$ --- произвольное слово. Если слово $uw$ содержит
запретное подслово, то это подслово содержится в $vw$, так как
длина запретного подслова не больше $d$. Поэтому слова $u$ и $v$
эквивалентны.

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


\bigskip {\bf \noindent60.}
 а) Пусть $S$ --- максимальное множество слов, из которых никакие два не
$M$-эквивалентны. Тогда любое другое слово эквивалентно какому-то слову из $S$.
Построим конечный автомат. Возьмём $S$ в качестве множества вершин графа. Для
всех $s\in S$, $a\in A$, проведём из вершины $s$ стрелку, помеченную $a$, в
вершину, $M$-эквивалентную $sa$. В полученном графе назовём начальной вершиной
ту, которая $M$-эквивалентна пустому слову, а принимающими вершинами --- все
слова из $S$, которые принадлежат $M$. Легко видеть, что построенный конечный
автомат принимает те и только те слова, которые принадлежат $M$.

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

\bigskip {\bf \noindent61.}
Рассмотрим конечный автомат $(\Gamma,v_0,W)$, принимающий множество $M$. Для
каждой вершины $v$ этого конечного автомата обозначим через $T_v$ множество
слов, для которых соответствующие пути по графу $\Gamma$ заканчиваются в $v$.


Далее, для каждой вершины $v$ и каждой буквы $a$ обозначим через $U(v,a)$
множество таких вершин $u$ графа $\Gamma$, что из $u$ в $v$ идёт стрелка,
помеченная $a$. Тогда выполнены следующие равенства:
\begin{equation}\label{eq_init}
T_{v_0}(x) = 1 + \sum_{a\in A}\;\sum_{u\in U(v_0,a)}xT_u(x)
\end{equation}
и
\begin{equation}\label{eq_all}
T_{v}(x) = \sum_{a\in A}\;\sum_{u\in U(v,a)}xT_u(x)
\end{equation}
для $v\ne v_0$.

Перенумеруем вершины графа $\Gamma$, начиная с $v_0$:
$V=\{v_0,v_1,v_2\dots,v_k\}$. Заметим, что каждое из равенств (\ref{eq_init}),
(\ref{eq_all}) можно воспринимать как уравнение вида
\begin{equation}\label{eq_gen}
(1+xP_i(x))T_{v_i}(x) = \sum_{j\ne i}xQ_{ij}(x)T_{v_j}(x) + R_i(x),
\end{equation}
где $P_i(x),Q_{ij}(x),R_j(x)$ --- некоторые известные многочлены, относительно
неизвестных рядов $T_{v_0}(x),\dots,T_{v_k}(x)$.

Попробуем решить уравнения (\ref{eq_gen}). Выразим из последнего уравнения
$T_{v_k}(x)$ через остальные неизвестные ряды,
$$
T_{v_k}(x) = \sum_{j\ne k}x\frac{Q_{kj}(x)}{(1+xP_k(x))}T_{v_j}(x)
 + \frac{R_k(x)}{(1+xP_k(x))},
$$
подставим это выражение вместо $T_{v_k}(x)$ в остальные уравнения, и домножим
их все на $(1+xP_k(x))$. Мы получим уравнения того же вида, но число их (как и
число неизвестных) станет на единицу меньше. Проделав то же самое для
$T_{v_{k-1}}(x)$, $T_{v_{k-2}}(x)$, и т.\,д., мы получим в конце концов
выражение для $T_{v_0}(x)$ в виде отношения двух многочленов. Подставив его в
выражение для $T_{v_1}(x)$, получаем, что и этот ряд есть отношение двух
многочленов. Продолжая этот процесс, получаем выражения того же вида для всех
$T_{v_i}(x)$. Осталось заметить, что $M(x) = \sum_{v\in W}T_v(x)$.

\bigskip {\bf \noindent62.}
Для каждого слова $v$ обозначим через $v^{opp}$ слово, состоящее из тех же букв
в противоположном порядке. Для каждого множества слов $M$ положим
$M^{opp}=\{v^{opp}\mid v\in M\}$. Ясно, что $M^{opp}(x)=M(x)$ для любого $M$.
Если $L$ --- язык с множеством запретных слов $B$, то через $L^{opp}$ мы
обозначаем язык с множеством запретных слов $B^{opp}$.

Вернёмся к задаче. Очевидно, что $M_w^{opp}$ --- это множество допустимых слов
языка $L^{opp}$, начинающихся с подслова, равного $w^{opp}$. Это множество
регулярно (доказательство аналогично решению задачи 59). Поэтому ряд
$M_w(x)=M_w^{opp}(x)$ равен отношению двух многочленов.

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


\end{document}
