%\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{plain}
\newtheorem{problem}{Задача}

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


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

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



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


\begin{document}

\maketitle


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

\begin{problem}
\label{1}
В словаре племени Винни--Пухов 100 слов. В фразах их языка возможны любые
сочетания этих слов. Существуют два магических заклинания, ``Земля стоит на
великом крокодиле'' и ``Каждый вечер крокодил глотает солнце'', которые
вызывают ураган, и поэтому вслух можно произносить только такие фразы, в
которых эти последовательности слов не встречаются\footnote{Даже если слова в
других словарных формах.}. Сколько всего фраз из двадцати слов можно
произносить вслух?
\end{problem}



\begin{problem}
\label{2} У компьютера есть $256$ различных команд. Существует
одна последовательность из четырёх команд, после которой компьютер
ломается. Программисты написали все возможные
программы из семи команд. Сколько процентов из них не сломают компьютер?%
\footnote{Подобная история в 1990-е гг произошла с первой версией
микропроцессора
          {\it Pentium}.% (``Pentium F00F bug''.)
          }
\end{problem}



\begin{problem}[Главная Задача]
 \label{main_p}
\label{0} Алфавит некоторого языка $L$ состоит из $N$ букв. Задано
несколько слов $v_1, \dots, v_k$, которые называются\/ \emph{запретными} и в
языке не употребляются. Слово (то есть ограниченная последовательность букв)
называется\/ \emph{допустимым}, если никакая часть этого слова не является
запретным словом. Сколько в языке $L$ возможно допустимых слов из $n$ букв?
\end{problem}


\begin{problem}
Докажите, что задачи~\ref{1}  и~\ref{2} сводятся к задаче~\ref{0}.
\end{problem}

%Все остальные задачи этой темы тоже будут сводиться к Главной задаче.






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

Зафиксируем какой-нибудь алфавит $A$ из $N$ букв (например, если $A =
(a,b,c,\dots,z)$, то $N=26$). \emph{Словом} мы будем называть любую конечную
последовательность букв алфавита $A$. \emph{Подсловом} мы будем называть часть
слова, состоящую из идущих подряд в этом слове букв.

Мы будем считать, что в каждом языке $L$ есть ровно одно слово из
нуля букв --- {\it пустое} слово. %Оно традиционно обозначается
%символом $\Lambda$.

Мы будем считать, что запретные слова не содержатся друг в друге,
т.е. никакое подслово запретного слова, кроме него самого, не
является снова запретным. Кроме того, мы будем считать, что
запретные слова состоят как минимум из двух букв, т.е. что пустое
слово и отдельные буквы являются допустимыми словами.
 Напомним, что множество запретных слов
конечно.


\begin{problem}
\label{free} \emph{Свободным языком} алфавита $A$ называется язык
$F_A$, в котором вообще нет запретных слов. Докажите, что
количество слов из $n$ букв в этом языке равно $N^n$.
\end{problem}


\begin{problem}
\label{b} В языке $B$  запретными являются все слова из двух
различных букв. Докажите, что для любого  натурального $n$
количество допустимых слов из $n$ букв в этом языке равно $N$.
\end{problem}


Пусть $M$ --- какое-нибудь множество слов. Обозначим через   $m_n$
количество слов в этом множестве, состоящих  из $n$ букв.
 \emph{Рядом размеров}  множества
$M$  называется бесконечная сумма
$$
  M (x) = m_0 + m_1 x + m_2 x^2  + m_3 x^3 + \dots
$$
Такого вида бесконечные суммы (с произвольными числами в качестве коэффициентов
$m_n$) мы будем кратко называть просто\/ \emph{рядами} (их полное название,
которое мы не будем использовать --- \emph{формальные степенные ряды}).

Для каждого языка $L$ его рядом размеров $L(x)$ называется ряд размеров
множества допустимых слов. Например, для свободного языка $F_A$ ряд размеров
--- это сумма геометрической прогрессии $F_A(x) = 1 + N x + N^2 x^2 + N^3 x^3 +
\dots $,
 а для языка $B$  это $B (x) = 1 + Nx + Nx^2 + Nx^3 + \dots$

%Хотя в ряде размеров стоит знак "$+$",
%складывать его члены нельзя: это просто
%способ записи ответа к Главной задаче сразу для всех возможных $n$.

\begin{problem}
\label{3} Выпишите ряд размеров для языка над алфавитом $\{a,b\}$, в
котором запретными являются слова $aa$  и $bb$.
\end{problem}




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


Если множество $M$  содержит только ограниченное количество слов,
то его ряд размеров --- это многочлен от переменной $x$.
Для бесконечных множеств и ряды тоже бесконечные,
но с ними можно производить разные арифметические операции, похожие
на операции с многочленами, то есть складывать, вычитать, умножать
друг на друга и на числа и даже иногда делить.


В определениях и задачах этого раздела $S = s_0 + s_1 x + s_2 x^2
+ \dots$ и
$R = r_0 + r_1 x + r_2 x^2 + \dots$ --- два %формальных степенных
ряда, а $L_1$
и $L_2$ --- какие-то два языка с разными алфавитами $A_1$ и $A_2$. Для
определённости, мы будем считать, что алфавит $A_1$ состоит из заглавных букв,
а алфавит $A_2$ --- из строчных. Алфавит $A$ --- это объединение двух алфавитов
$A_1$ и $A_2$, то есть в него входят и заглавные, и строчные буквы.




\begin{definition}
a)\/ \emph{Суммой рядов} $R$ и $S$ называется сумма
$$
  R + S = (s_0 + r_0) +(s_1 + r_1)x +(s_2 + r_2)x^2 + \dots
$$

б)\/ \emph{Суммой языков} $L_1$ и $L_2$ называется язык $L_1 + L_2$ над
алфавитом $A$, у которого множество допустимых слов --- объединение множеств
допустимых слов языков $L_1$ и $L_2$.
% все допустимые слова --- это
%допустимые слова языков $L_1$ и $L_2$.
\end{definition}


\begin{problem}
Задайте язык $L_1 + L_2$ конечным множеством запретных слов.
\end{problem}


\begin{problem}
Докажите, что если $L=L_1 + L_2$,
  то
$$
  L (x)  = L_1  (x)   +  L_2  (x) - 1.
$$
\end{problem}



 Произведение рядов размеров определяется так же, как произведение
многочленов.

\begin{definition}
\emph{Произведением ряда $R$ на одночлен $a x^n$}
 называется  ряд
$$
  R\cdot a x^n = a r_0 x^n + a r_1 x^{n+1} + a r_2 x^2 x^{n+2} + \dots
$$
\emph{Произведением рядов $R$ и $S$} называется сумма
$$
  R \cdot S = R\cdot s_0 + R\cdot s_1 x + R\cdot s_2 x^2 + \dots
$$
Заметим, что эта бесконечная сумма %формальных степенных
рядов имеет смысл ---
складывая ряды почленно, мы получаем в качестве коэффициента при каждой степени
$x$ конечную сумму чисел.

\end{definition}

\begin{problem}
\label{progr}
 Докажите равенство
$$
  (1-x) \cdot (1+ x+ x^2 + \dots) = 1.
$$
\end{problem}


\begin{definition}
 \emph{Произведением двух множеств слов} $M,N$  называется множество $MN$ всех слов
вида $mn$, где $m$ --- слово из $M$, а $n$ --- слово из $N$.



\emph{Произведением двух языков} $L_1$ и $L_2$ называется язык $L_1 \cdot L_2$
над алфавитом $A$, у которого множество допустимых слов является произведением
множеств допустимых слов языков $L_1$ и $L_2$.
%запретными являются
%все запретные слова языков $L_1$ и $L_2$, а также те слова, в
%которых строчные буквы идут раньше заглавных.
\end{definition}

\begin{problem}
Задайте язык $L_1 \cdot L_2$ конечным множеством запретных слов.
\end{problem}


\begin{problem}
%
%а) Пусть $M,N$ --- два множества слов.
%Докажите формулу
%$$
%    M\cdot N (x) = M(x) \cdot N(x).
%$$
%
%
%
%Пусть $L = L_1 \cdot L_2$.
%
%
%б) Докажите, что все допустимые слова языка $L$  имеют вид $Ww$,
%где $W$ ---  допустимое слово из языка $L_1$  (состоящее из
%заглавных букв), а $w$ --- допустимое слово из языка $L_2$
%(состоящее из строчных букв).
%
%в)
 Докажите равенство
$$
  L (x) = L_1 (x) \cdot L_2 (x).
$$
\end{problem}



Деление рядов не имеет аналога для языков, но позволяет сокращённо записывать
их ряды размеров. Оно определяется по формуле, похожей на формулу суммы
геометрической прогрессии.

\begin{definition}
 Предположим, что ряд $S$ начинается с единицы, то есть
$s_0 = 1$, и $S = 1 + \overline S$,
 где $\overline S = s_1 x + s_2 x^2 + \dots$
 Тогда  \emph{обратным рядом} называется ряд
$$
  \frac{\d 1}{\d S} = 1 - \overline S +\overline S^2 -\overline S^3 +\dots
$$
\emph{Частным} от деления рядов $R$ и $S$ называется ряд
$$
  \frac{\d R}{\d S} = R -R\cdot \overline S +
       R\cdot \overline S^2 -R\cdot \overline S^3 +\dots
$$
\end{definition}

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


\begin{problem}
a) Докажите, что
$$
   S \cdot \frac{\d R}{\d S} = R.
$$

b) Докажите, что если $S \cdot T = R$, где ряд $S$ начинается с
единицы, то $T = \frac{\d R}{\d S} $.
\end{problem}


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

\begin{problem}
a) Докажите, что
$$
   F_A(x) = \frac{\d 1}{\d 1 - Nx}.
$$

б) Запишите ряды размеров языков из задач~\ref{b}  и~\ref{3}
в виде частного двух многочленов.
\end{problem}


\begin{problem}%\footnote{Жюри неизвестно элементарное решение этой задачи}
\label{grob1}
Докажите, что  ряд размеров любого языка может быть
записан в виде частного двух многочленов.
\end{problem}


Таким образом, ответ к Главной Задаче
% (Задаче~\ref{main_p})
должен быть представим в виде частного двух многочленов.


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




\begin{problem}
 Пусть  $L$ --- язык над латинским алфавитом,
в котором запретным является только слово ``mouse''. Найдите
$L(x)$.
\end{problem}



\begin{definition}
Пусть $a,b$ --- два слова, из которых ни одно не является частью другого.
Непустое слово $c$ называется\/ \emph{зацеплением} слов $a$ и $b$, если оно
является окончанием слова $a$ и в то же время началом слова $b$ (например,
слово ``ко'' --- зацепление слов ``молоко'' и ``корова'').

Слово называется\/ \emph{свободным,} если у него нет никаких зацеплений с самим
собой, кроме самого этого слова.
\end{definition}


\begin{problem}
 Пусть в языке  $L$  над алфавитом $A$  из $N$  букв имеется только одно
запретное слово --- некоторое свободное слово из $m$ букв.
Докажите, что
$$
   L(x) = \frac{1}{1-Nx+ x^m}.
$$
\end{problem}


\begin{problem}
Решите задачу~\ref{2} в предположении, что последовательность, ломающая компьютер,
является свободным словом.
\end{problem}


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

\begin{definition}
Пусть $M$ и $M'$ --- два множества слов. Разобьём множество $M$ на какие-нибудь
две части $K$ и $L$. Функция $f$ из множества $L$ в какое-нибудь подмножество
$I$ множества $M'$ называется\/ \emph{преобразованием} множества $M$ в
множество $M'$, если $f$ сохраняет длину слова и является взаимно однозначным
отображением из $L$ в $I$.

В этом случае множество $K$ называется\/ \emph{ядром} отображения $f$, а
множество $I$ --- его\/ \emph{образом}.
\end{definition}
Преобразование мы будем обозначать стрелкой: $M \Longrightarrow M'$.



\begin{definition}
 Цепочка преобразований
$$
  M_1 \Longrightarrow M_2 \Longrightarrow \dots \Longrightarrow M_n
$$
называется\/ \emph{точной}, если
%ядро первой стрелки пусто, образ последней стрелки есть $M_n$, а
%для всех остальных стрелок
ядро каждого следующего преобразования совпадает с образом
предыдущего.
\end{definition}


\begin{problem}
 Пусть $L$ --- язык над алфавитом $A$ с множеством допустимых слов $G$ и множеством всех не
допустимых слов $N$. Постройте точную последовательность
преобразований
$$
 \emptyset \Longrightarrow N \Longrightarrow F_A \Longrightarrow G \Longrightarrow \emptyset,
$$
где $F_A$ --- множество слов свободного языка, то есть всех слов
над алфавитом $A$, а $\emptyset$ обозначает пустое множество.
\end{problem}



\begin{problem}
В ряд сидят по очереди мальчики и девочки, по 10 тех и других;
последней сидит учительница. У детей есть конфеты, поровну в сумме
у мальчиков и у девочек.  Первый мальчик отдаёт все свои конфеты
сидящей за ним девочке. Девочка съедает их, съедает из своих
конфет столько же, а остаток отдаёт следующему мальчику. Тот тоже
поступает точно так же, за ним --- следующая девочка, и так далее.
Последняя девочка отдаёт остаток своих конфет учительнице. Сколько
ей достанется?
\end{problem}


\begin{problem}
Пусть
$$
\emptyset \Longrightarrow   M_1 \Longrightarrow M_2
\Longrightarrow \dots \Longrightarrow M_n \Longrightarrow
\emptyset
$$
--- точная цепочка преобразований.

а) Докажите, что если в каждом множестве $M_i$ только конечное
число $m_i$ слов, то
$$
   m_1 + m_3 +m_5 + \dots = m_2 + m_4 + \dots
$$

б) Докажите формулу для рядов размеров
$$
   M_1(x) + M_3(x)  +M_5 (x) + \dots = M_2(x)  + M_4(x)  + \dots
$$
\end{problem}


\begin{definition}
Множество слов $M$ называется\/ \emph{свободным,} если никакое слово из $M$ не
является подсловом другого слова из этого множества, все слова в нём свободные
и не имеют зацеплений между собой.
\end{definition}


\begin{problem}
 Пусть $L$ ---  язык над алфавитом $A$,  у которого множество запретных
слов $B$ свободное. Обозначим через $G$ множество его допустимых
слов, через $\overline G$ --- множество всех допустимых слов,
кроме пустого. Постройте точную последовательность преобразований
$$
\emptyset \Longrightarrow
  B\cdot G \Longrightarrow A \cdot G   \Longrightarrow \overline G
  \Longrightarrow \emptyset.
$$
\end{problem}


\begin{problem}
 Пусть $L$ ---  язык над алфавитом $A$  из $N$ букв,
у которого множество запретных слов $B$ свободное. Докажите
формулу
$$
   L (x) = \frac{\d 1}{\d 1 - N x + B(x)}.
$$
\end{problem}

\begin{problem}
Докажите, что множество заклинаний в задаче~\ref{1} свободное,
и решите её.
\end{problem}


\begin{problem}
Найдите $L(x)$,  если алфавит языка $L$  --- латинский, а
запретные слова --- это слова {\it veni, vidi, vici.}
\end{problem}

\begin{definition}
Пусть $L$ --- язык. \emph{Простой сцепкой} называется слово $v = str$, где $s$,
$t$, $r$ --- непустые слова, причём $g=st$ и $f=tr$ --- запретные слова, и
больше никаких запретных подслов в $v$ нет. Конец $r$ простой сцепки,
остающийся после первого запретного слова $g$, называется её хвостом.
% Простой сцепкой  называется слово $v = gt =
%sf$, у которого имеется начало $g$ --- запретное слово, не
%совпадающее с $v$, конец $f$
%--- тоже запретное слово, которое зацепляется с $g$, и больше никаких запретных слов в $v$ нет.
%Конец $t$ простой сцепки, остающийся после первого запретного
%слова $g$, называется её хвостом.
%
%Язык $L$ называется слабо сцепленным, если никакие простые сцепки
%не зацепляются ни друг с другом, ни сами с собой.
\end{definition}

\begin{problem}
Докажите, что множество запретных слов языка является свободным в
том и только том случае, если в этом языке нет простых сцепок.
\end{problem}



\begin{problem}
\label{syz_2} Пусть  $L$ --- язык над некоторым алфавитом $A$  с
множеством запретных слов $B$ и множеством простых сцепок $S$.
Обозначим через $G$  множество его допустимых слов, через $\o G$
--- множество всех допустимых слов, кроме пустого. Постройте точную
последовательность преобразований
$$
%\emptyset \Longrightarrow
  S\cdot G \Longrightarrow  B\cdot G \Longrightarrow A \cdot G   \Longrightarrow \overline G
  \Longrightarrow \emptyset.
$$
\end{problem}

\begin{problem}
 Каким условиям должно удовлетворять множество запретных слов
языка $L$, чтобы точную последовательность из задачи~\ref{syz_2}
можно было продолжить до последовательности
$$
\emptyset \Longrightarrow
  S\cdot G \Longrightarrow  B\cdot G \Longrightarrow A \cdot G   \Longrightarrow \overline G
  \Longrightarrow \emptyset
$$
(такие языки назовём незапутанными)? Выведите формулу, которая
выражала бы ряд размеров $L(z)$ незапутанного языка через число
$N$ букв в алфавите  и ряды размеров множеств $B$ и $S$.
\end{problem}


\begin{problem}
Вычислите ряд размеров для языка над  алфавитом из трёх букв
$a,b,c$ с запретными словами $abb, bbc, bac$.
\end{problem}

\begin{problem}
Вычислите ряд размеров для языка над  алфавитом $A = \{ x_1,
\dots, x_n , y_1,  \dots, y_n,z_1, \dots , z_n \}$, в котором
запретными являются все слова вида $x_i y_j$ и $y_j z_k$, где
$1\le i,j,k \le n$.
\end{problem}




\begin{problem}
Докажите, если множество запретных слов незапутанного языка
состоит только из одного слова, то это множество свободно.
\end{problem}

%\pagebreak






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

\begin{problem}
Постройте бесконечное свободное множество в алфавите из двух букв.
\end{problem}


\begin{problem}
Предположим, что множество запретных слов $B$ языка $L$ свободно, а алфавит
содержит более одной буквы. Докажите, что множество допустимых слов этого языка
бесконечно.
\end{problem}

\begin{definition}
Пусть $S = s_0 + s_1 x + s_2 x^2 + \dots$ и
 $R = r_0 + r_1 x + r_2 x^2 + \dots$  ---  два %формальных степенных
 ряда.
 Если для  любых коэффициентов $s_k $  и $r_k$ с одинаковыми номерами выполняется неравенство
  $s_k \ge r_k$, то будем говорить, что между рядами выполняется
  неравенство
$$
   S \ge R.
$$
\end{definition}

\begin{problem}
Докажите, что если для рядов $P,Q$ и $R$ выполняются неравенства
$$
           P \ge Q  \mbox{ и }  R\ge 0,
$$
то
$$
           PR \ge QR.
$$
\end{problem}



\begin{problem}
Предположим, что множества запретных слов $B$ и $B'$ двух языков $L$ и $L'$ над
одним алфавитом $A$ содержат одно и то же количество слов каждой длины, так что
$B(z) = B'(z)$. Докажите, что если множество $B$ свободно, то выполняется
неравенство
$$
            L'(z)  \ge L(z),
$$
причём равенство $L'(z)  = L(z)$ достигается в том и только том
случае, когда множество $B'$ также является свободным.
\end{problem}


\begin{problem}
Известно, что алфавит  состоит из двух букв, а множество  $B$
содержит не менее двух слов, одно из которых, слово $w$, имеет
длину 2.

a) Докажите, что множество $B$ не является свободным.

b) Может ли оно быть свободным, если длина слова $w$ равна 3?
\end{problem}


\begin{problem}
Известно, что алфавит состоит из $n $ букв, а множество $B$ состоит из $g$ слов
длины 2. Докажите, что если $g \le n^2/4$, то множество $B$ может быть выбрано
свободным.
\end{problem}

\begin{problem}
\label{n=kd}
 Докажите, что если $n = k d $ и $m \le k^d
(d-1)^{d-1}$, где числа $d,k,m,n$ натуральные, то над алфавитом из
$n $ букв можно выбрать свободное множество, состоящее из $m$ слов
длины $d$.
\end{problem}

\begin{problem}
а) Докажите, что если $B$ --- свободное множество над алфавитом из $n$ букв, то
выполняется неравенство
$$\frac{1}{1-nx+B(x)} \ge 1.$$

б) Верно ли обратное утверждение: если для некоторого натурального
$n$ и некоторого многочлена $p(x)$ с неотрицательными целыми
коэффициентами и нулевым свободным членом выполняется неравенство
 $$\frac{1}{1-nx+p(x)}
                       \ge 1,$$
 то над алфавитом из $n $ букв  существует свободное
множество $B$ такое, что $B(x) = p(x)$?
\end{problem}

\begin{problem}%\footnote{Жюри неизвестно элементарное решение этой задачи}
\label{grob2}
 Пусть $n$ --- натуральное число,  $p(x)$ ---
многочлен с неотрицательными целями коэффициентами и нулевым
свободным членом. Докажите, что свободное множество $B$ с рядом
размеров $B(x) = p(x)$ существует в том и только том случае, когда
существуют такие многочлены $f$ и $g$ с неотрицательными целыми
коэффициентами такие без свободных членов, что
$$
(1-f)(1-g)\ge 1-nx+p(x).
$$
\end{problem}

\begin{problem}\footnote{Жюри не известны ни решение, ни даже ответ к этой задаче}
\label{grob3}
 Придумайте условие, описывающее
возможные ряды размеров множеств запрещённых слов незапутанных
языков (подобно тому, как в задаче~\ref{grob2} охарактеризованы
ряды размеров свободных множеств).
\end{problem}





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

%Мы будем считать, что набор запретных слов в каждом языке задан экономно, то
%есть никакое запретное слово не является подсловом другого запретного слова.


\begin{definition}
\label{def_chain}
 Пусть $L$ --- язык. Цепями длины 1 называются
все запретные слова, цепями длины 2 --- все простые сцепки. Через
эти цепи определяются ещё цепи длины 3, 4 и так далее. А именно,
слово $v = str$ (где все слова $s$, $t$, $r$ --- непустые)
называется\/ \emph{цепью длины $n$}, если его начало $g=st$
является цепью длины $n-1$, конец $f=tr$ --- запретным словом,
причём $t$ является подсловом хвоста $p$ цепи $g$, и никаких
запретных подслов, кроме $f$, в конечном участке $pr$ нет.
\emph{Хвостом} этой цепи называется слово~$r$.
%А именно, слово $v = gt$ называется цепью длины $n$, если её начало $g$
%является цепью длины $n-1$, какой-то конец $f$ --- запретным словом, которое
%зацепляется с хвостом $r$ цепи $g$, и больше никаких запретных слов в конечном
%участке $rt$ нет. Хвостом этой цепи называется слово $t$, которое остаётся
%после $g$.
\end{definition}

Цепь выглядит примерно так (каждая дуга --- это запретное слово в
ней):

\begin{picture}(90,15)


  \put(12.5,1){\line(1,0){75}}

  \put(20,1){\oval(15,10)[t]}
  \put(30,1){\oval(15,10)[t]}
  \put(40,1){\oval(15,10)[t]}
  \put(50,1){\oval(15,10)[t]}
  \put(60,1){\oval(15,10)[t]}
  \put(70,1){\oval(15,10)[t]}
  \put(80,1){\oval(15,10)[t]}

  \put(67.5,2){\line(1,0){20}}

\end{picture}

Длина цепи --- это количество дуг. Зацепляются только соседние
дуги (т.~е. их пересечение -- зацепление ненулевой длины), и
выделенные два последних хвоста не содержат запретных слов, кроме
последней дуги.

Например, если запретное слово --- $aba$, то единственная цепь
длины 1 --- это  $aba$, длины 2 ---  $ababa$, длины 3 ---
$abababa$,  и так далее.


\begin{problem}
\label{tourn} Пусть в языке $L$  запретными считаются слова
``tournament'', ``of'', ``towns''. Выпишите все цепи длины $n$.
\end{problem}


\begin{problem}
\label{right_chains} \emph{Антицепь} длины $n$ определяется так
же, как и цепь  длины $n$, но все слова языка $L$ в
определении~\ref{def_chain} прочитывается ``справа налево'', т.~е.
хвосты антицепей находятся слева, а начальная цепь длины $n-1$ ---
справа. Докажите, что множества цепей длины $n$ и антицепей длины
$n$ совпадают.
\end{problem}

\begin{problem}
\label{chains} Докажите, что никакая цепь длины $n$ не содержит в
качестве подслова никакую другую цепь длины $n$.
\end{problem}


\begin{problem}
 Докажите, что если слово имеет вид $w= g c$, где $g$ --- допустимое слово, а $c$ ---
 цепь,  то в случае, если длина цепи $c$ больше 1, слово $w$
  представимо в таком виде ровно двумя способами,
 причём длины цепей в этих представлениях различаются на единицу.
\end{problem}





Следующая задача даёт способ решения Главной Задачи.

\begin{problem}
Пусть $L$ --- язык над алфавитом $A$. Обозначим через $G$
множество его допустимых слов, через $\o G$ ---  множество всех
допустимых слов, кроме пустого. Пусть $C_1$ --- множество цепей
длины 1,
      $C_2$ --- цепей длины 2, и так далее.


%а)
%Постройте  бесконечную точную последовательность преобразований
%$$  \dots \Longrightarrow    C_3  \cdot G  \Longrightarrow     C_2  \cdot G  \Longrightarrow
%   C_1 \cdot G \Longrightarrow  A \cdot G   \Longrightarrow \overline G    \Longrightarrow
%\emptyset. $$

%б)
 Докажите формулу
$$
   L(x) = \frac{\d 1}{\d 1 - Nx + C_1(x) - C_2 (x) + C_3 (x) - \dots}
$$
\end{problem}


\begin{problem}
Найдите ряд размеров для языка из задачи~\ref{tourn}.
\end{problem}

\begin{problem}
 Найдите все возможные варианты ответов для задачи~\ref{2}  в зависимости
от того, какие именно команды ломают компьютер.
\end{problem}

\begin{problem}
 Назовём подслово $c$ слова $w$ \emph{максимальной подцепью}, если
 $w$ представимо в виде   $w= g c u$, где $g$ --- допустимое слово, а $c$ ---
 цепь,  причём для любого другого представления $w= g c' u'$ с другой цепью $c'$ всегда
 слово $c'$ --- подслово слова $c$. Докажите, что любое
 недопустимое слово имеет ровно одну максимальную подцепь нечётной
 длины.
\end{problem}


\begin{problem}
Пусть  $L$ --- язык над алфавитом $A$, и $A'$ --- новый алфавит,
полученный из $A$  добавлением одной буквы. Пусть $L'$ --- язык
над алфавитом $A'$,  в котором запретными являются все запретные
слова языка $L$. Докажите формулу
$$
  L'(x) = \frac{\d 1}{\d \frac{1}{L(x)} - x }.
$$
\end{problem}

\begin{problem}
Язык $W$ называется\/ \emph{свободным произведением} языков $L$ и $L'$ над
непересекающимися алфавитами $A$ и $A'$, если алфавит языка $W$ есть
объединение алфавитов $A$ и $A'$, а множество запретных слов --- объединение
множеств запретных слов языков $L$ и $L'$. Выразите ряд размеров свободного
произведения $W$ через ряды размеров языков $L$ и $L'$.
\end{problem}

\begin{problem}
\label{kos_dual}
 Предположим, что множество запретных слов языка
$L$ содержит только слова из двух букв. Рассмотрим другой язык
${M}$ над тем же алфавитом, в котором запретными являются те и
только те двухбуквенные слова, которые не являются запретными в
языке $L$. Докажите равенство
$$
       L(x) M (-x) = 1.
$$
\end{problem}


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



\begin{problem}
Докажите, что свободное множество из $m$ слов длины $d$ в алфавите
из $n=kd$ букв существует в том и только том случае, когда $m \le
k^d (d-1)^{d-1}$ (ср. задачу~\ref{n=kd}), если

 a) $d=2$;  \qquad   б) $d=3$;  \qquad   в) $d >3$.
\end{problem}


\begin{definition}
Язык называется \emph{$d$-определённым}, если наибольшая из длин его запретных
слов равна~$d$. 2-определённый язык называется\/ \emph{квадратичным}.
\end{definition}

\begin{problem}
Квадратичные языки $L$ и $M$ из задачи~\ref{kos_dual} называются\/
\emph{двойственными} друг к другу (обозначение: $M=L^!$).

a) Докажите, что $(L^!)^! = L$.

б) Найдите $(L_1 + L_2)^!$.

в) Опишите $(L_1 \cdot L_2)^!$.
\end{problem}


\begin{problem}
Пусть $L$ --- $d$-определённый язык. Определим новый язык $L^{(n)}$, в котором
алфавитом являются все допустимые слова языка $L$ длины $n$, а допустимые слова
--- все допустимые слова языка $L$, длина которых делится на $n$ (выраженные
через новые буквы).

a) Докажите, что язык $L^{(n)}$ задаётся конечным набором
запретных слов.

б) Всегда ли язык  $L^{(n)}$ является $d$-определённым?

в) При каком наименьшем $n$ язык $L^{(n)}$ гарантированно является
квадратичным или свободным (вне зависимости от выбора
$d$-определённого языкам $L$)?
\end{problem}

\begin{problem}
\label{quadr_graph}
 Для любого квадратичного языка $L$ над
алфавитом $x_1, \dots, x_n $ определим ориентированный граф
$\Gamma_L$ следующим образом: его вершины --- $n$ точек,
помеченные буквами $x_1, \dots, x_n$, а ребро (стрелка) $x_i \to
x_j$ проводится в том и только том случае, когда $x_ix_j$ ---
разрешённое слово. Обозначим через $a_k$ количество допустимых
слов из $k$ букв. Докажите, что

а) язык $L$ конечный в том и только том случае, когда в графе
$\Gamma_L$ нет циклов;

b) язык $L$ имеет полиномиальный рост (т.~е. существуют два
ненулевых многочлена $p,q$ одной и той же степени $d$ с
положительным старшим коэффициентом такие, что $p(k) \ge a_k \ge
q(k)$ для всех $k\ge 0$) в том и только том случае, когда в графе
$\Gamma_L$ есть цикл, но нет пересекающихся циклов;

c) язык $L$ имеет экспоненциальный рост (т.~е. для некоторых
$c_1>c_2>1$ и для всех $k$ выполняются неравенства $c_1^k \ge a_k
\ge c_2^k $) тогда и только тогда, когда в графе $\Gamma_L$ есть
хотя бы два пересекающихся цикла.
\end{problem}

\begin{problem}
Пусть $L$ и $L^!$ --- пара двойственных квадратичных языков.
Возможно ли, что оба они имеют экспоненциальный рост?
\end{problem}


\begin{problem}
Для любого $d$-определённого  языка $L$ над алфавитом $x_1, \dots,
x_n $ определим ориентированный граф $\Gamma_L$ следующим образом:
его вершины помечены всеми допустимыми словами длины $d-1$,  а
ребро  (стрелка) $v \to w$ проводится  в том и только том случае,
когда при умножении  слова $v$ на некоторую букву $x_i$ получается
допустимое слово, последние $d-1$ букв которого составляют слово
$w$. Докажите все три свойства a), b), c) из
задачи~\ref{quadr_graph} для построенного графа $\Gamma_L$.
\end{problem}






\begin{definition}
Пусть $M$ --- некоторое множество слов над алфавитом $A$. Слова
$u$ и $v$ (над тем же алфавитом) называются\/
\emph{$M$-эквивалентными}, если для любого слова $w$ слова $uw$ и
$vw$ либо оба принадлежат $M$, либо оба не принадлежат $M$.
Множество $M$ называется\/ \emph{регулярным}, если найдётся такое
натуральное число $n$, что в любом множестве из $n$ слов найдутся
два $M$-эквивалентных друг другу слова.
\end{definition}

\begin{problem}
Докажите, что множество допустимых слов любого языка регулярно.
\end{problem}

\begin{definition}
\emph{Конечным автоматом} над алфавитом $A$ называется
ориентированный граф $\Gamma$ с конечным множеством вершин $V$,
причём

\noindent a) стрелки помечены буквами алфавита $A$, причём для
любой буквы $a\in A$ из каждой вершины выходит ровно одна стрелка,
помеченная $a$;

\noindent b) выделены \emph{начальная вершина} $v_0\in V$ и
множество \emph{принимающих вершин} $W\subseteq V$.

Будем воспринимать каждое слово над алфавитом $A$ как инструкцию
для путешествия по стрелкам конечного автомата $(\Gamma,v_0,W)$:
начинаем с начальной вершины, идём из неё по стрелке, помеченной
первой буквой слова, дальше идём по стрелке, помеченной второй
буквой, и т.д. Мы говорим, что автомат \emph{принимает} слово,
если соответствующий слову путь заканчивается в принимающей
вершине.
\end{definition}

\begin{problem}
a) Докажите, что для любого регулярного множества $M$ существует
конечный автомат, принимающий слова из $M$ и никаких больше.

b) Докажите, что для любого конечного автомата множество
принимаемых им слов регулярно.
\end{problem}


\begin{problem}
Докажите, что для любого регулярного множества $M$ его ряд
размеров может быть записан в виде частного двух многочленов.
\end{problem}

\begin{problem}
Пусть $M_{ w}$ --- множество всех допустимых слов языка $L$,
оканчивающихся на фиксированное подслово $w$.  Докажите, что ряд
размеров множества $M_{ w}$ представим в виде частного двух
многочленов.
\end{problem}


\bigskip

(До промежуточного финиша были предложены части 1--5,
после промежуточного финиша добавлены части 6--8.)

\end{document}
