main.tex

\documentclass[12pt,a4paper]{article}
\usepackage{../.tex/mcs-notes}
\usepackage{todonotes}
% \usepackage{multicol}
\usepackage{float}

\settitle
{Теоретическая информатика.}
{\href{https://users.math-cs.spbu.ru/~okhotin/}{А.С. Охотин},
Э.А. Гирш и
Д.О. Соколов}
{computer-science/main.pdf}
\date{}

% \DeclareMathOperator{\Quot}{Quot}
% \DeclareMathOperator*{\osc}{osc}
% \DeclareMathOperator{\sign}{sign}
% \DeclareMathOperator{\const}{const}
% \DeclareMathOperator{\grad}{grad}
% \newcommand{\eqdef}{\mathbin{\stackrel{\mathrm{def}}{=}}}
% \newcommand{\True}{\mathrm{True}}
% \newcommand{\False}{\mathrm{False}}
\newcommand{\Id}{\mathrm{Id}}
% \renewcommand{\Re}{\mathrm{Re}}
% \renewcommand{\Im}{\mathrm{Im}}
\newcommand{\spacesymbol}{\ensuremath{\text{\textvisiblespace}}}
\newcommand{\RE}{\mathrm{RE}}
\newcommand{\const}{\mathrm{const}}
\newcommand{\VALC}{\mathrm{VALC}}
\newcommand{\DTime}{\mathrm{DTime}}
\newcommand{\NTime}{\mathrm{NTime}}
\newcommand{\Pclass}{\mathrm{P}}
\newcommand{\NPclass}{\mathrm{NP}}
\newcommand{\Ptilde}{\widetilde{\mathrm{P}}}
\newcommand{\NPtilde}{\widetilde{\mathrm{NP}}}
\newcommand{\BH}{\mathrm{BH}}
\newcommand{\BHtilde}{\widetilde{\mathrm{BH}}}
\newcommand{\CURCUITSAT}{\mathrm{CURCUIT\_SAT}}
\newcommand{\CURCUITSATtilde}{\widetilde{\mathrm{CURCUIT\_SAT}}}

\begin{document}
    \maketitle

    \listoftodos[TODOs]

    \tableofcontents

    \vspace{2em}
    Литература:
    \begin{itemize}
        \item \dots
    \end{itemize}

    Страницы курса:
    \begin{itemize}
        \item \href{https://users.math-cs.spbu.ru/~okhotin/teaching/tcs_fl_2021/}{Часть курса}, прочитанная А.С. Охотиным.
    \end{itemize}
    
    \section{Вычислимость}

    \begin{definition}
        \emph{Машина Тьюринга} --- это реализация понятия вычисления. Она заключается в том, что имеется бесконечная в обе стороны клетчатая лента с записанным на ней конечным словом (по букве на клетку) --- входные данные вычисления --- и головка --- вычисляющий аппарат, которая в каждый момент времени смотрит на какую-то клетку ленты и имеет в себе некоторое внутреннее состояние вычислений. Каждым своим действием она читает символ в клетке, на которую смотрит, и в зависимости от прочитанного символа и внутреннего состояния в данный момент она пишет в клетку, на которую смотрит новый символ, стирая старый, переходит на новую клетку и меняет внутренне состояние.

        Формально машина Тьюринга $M$ --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$ --- (конечного) алфавита входных данных,
            \item рабочего алфавита $\Gamma$ --- (конечного) алфавита, над которым мы работаем, что $\Gamma \supseteq \Sigma \sqcup \{\spacesymbol\}$,
            \item конечного множества (внутренних) состояний $Q$,
            \item начального состояния $q_0 \in Q$,
            \item функции переходов $\delta: Q \times \Gamma \to Q \times \Gamma \times \{-1; +1\}$
            \item и дополнительных объектов и условий в зависимости от предназначения машины.
        \end{itemize}
        Входными данными программы является конечная строка $s_1 \dots s_l$, которая превращается в запись $(a_i)_{i \in \ZZ}$ на ленте по правилу
        \[
            a_i
            = \begin{cases}
                s_{i+1}& \text{ если } 0 \leqslant i \leqslant l-1,\\
                \spacesymbol& \text{ иначе.}
            \end{cases}
        \] 
        Состояние каждого момент вычисления --- это совокупность
        \begin{itemize}
            \item состояния ленты $(a_i)_{i \in \ZZ}$, где $a_i \in \Sigma$ и все $a_i$ кроме конечного числа элементов являются пробелом \spacesymbol,
            \item положения головки $n \in \ZZ$ на ленте и
            \item состояния головки $q \in Q$.
        \end{itemize}
        Состояние начального момента вычислений образуется из
        \begin{itemize}
            \item состояния ленты, полученного из входных данных,
            \item положения головки по умолчанию $n = 0$
            \item начального состояния головки $q_0$.
        \end{itemize}
        Каждым шагом состояние $((a_i)_{i \in \ZZ}, n, q)$ заменяется на состояние $((a'_i)_{i \in \ZZ}, n', q')$, где $a'_i = a_i$ для всех $i \in \ZZ \setminus \{n\}$ и
        \[
            (q', a'_n, n'-n) := \delta(q, a_n).
        \]

        Далее есть два вида предназначений машины:
        \begin{enumerate}
            \item \textbf{Распознование свойства.} В этом случае мы хотим уметь распознавать разные конечные строки, т.е. чтобы машина отвечала ``да'' или ``нет'' на вопрос ``Лежит ли эта строка в заданном семействе?''. В таком случае у машины выделяются \emph{принимающее состояние} $q_{acc} \in Q$ и \emph{отвергающее состояние} $q_{rej} \in Q$, и когда машина переходит в одно из этих двух состояний, вычисления прекращаются. В таком случае $\delta(q, a)$ должно быть не определено в случае $q \in \{q_{acc}; q_{rej}\}$.
            \item \textbf{Вычисление функции.} В этом случае мы хотим вычислять значение некоторой функции $M: \Sigma^* \to \Sigma^*$, т.е. чтобы машаина после некоторого количества действий говорила ``Готово.'' и оставляла на ленте конечное слово в том же формате, в котором производится ввод. В таком случае у машины выделяется \emph{состояние останова} $q_{halt} \in Q$, и когда машина переходит в это состояние, вычисления прекращаются, а на ленте должно остаться слово в правильном формате. В таком случае $\delta(q, a)$ должно быть не определено в случае $q = q_{halt}$.
        \end{enumerate}
    \end{definition}

    \begin{remark*}
        Фактически множество результатов работы машины состоит из переходов в одно из терминальных состояний ($q_{acc}$, $q_{rej}$ или $q_{halt}$) и попадания в ``вечный цикл''.
    \end{remark*}

    \begin{theorem}
        В определении машина Тьюринга множество возможных смещений головки $\{+1; -1\}$ можно сменить на некоторое $S \subseteq \ZZ$.
        \begin{enumerate}
            \item Тогда если $S$ конечно и всякое целое число представляется в виде суммы хотя бы одного значения (возможно, с повторами) из $S$, то определение получается равносильным.
            \item То же самое верно для всякого $S$ (не обязательно конечного).
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        \begin{enumerate}
            \item Действительно, пусть у нас имеется машина с множеством возможных сдвигов $S_1$, а у нас есть множество возможных сдвигов $S_2$, что всякое число из $S_1$ представляется в виде суммы некоторых (хотя бы одного и, возможно, с повторениями) членов из $S_2$. Тогда для всякой перехода между состояниями $q_1 \to q_2$ можно создать такие фальшсостояния, что смещение на значение из $S_1$ будет заменено на несколько смещений на значения из $S_2$ с тем же итогом. Таким образом мы можем всякую машину на $S_1$ поменять на машину на $S_2$ и большим числом состояний.
        
                Таким образом множества смещений $S_1$ и $S_2$ реализуют равносильные модели, если всякое значение из $S_1$ расскладывается в сумму значений $S_2$ и наоборот. При для $S_1 = \{+1; -1\}$ переход $S_2 \to S_1$ очевиден, а переход $S_1 \to S_2$ означает, что $1$ и $-1$ раскладываются в суммы некоторых чисел из $S_2$, что равносильно разложимости всякого целого.

            \item Несложно понять, что в каждой конкретной машине Тьюринга множество $Q \times \Sigma$ конечно, а значит $S$ можно заменить на конечное подмножества, что задача для данной машины не изменится.
        \end{enumerate}
    \end{proof}

    \begin{corollary}
        Вместо $\{+1; -1\}$ для удобства можно также подразумевать $\{+1; 0; -1\}$.
    \end{corollary}

    \begin{remark*}
        В данный момент мы будем рассматривать только задачу распознавания свойства.
    \end{remark*}

    \begin{definition}
        \emph{Язык машины} $M$ или \emph{язык, распознаваемый машиной $M$,} --- это множество $L(M) \subseteq \Sigma^*$ входных строк, которые машина принимает. Т.е. это множество всех конечных строк $w \in \Sigma^*$ таких, что машина $M$ на входе $w$ завершает работу и принимает данный вход.

        Язык, распознаваемый какой-нибудь машиной, называется \emph{рекурсивно-перечислимым}.

        Язык, распознаваемый какой-нибудь машиной, которая останавливается на любом входе, называется \emph{рекурсивным}.
    \end{definition}

    \begin{example}
        Пусть $\Sigma = \{a; b\}$, $L = \{a^nb ^n\}_{n \geqslant 0}$. Тогда $L$ распознаётся машиной Тьюринга (которая причём останавливается на всяком входе!).

        Действительно, давайте напишем машину, которая будить ездить из одного конца нашей строки в другую и стирать $a$ справа и $b$ слева, и, если получит пустую строку, примет вход, а если поймет, что в какой-то момент получается что-то неправильное, то отвергнет вход. Формально, возьмём $Q = \{q_0; q_1; q_2; q_3; q_{acc}; q_{rej}\}$ и $\Gamma = \{a; b; \spacesymbol\}$, а функцию перехода опишем следующей таблицей:
        \begin{table}[H]
            \centering
            \begin{tabular}{c||c|c|c}
                $Q\backslash\Gamma$& $a$& $b$& $\spacesymbol$\\
                \hline
                \hline
                $q_0$& $q_1$, \spacesymbol, $+1$& $q_{rej}$& $q_{acc}$\\
                \hline
                $q_1$& $q_1$, $a$, $+1$& $q_1$, $b$, $+1$& $q_2$, \spacesymbol, $-1$\\
                \hline
                $q_2$& $q_{rej}$& $q_3$, \spacesymbol, $-1$& $q_{rej}$\\
                \hline
                $q_3$& $q_3$, $a$, $-1$& $q_3$, $b$, $-1$& $q_0$, \spacesymbol, $+1$\\
            \end{tabular}
        \end{table}
        Т.е. во с помощью $q_0$ и $q_2$ мы стираем $a$ слева и $b$ справа соответственно, а с помощью $q_1$ и $q_2$ перемещаемя до конца вправо и влево соответственно.
    \end{example}

    \begin{theorem}
        Есть язык, нераспознаваемый никакой машиной Тьюринга.
    \end{theorem}

    \begin{proof}
        Несложно видеть, что для всякого конечного непустого алфавита $\Sigma$ количество $|\Sigma^*|$ конечных строк над $\Sigma$ счётно, а значит языков над $\Sigma$ континуум. При этом машин Тьюринга с входным алфавитом $\Sigma$ счётное число. Значит почти все языки не распознаются машинами Тьюринга.

        При этом есть довольно простые конкретные примеры нераспознаваемых языков.
    \end{proof}

    \begin{definition}
        \emph{Запись $\sigma(M)$ машины Тьюринга $M$} --- это конечной битовая строка, созданная по следующему правилу. Пусть у машины $M = (\Sigma, \Gamma, Q, q_0, \delta, q_{acc}, q_{rej})$
        \begin{itemize}
            \item $\Sigma = \{a_1; \dots; a_l\}$,
            \item $\Gamma = \Sigma \cup \{a_{l+1}; \dots; a_m\}$, где причём $a_m = \spacesymbol$,
            \item $Q = \{q_0; \dots; q_{n-1}\}$, где причём $q_{acc} = q_{n-2}$, $q_{rej} = q_{n-1}$.
        \end{itemize}
        Тогда запишем всё в унарной системе счисления, т.е. (всякий абстрактный) массив числовых данных будет храниться в виде последовательностей единиц, длины которых будут равняться соответствующим значениям массиве, разделённых нулями. Тогда машина $M$ будет записана строкой
        \[\sigma(M) := 1^l\, 0\, 1^m\, 0\, 1^n\, 0 \prod_{\delta(q_i, a_j) = q_{i'}, a_{j'}, d} 1^i\, 0\, 1^j\, 0\, 1^{i'}\, 0\, 1^{j'}\, 0\, 1^{d+1}\]
        (где умножение, безусловно, --- конкатенация, а $\prod$ --- конкатенация нескольких строк).
    \end{definition}

    \begin{definition}
        Языки $L_0$ и $L_1$ --- это
        \[
            L_0 := \{\sigma(M) \mid \sigma(M) \notin L(M)\}
            \qquad \text{ и } \qquad
            L_1 := \{\sigma(M) \mid \sigma(M) \in L(M)\}.
        \]
    \end{definition}

    \begin{theorem}\ 
        \begin{enumerate}
            \item $L_0$ не рекурсивно-перечислимый.
            \item $L_1$ рекурсивно-перечислимый.
            \item $L_1$ не рекурсивный.
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        \begin{enumerate}
            \item Предположим противное, т.е. есть машина $M$, распознающая $L_0$. Тогда если $M$ принимает $\sigma(M)$, то $\sigma(M) \in L(M)$, но тогда $\sigma(M) \notin L$. Если же $M$ не принимает $\sigma(M)$, то $\sigma(M) \notin L(M)$, но тогда $\sigma(M) \in L$. Противоречие наподобие парадокса Рассела. Значит нет никакой машины, распознающей $L_0$.
            \item Неформально опишем машину, которая будет распознавать $L_1$. Идея машины заключается в том, что получая на вход $\sigma(M)$, после этого запсанного кода машины $M$ она запишет код начального состояния $q_0$ машины $M$, а затем код $\sigma(M)$ как входную строчку для $M$. После этого она начнёт моделировать работу машины $M$ на входе $\sigma(M)$. Состояние головки будет писаться перед клеткой, на которую головка смотрит. Если места слева будет не хватать, то вся запись будет просто сдвигаться вправо.
            \item Покажим, что всякая машина, распознающая $L_1$ зацикливается при некотором входе. Предположим противное, т.е. есть машина $\widetilde{M}$, которая распознаёт $L_1$ и всегда остансавливается. Тогда построим $\widehat{M}$ по алгоритму:
                \begin{itemize}
                    \item Проверить правда ли, что на было подано некоторое $\sigma(M)$. Если нет, то отвергнуть.
                    \item Работать как $\widetilde{M}$ на $\sigma(M)$. Если $\widetilde{M}$ принимает, то отвергнуть. Если отвергает --- принять.
                \end{itemize}
                Тогда $\widehat{M}$ распознаёт $L_0$ --- противоречие. Значит машины $\widetilde{M}$ не существует.
        \end{enumerate}
    \end{proof}
    
    \begin{theorem}
        Язык
        \[L_\varnothing := \{\sigma(M) \mid L(M) = \varnothing\}\]
        не рекурсивно-перечислимый.
    \end{theorem}

    \begin{proof}
        Предположим противное, т.е. есть машина $M_\varnothing$, которая распознаёт $L_\varnothing$. Тогда построим машину $M_0$ по следующему алгоритму.
        \begin{enumerate}
            \item Проверить правда ли, что на было подано некоторое $\sigma(M)$. Если нет, то отвергнуть.
            \item Построить $\sigma(M')$, где машина $M'$ работает по следующему алгоритму.
                \begin{itemize}
                    \item Стереть входную строку.
                    \item Написать $\sigma(M)$.
                    \item Запустить $M$.
                \end{itemize}
            \item Запустить $M_\varnothing$ на $\sigma(M')$.
        \end{enumerate}
        $M'$ принимает любую строку, если $M$ принимает $\sigma(M)$, отвергает любую строку, если $M$ отвергает $\sigma(M)$, и зацикливается, если $M$ зацикливается на $\sigma(M)$. Следовательно $M_\varnothing$ примет $\sigma(M')$ тогда и только тогда, когда $\sigma(M) \notin L(M)$. Таким образом $M_0$ распознаёт $L_0$.
    \end{proof}

    \begin{definition}
        Для всякого свойства $P$ языков можно определить язык
        \[L_P := \{\sigma(M) \mid \text{$L(M)$ обладает свойством $P$}\}.\]
        Можно считать, что свойство есть некоторое множество языков (т.е. подмножество $2^{\Sigma^*}$), а обладание свойством означает содержание в нём как в множестве.

        Свойство называется \emph{тривиальным}, если либо ни один рекурсивно-перечислимый язык, либо все рекурсивно-перечислимые языки обладают этим свойством.
    \end{definition}

    \begin{example}\ 
        \begin{enumerate}
            \item Если $P$ --- это ``непустота'', то
                \[L_P := \{\sigma(M) \mid L(M) \neq \varnothing\}.\]
                Такой язык рекурсивно-перечислим. Но нерекурсивно.
            \item
                \[L_P := \{\sigma(M) \mid \text{$M$ отвергает конечное число программ на C++}\}.\]
            \item
                \[L_P := \{\sigma(M) \mid L(M) = L_0\}.\]
                Как мы уже знаем $L_P = \varnothing$, т.е. данное свойство тривиально.
        \end{enumerate}
    \end{example}

    \begin{theorem}[Райса]
        Всякое нетривиальное свойство нерекурсивно. Точнее для всякого нетривиального свойства $P$ язык $L_P$ нерекурсивен.
    \end{theorem}

    \begin{proof}
        Пусть дано нетривиальное свойство $P \subseteq 2^{\Sigma^*}$ рекурсивно-перечислимых языков. Предположим противное: есть машина $M_P$, которая распознаёт $L_P$ (не зацикливается и принимает только язык $L_P$).

        Предположим, что $\varnothing \notin P$. Тогда есть машина $\widehat{M}$, что $L(\widehat{M}) \in P$. Тогда построим машину Тьюринга $M_1$, принимающую в себя $\sigma(M)$ некоторой машины Тьюринга $M$, со следующим алгоритмом:
        \begin{enumerate}
            \item Построить машину Тьюринга $\widetilde{M}$ по следующему описанию.
                \begin{enumerate}
                    \item Сохранить вход $w$.
                    \item Запустить $M$ на $\sigma(M)$.
                    \item Если отвергнет, зациклиться. Если примет, запустить $\widehat{M}$ на $w$.
                \end{enumerate}
            \item Запустить $M_P$ на $\sigma(\widetilde{M})$.
        \end{enumerate}
        Заметим, что если $\sigma(M) \notin L(M)$, то машина $\widetilde{M}$ зацикливается на любом входе, т.е. $L(\widetilde{M}) = \varnothing$. Иначе $\widetilde{M}$ совпадает с $\widehat{M}$, т.е. $L(\widetilde{M}) = L(\widehat{M})$. Таким образом
        \[L(\widetilde{M}) \in P \quad \Longleftrightarrow \quad \sigma(M) \in L(M).\]
        Таким образом ответ $M_p$ на входе $\sigma(\widetilde{M})$ есть ответ на вопрос принадлежности $\sigma(M)$ множеству $L(M)$. Таким образом $M_1$ не зацикливается и распознаёт язык $L_1$, что противоречит ранее доказанным утверждениям.

        Теперь предположим $\varnothing \in P$. Тогда есть машина $\widehat{M}$, что $L(\widehat{M}) \notin P$. По аналогии можно построить машину, которая распознаёт $L_0$.
    \end{proof}

    \section{Формальные зыки и автоматы}

    \begin{definition}
        \emph{Алфавит} $\Sigma$ --- фиксированный (контекстом) набор элементов (\emph{символов}). Мы будем рассматривать только конечные алфавиты.
        
        \emph{Строка} --- (если не оговорено обратное, конечная) последовательность символов из алфавита. Строки обозначаются либо просто как переменные, т.е. $w$, либо в виде
        \[a_1 \dots a_n,\]
        где $a_i$ --- символы из алфавита $\Sigma$. Строка, где $n=0$, называется \emph{пустой строкой} и обозначается $\varepsilon$. Значение $n$ называется длиной строки $w$ и обозначается $|w|$. Количество вхождение некоторого символа $a$ (т.е. количество индексов $i$, что $a_i = a$) обозначается $|w|_a$. Множество всех строк обозначается $\Sigma^*$.
        
        \emph{Конкатенация} --- бинарная операция на строках, определяемая по правилу
        \[(a_1 \dots a_n, b_1 \dots b_m) \mapsto a_1 \dots a_n b_1 \dots b_m.\]
        Конкатенация строк $u$ и $v$ обозначается $uv$ или $u \cdot v$. Множество строк с операцией конкатенации и выделенной $\varepsilon$ образуют моноид.

        \emph{Обращение строки} --- унарная операция на строках, определяемая по правилу
        \[a_1 \dots a_n \mapsto a_n \dots a_1.\]
        Обращение строки $w$ обозначается $w^R$.

        \emph{Язык} --- множество строк, т.е. подмножество $\Sigma^*$.
    \end{definition}

    \begin{definition}
        \emph{Детерминированный конечный автомат} (также ``ДКА'' или ``DFA'') $A$ --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item начального состояния $q_0 \in Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times \Sigma \to Q$.
        \end{itemize}
        Входными данными является конечная строка $w = s_1 \dots s_n$. Состояние вычисления после $k$ шагов --- это некоторое состояние автомата $q_k \in Q$. Соответственно, начальное состояние вычисления (оно же состояние вычисления после $0$ шагов) --- начальное состояние автомата $q_0$. Каждым шагом состояние $q_k$ заменяется на $q_{k+1} := \delta(q_k, s_{k+1})$. Т.е. формально вычисление --- это последовательность состояний $(q_k)_{k=0}^n$, где
        \begin{itemize}
            \item $q_0$ --- начальное состояние автомата,
            \item $q_{k+1} := \delta(q_k, s_{k+1})$.
        \end{itemize}
        Состояние $q_n$ называется \emph{результатом вычисления}. Также говорят, что автомат принимает строку $w$, если $q_n \in F$, и отвергает в ином случае.

        \emph{Язык автомата} $A$ или \emph{язык, распознаваемый автоматом} $A$, --- это множество $L(A)$ всех строк, распознаваемых (принимаемых) автоматом $A$. Язык, распознаваемый хоть каким-нибудь автоматом называется \emph{регулярным}.

        Также в качестве удобства обозначений определим функцию $\delta^*$ на $Q \times \Sigma^*$ как
        \[\delta^*(q, a_1 \dots a_n) := \delta^*(\dots \delta(q, a_1), \dots, a_n),\]
        т.е. $\delta^*$ задаётся рекурсивно как
        \[\delta^*(q, \varepsilon) = q, \qquad \delta^*(q, aw) = \delta^*(\delta(q, a), w).\]
        Иногда мы будем писать $\delta$, подразумевая $\delta^*$.
    \end{definition}

    \begin{remark*}
        Детерминированные конечные автоматы удобно изображать в виде ориентированного графа. Пусть $Q$ --- вершины графа, и из каждой вершины $q$ ведёт по $|\Sigma|$ рёбер: ребро из $q$ с меткой $s$ (для всякого $s \in \Sigma$) ведёт в $\delta(q, s)$. Также небольшой стрелочкой ведущей из ниоткуда в $q_0$ удобно помечать $q_0$ как начальную вершину, и удобно обвести каждую вершину из $F$, чтобы пометить её как принимающую. 
    \end{remark*}

    \begin{remark*}
        Несложно видеть, что
        \[L(A) = \{w \in \Sigma^* \mid \delta^*_A(q_{A, 0}, w) \in F_A\}.\]
        Это также значит, что $w \in L(A)$ тогда и только тогда, когда при проходе в графе $A$ по пути, соответствующему слову $w$, мы попадаем в принимающее состояние. Говоря иначе, есть некоторая последовательность состояний $q_0, \dots, q_n$, что
        \begin{itemize}
            \item $n = |w|$,
            \item $q_0 = q_{A, 0}$ --- начальное состояние автомата,
            \item $q_{k+1} = \delta_A(q_k, a_{k+1})$,
            \item $q_n \in F_A$.
        \end{itemize}
    \end{remark*}

    \begin{theorem}
        Язык $L := \{a^n b^n\}_{n \in \NN}$ нерегулярен.
    \end{theorem}

    \begin{proof}
        Предположим имеется ДКА $A$, что $L(A) = L$. Заметим, что тогда строка $a^{|Q|} b^{|Q|} \in L$. Пусть вычисление этой строки имеет вид $q_0 \dots q_{|Q|} \dots$ (понятно, что $q_{|Q|}$ --- состояние вычисления после последней буквы $a$). По принципу Дирихле есть из состояний $q_0$, \dots, $q_{|Q|}$ есть два совпадающих; пусть это будут $q_i$ и $q_j$ ($i < j$). Тогда покажем, что $a^{|Q| - (j-i)} b^{|Q|}$ тоже распознаётся (хотя не должна). Заметим, что процесс вычисления букв $a$ будет иметь вид
        \[q_0 \dots q_i = q_j \dots q_{|Q|}.\]
        Таким образом состояние после прочтения последней буквы $a$ будет тем же, а значит состояние после прочтения всей строки тоже будет тем же, а значит принимающим.
    \end{proof}

    \begin{definition}
        Недетерминированный конечный автомат (также ``НКА'' или ``NFA'') --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item множества начальных состояния $S \subseteq Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times \Sigma \to 2^Q$.
        \end{itemize}
        Входными данными является конечная строка $w = s_1 \dots s_n$. Состояние вычисления после $k$ шагов --- это некоторое множество состояний автомата $S_k \in Q$. Соответственно, начальное состояние вычисления (оно же состояние вычисления после $0$ шагов) --- множество начальных состояние автомата $S_0 = S$. Каждым шагом состояние $S_k$ заменяется на $S_{k+1} := \bigcup_{q \in S_k} \delta(q, s_{k+1})$. Т.е. формально вычисление --- это последовательность множеств состояний $(S_k)_{k=0}^n$, где
        \begin{itemize}
            \item $S_0 = S$ --- начальное состояние автомата,
            \item $S_{k+1} := \bigcup_{q \in S_k} \delta(q, s_{k+1})$.
        \end{itemize}
        Множество состояний $S_n$ называется \emph{результатом вычисления}. Также говорят, что автомат принимает строку $w$, если $S_n \cap F \neq \varnothing$, и отвергает в ином случае.

        \emph{Язык автомата} $A$ или \emph{язык, распознаваемый автоматом} $A$, --- это множество $L(A)$ всех строк, распознаваемых (принимаемых) автоматом $A$. Язык, распознаваемый хоть каким-нибудь автоматом называется \emph{регулярным}.

        Также в качестве удобства обозначений определим функцию $\delta^*$ на $2^Q \times \Sigma^*$ рекурсивно как
        \[
            \delta^*(T, w) = \bigcup_{q \in T} \delta^*(q, w),
            \qquad
            \delta^*(\{q\}, \varepsilon) = \{q\},
            \qquad
            \delta^*(\{q\}, aw) = \delta^*(\delta(q, a), w).
        \]
        Иногда мы будем писать $\delta$, подразумевая $\delta^*$.
    \end{definition}

    \begin{remark*}
        Недетерминированные конечные автоматы удобно изображать в виде ориентированного графа. Пусть $Q$ --- вершины графа, и из каждой вершины $q$ ведёт некоторое количество рёбер: по ребру из $q$ с меткой $s$ (для всякого $s \in \Sigma$) ведёт в каждую вершину из $\delta(q, s)$. Также небольшими стрелочками ведущими из ниоткуда в каждую вершину из $S$ удобно помечать $S$ как множество начальных вершин, и удобно обвести каждую вершину из $F$, чтобы пометить её как принимающую. 
    \end{remark*}

    \begin{remark*}
        Несложно видеть, что $w \in L(A)$ тогда и только тогда, когда есть путь в графе $A$, соответствующий строке $w$, что конечное состояние является принимающим. Говоря иначе, есть некоторая последовательность состояний $q_0, \dots, q_n$, что
        \begin{itemize}
            \item $n = |w|$,
            \item $q_0 \in S_A$,
            \item $q_{k+1} \in \delta_A(q_k, a_{k+1})$,
            \item $q_n \in F_A$.
        \end{itemize}
        С другой стороны это также равносильно тому, что $\delta^*_A(S_A, w) \in F_A$.
    \end{remark*}

    \begin{theorem}
        У всякого недетерминированного автомата $A$ есть детерминированный автомат $A'$, что $L(A') = L(A)$.
    \end{theorem}

    \begin{proof}
        Пусть дано, что $A = (\Sigma, Q, S, \delta, F)$. Тогда определим
        \[A' = (\Sigma, 2^Q, S, \delta', \{T \subseteq Q \mid T \cap F \neq \varnothing\}),\]
        где $\delta'$ определяется по правилу
        \[\delta'(T, s) := \delta(T, s) = \bigcap_{q \in T} \delta(q, s).\]

        Проще говоря, $A'$ имитирует $A$, запоминая в каком множестве состояний мы находимся в каждый момент и эмулируя правильный переход к новому множеству состояний. Формально говоря, несложно показать по индукции по $|w|$, что множество состояний автомата $A$ после прочтения слова $w$ является состоянием автомата $A'$ после прочтения того же слова $w$.
    \end{proof}

    \begin{remark}
        Можно на языках ввести следующие операции.
        \begin{itemize}
            \item $K \cup L$, $K \cap L$, $K \triangle L$, $\overline{L}$ --- стандартные операции на множествах.
            \item Конкатенация. $KL = K \cdot L := \{uv \mid u \in K \wedge v \in L\}$.
            \item Конкатенация нескольких копий. $L^k := L \cdot \dots \cdot L$. $L^0 = \{\varepsilon\}$.
            \item Конкатенация любого конечного числа копий или звёздочка Клини. $L^* = \bigcup_{k=0}^\infty L^k$.
        \end{itemize}

        В таком случае $(2^{\Sigma^*}, {\cup}, {\cdot}, \varnothing, \{\varepsilon\})$ --- полукольцо.
    \end{remark}

    \subsection{Регулярные выражение и равносильность конечным автоматам}

    \begin{definition}
        Рекурсивно определим понятие \emph{регулярного выражения}.
        \begin{itemize}
            \item $\varnothing$ --- регулярное выражение.
            \item $a$, где $a \in \Sigma$, --- регулярное выражение.
            \item $(\varphi \psi)$, $(\varphi | \psi)$ и $\varphi^*$, где $\varphi$ и $\psi$ есть регулярные выражения, --- регулярные выражения.
        \end{itemize}
        Множество регулярных выражений над алфавитом $\Sigma$ обозначается $\RE(\Sigma)$.
        
        Теперь рекурсивно определим \emph{язык регулярного выражения}.
        \begin{itemize}
            \item $L(\varnothing) = \varnothing$.
            \item $L(a) = \{a\}$.
            \item $L(\varphi \psi) = L(\varphi) L(\psi)$.
            \item $L(\varphi | \psi) = L(\varphi) \cup L(\psi)$.
            \item $L(\varphi^*) = L(\varphi)^*$.
        \end{itemize}
    \end{definition}

    \begin{theorem}
        Язык распознаётся конечным автоматом тогда и только тогда, когда задаётся регулярным выражением.
    \end{theorem}

    \begin{definition}
        Недетерминированный конечный автомат с $\varepsilon$-переходами (также ``$\varepsilon$-НКА'' или ``$\varepsilon$-NFA'') --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item множества начальных состояния $S \subseteq Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$.
        \end{itemize}
        \emph{$\varepsilon$-замыканием} состояния $q$ называется множество состояний
        \[E(q) := \{p \mid \exists k \in \NN\colon \exists q_0, \dots, q_k \in Q\colon q_0 = q \wedge q_k = p \wedge \forall i = 1, \dots, k\; q_i = \delta(q_{i-1}, \varepsilon)\}.\]
        Также по аналогии $\varepsilon$-замыканием множества состояния $T$ называется множество состояний
        \[E(T) := \bigcup_{q \in T} E(q),\]
        откуда, в частности, получается ``рекурсивное определение''
        \[E(T) := T \cup \bigcup_{q \in T} E(\delta(q, \varepsilon)).\]
        Входными данными является конечная строка $w = s_1 \dots s_n$. Состояние вычисления после $k$ шагов --- это некоторое множество состояний автомата $S_k \in Q$. Соответственно, начальное состояние вычисления (оно же состояние вычисления после $0$ шагов) --- множество начальных состояние автомата $S_0 = E(S)$. Каждым шагом состояние $S_k$ заменяется на $S_{k+1} := \bigcup_{q \in S_k} E(\delta(q, s_{k+1}))$. Т.е. формально вычисление --- это последовательность множеств состояний $(S_k)_{k=0}^n$, где
        \begin{itemize}
            \item $S_0 = E(S)$ --- начальное состояние автомата,
            \item $S_{k+1} := \bigcup_{q \in S_k} E(\delta(q, s_{k+1}))$.
        \end{itemize}
        Множество состояний $S_n$ называется \emph{результатом вычисления}. Также говорят, что автомат принимает строку $w$, если $S_n \cap F \neq \varnothing$, и отвергает в ином случае.

        \emph{Язык автомата} $A$ или \emph{язык, распознаваемый автоматом} $A$, --- это множество $L(A)$ всех строк, распознаваемых (принимаемых) автоматом $A$. Язык, распознаваемый хоть каким-нибудь автоматом называется \emph{регулярным}.

        Также в качестве удобства обозначений определим функцию $\delta^*$ на $2^Q \times \Sigma^*$ рекурсивно как
        \[
            \delta^*(T, w) = \bigcup_{q \in T} \delta^*(q, w),
            \qquad
            \delta^*(\{q\}, \varepsilon) = E(\{q\}),
            \qquad
            \delta^*(\{q\}, aw) = \delta^*\left(\bigcup_{p \in E(q)} \delta(p, a), w\right).
        \]
        Иногда мы будем писать $\delta$, подразумевая $\delta^*$.
    \end{definition}

    \begin{remark*}
        Недетерминированные конечные автоматы с $\varepsilon$-переходами удобно изображать точно также как обычные НКА, но на стрелках (ориентированных рёбрах) переходов теперь можно писать и новодобавленный символ $\varepsilon$.
    \end{remark*}

    \begin{remark*}
        Несложно видеть, что $w \in L(A)$ тогда и только тогда, когда есть некоторое представление $w = s_1 \dots s_n$, где $s_i \in \Sigma \cup \{\varepsilon\}$, и некоторая последовательность состояний $q_0, \dots, q_n$, что
        \begin{itemize}
            \item $q_0 \in S_A$,
            \item $q_{k+1} \in \delta_A(q_k, s_{k+1})$,
            \item $q_n \in F_A$.
        \end{itemize}
        С другой стороны это также равносильно тому, что $\delta^*_A(S_A, w) \in F_A$.
    \end{remark*}

    \begin{lemma}
        Всякое регулярное выражение можно заменить на $\varepsilon$-НКА, порождающий тот же язык.
    \end{lemma}

    \begin{proof}
        Давайте построим для каждого регулярного выражения $\varepsilon$-НКА с ровно одним начальным состоянием и ровно одним принимающим состоянием. И будем мы это делать по рекурсивному построению регулярного выражения:
        \begin{itemize}
            \item Автомат для регулярного выражения $\varnothing$ будет состоять только из одного начального и одного принимающего состояний, не иметь других состояний и не иметь никаких переходов.
            \item Автомат для регулярного выражения $a$ ($a \in \Sigma$) будет состоять только из одного начального и одного принимающего состояний, не иметь других состояний и иметь единственный переход от начального состояния к принимающему по символу $a$.
            \item Автомат для регулярного выражения $\varphi \psi$ будет получаться проведением перехода по $\varepsilon$ от принимающего состояния $\varphi$ к начальному состоянию $\psi$. Соединённые состояния теряют свои роли (т.е. больше не являются принимающей и начальной соответственно).
            \item Автомат для регулярного выражения $\varphi | \psi$ будет получаться проведением переходов по $\varepsilon$ от начального состояния строимого автомата к начальным состояниям автоматов $\varphi$ и $\psi$ и переходов по $\varepsilon$ от принимающих состояний автоматов $\varphi$ и $\psi$ к принимающему состоянию строимого автомата. Начальные и принимающие состояния старых автоматов теряют свои роли.
            \item Автомат для регулярного выражения $\varphi*$ будет получаться проведением перехода по $\varepsilon$ от начального состояния строимого автомата к начальному состоянию автомата $\varphi$, перехода по $\varepsilon$ от принимающего состояния автомата $\varphi$ к начальному состоянию строимого автомата и перехода по $\varepsilon$ от начального состояния строимого автомата к принимающему состоянию строимого автомата. Начальные и принимающие состояния старого автомата теряют свои роли.
        \end{itemize}
        \todo[inline]{Картиночки.}
        Несложно видеть по индукции по построению выражения, что строимые автоматы, действительно, строят язык соответствующих регулярных выражений.
    \end{proof}

    \begin{lemma}
        Всякий $\varepsilon$-НКА можно заменить на НКА, порождающий тот же язык.
    \end{lemma}

    \begin{proof}
        Неформально говоря, мы хотим во всяком пути $s_1 \dots s_n$ произвести разбиение на несколько блоков вида $\varepsilon^k a$ (для некоторых $k \in \NN$ и $a \in \Sigma$) оканчивающееся на дополнительный блок вида $\varepsilon^k$ и заменить каждый (не дополнительный) блок на ровно один переход; дополнительный блок можно будет убрать при правильной замене множества принимающих состояний.

        Теперь формальное построение. Пусть дан $\varepsilon$-НКА $A = (\Sigma, Q, S, F, \delta)$. Будем строить НКА $A'$. $\Sigma$, $Q$ и $S$ оставим без изменений. Теперь определим новые $\delta'$ и $F'$. $\delta'$ определяется по правилу
        \[\delta'(q, a) := \bigcup_{p \in E(q)} \delta(p, a),\]
        а $F'$ определяется как
        \[F' := \{q \in Q \mid E(q) \cap F \neq \varnothing\}.\]
    \end{proof}

    \begin{definition}
        Недетерминированный конечный автомат с regex-переходами (также ``RE-НКА'' или ``RE-NFA'') --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item множества начальных состояния $S \subseteq Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times \RE(\Sigma) \to 2^Q$, что для всякого $q \in Q$ и всех $r \in RE(\Sigma)$ кроме, быть может, конечного множества $\delta(q, r) = \varnothing$.
        \end{itemize}
        Входными данными является конечная строка $w$. Входная строка принимается автоматом, если есть её разбиение на подстроки $w = u_1 \dots u_n$, последовательность регулярных выражений $r_1$, \dots, $r_n$ и последовательность состояний $q_0$, \dots, $q_n$, что
        \begin{itemize}
            \item $u_k \in L(r_k)$ для всех $k$,
            \item $q_0 \in S$,
            \item $q_{k+1} \in \delta(q_k, r_{k+1})$,
            \item $q_n \in F$.
        \end{itemize}

        \emph{Язык автомата} $A$ или \emph{язык, распознаваемый автоматом} $A$, --- это множество $L(A)$ всех строк, распознаваемых (принимаемых) автоматом $A$. Язык, распознаваемый хоть каким-нибудь автоматом называется \emph{регулярным}.
    \end{definition}

    \begin{remark*}
        Недетерминированные конечные автоматы с $\varepsilon$-переходами удобно изображать точно также как обычные НКА, но на стрелках (ориентированных рёбрах) переходов теперь можно писать не символы из $\Sigma$, а регулярные выражения из $\RE(\Sigma)$. Также по аналогии можно описать про существование пути в графе, но проще будет это вывести напрямик из уже данного определения.
    \end{remark*}

    \begin{remark*}
        В этом случае также можно написать рекурсивную формулу $\delta^*$ (и через неё определить принимаемые слова). Но в этот раз она будет совсем муторной и бесполезной.
    \end{remark*}

    \begin{lemma}
        Всякий RE-НКА можно заменить на регулярное выражение, порождающее тот же язык.
    \end{lemma}

    \begin{proof}
        Заметим, что регулярное выражение для пустой строки есть $\varnothing^*$. Таким образом WLOG рассматриваемый RE-НКА автомат содержит одно начальное и одно принимающее состояние; так как иначе можно создать новые начальное и принимающее состояния, провести $\varepsilon$-переходы из нового начального в старые начальные состояния и из старых принимающих в новое принимающее и забыть роли старых начальных и принимающих состояний.

        Будем уменьшать когда можно количество рёбер, а затем когда можно количество вершин. Рёбра будем склеивать кратные, т.е. если есть две вершины $p$ и $q$ два перехода из $p$ в $q$ по регулярным выражениям $r_1$ и $r_2$, то заменим на один переход из $p$ в $q$ по регулярному выражению $r_1 | r_2$. Очевидно, что язык автомата не меняется. Таким образом кратных рёбер у нас исчезают.

        Теперь пусть имеется состояние $q$ отличное от начального и принимающего. Попытаемся удалить $q$. Для всяких вершин $p_1$ и $p_2$ рассмотрим регулярные выражения $r_1$, $r_2$ и $r$, соответствующие переходам из $p_1$ в $q$, из $q$ в $r_2$ и из $q$ в $q$ соответственно, и заменим эти переходы (они будут удалены с удалением $q$) на перход из $p_1$ в $p_2$ по регулярному выражению $r_1 r* r_2$. Несложно проверить, что это тоже не изменит язык автомата.

        Таким образом у нас останутся только два состояния и не более двух переходов между ними. Пусть регулярное выражение перехода от начального состояния к принимающему --- $r$, а от принимающего к начальному --- $s$. Следовательно, язык автомата порождается регулярным выражением $r(sr)^*$.
    \end{proof}

    \subsection{Разные действия над автоматами}

    \begin{definition}
        Пусть даны ДКА $A = (\Sigma, P, p_0, \eta, E)$ и $B = (\Sigma, Q, q_0, \delta, F)$. \emph{Прямым произведением автоматов} $A$ и $B$ есть автомат $A \times B := C = (\Sigma, P \times Q, (p_0, q_0), \theta, E \times F)$, где
        \[\theta((p, q), a) := (\eta(p, a), \delta(q, a)).\]
        В таком случае $L(A \times B) = L(A) \cap L(B)$.

        Также можно построить автомат $C = (\Sigma, P \times Q, (p_0, q_0), \theta, E \times Q \cup P \times F)$, где
        \[\theta((p, q), a) := (\eta(p, a), \delta(q, a)).\]
        В таком случае $L(C) = L(A) \cup L(B)$.

        Также можно построить автомат $C = (\Sigma, P, p_0, \eta, P \setminus E)$. В таком случае $L(C) = \Sigma^* \setminus L(A)$.

        Также можно построить автомат $C = (\Sigma, P^P, f_\varepsilon = \Id, \widehat{\varepsilon}, \{f \in P^P \mid f^2(q_0) \in F\})$, где $P^P$ --- множество функций $P \to P$, $f_w: P \to P$ --- функция, переводящее всякое состояние $p$ в состояние, которое получается из $p$ прохождением по слову $w$, а
        \[\widehat{\delta}(f, a) := f_a \circ f.\]
        В таком случае $L(C) = \sqrt{L(A)} := \{w \in \Sigma^* \mid ww \in L(A)\}$.
    \end{definition}

    \begin{lemma}[о накачке, Рабин, Скотт]
        Пусть $L \subseteq \Sigma^*$ регулярен. Тогда есть константа $p \geqslant 1$, что для всякого слова $w$ длины хотя бы $p$ существует разбиение $w = xyz$, где $y \neq \varepsilon$ и $|xy| \leqslant p$, что для всех $l \geqslant 0$
        \[x y^l z \in L.\]
    \end{lemma}

    \begin{example}
        Язык $L = \{(ab)^n a^n\}_{n \in \NN}$ не регулярен, но удовлетворяет лемме о накачке.
    \end{example}

    \subsection{Минимальные ДКА}

    \begin{definition}
        Пусть дан ДКА $A$. \emph{Язык, принимаемый из состояния} $q$ --- язык
        \[L_A(q) := \{w \in \Sigma^* \mid \delta_A^*(q, w) \in F_A\}.\]
        Состояния, из которых принимаются эквивалентные состояния, называются \emph{равносильными}.
    \end{definition}

    \begin{lemma}
        Пусть в ДКА $A$ для двух различных вершин $q$ и $q' \neq q_0$ верно, что $L_A(q) = L_A(q')$. Рассмотрим автомат $A'$, полученный из автомата $A$ удалением вершины $q'$ и перенаправлением всех переходов, идущих в $q'$, на $q$.
        \begin{enumerate}
            \item $L_{A'}(p) = L_A(p)$ для всякой вершины $p \in Q \setminus \{q'\}$.
            \item $L(A') = L(A)$.
        \end{enumerate}
    \end{lemma}

    \begin{lemma}
        Пусть дан регулярный язык $L$ и строки $u, v \in \Sigma^*$, что существует строка $w \in \Sigma^*$, что одна из $uw$ и $vw$ лежит в $L$, а другая --- нет. Тогда для всякого ДКА $A$, реализующего $L$, верно, что
        \[\delta^*(q_0, u) \neq \delta^*(q_0, v).\]
    \end{lemma}

    \begin{lemma}
        Если ДКА $A$ минимален, то
        \begin{itemize}
            \item все состояния достижимы,
            \item из разных состояний принимаются разные языки.
        \end{itemize}
    \end{lemma}

    \begin{theorem}
        ДКА, реализующий язык $L$, без недостижимых состояний, где из разных состояний принимаются разные языки, единственен с точностью до изоморфизма (переименовывания состояний).
    \end{theorem}

    \begin{proof}
        Пусть $A$, $B$ --- два таких ДКА, порождающие язык $L$. Для каждого состояния $q \in Q_A$ выберем какую-нибудь строку $w_q$, что
        \[\delta_A^*(q_{A, 0}, w_q) = q.\]
        Тогда обозначим
        \[r_q := \delta_B^*(q_{B, 0}, w_q).\]

        Если для каких-то различных $p$ и $q$ верно, что $r_p = r_q$, то для всякой строки $w \in \Sigma^*$ верно, что
        \[w_p w \in L \quad \Longleftrightarrow \quad w_q w \in L.\]
        Отсюда следует, что $L_A(p) = L_A(q)$ --- противоречие с определением $A$. Значит все $r_q$ попарно различны. Следовательно $|Q_A| \leqslant |Q_B|$; аналогично наоборот. Значит отображение $\varphi: q \mapsto r_q$ задаёт биекцию.

        Если какая-то строка $w \in L_A(q)$, то $w_q w \in L(A) = L(B)$, значит $w \in L_B(\varphi(q))$. Таким образом $L_A(q) \subseteq L_B(\varphi(q))$; аналогично наоборот. Таким образом $L_A(q) = L_B(\varphi(q))$.

        Таким образом начальные и принимающие состояние автоматов соответствуют по $\varphi$, так как состояние $q$ начально тогда и только тогда, когда $L_A(q) = L(A)$, и принимающее тогда и только тогда, когда $\varepsilon \in L_A(q)$.

        Возьмём любое состояние $q \in Q_A$ и $a \in \Sigma$. Обозначим $p_A := \delta_A(q, a)$, $p_B := \delta_B(\varphi(q), a)$. Тогда если есть $w \in L_A(p_A) \bigtriangleup L_B(p_B)$, то $aw \in L_A(q) \bigtriangleup L_B(\varphi(q))$. Но $L_A(q) = L_B(\varphi(q))$, а значит
        \[\varphi(\delta_A(q, a)) = \delta_B(\varphi(q), a),\]
        т.е. $\delta_A$ и $\delta_B$ соответствуют друг другу по $\varphi$.

        Таким образом $\varphi$ --- изоморфизм автоматов $A$ и $B$.
    \end{proof}

    \begin{corollary}
        Любой автомат, реализующий $L$, является минимальным тогда и только тогда, когда не имеет недостижимых состояний, а из разных состояний принимаются разные языки.
    \end{corollary}

    \begin{corollary}
        Из любого автомата можно получить минимальный, убрав недостижимые состояния и склеив эквивалентные. 
    \end{corollary}

    \begin{corollary}
        У всех автоматов без недостижимых состояний множество (следовательно, и количество) языков, принимаемых из состояний одинаковое.
    \end{corollary}

    \begin{theorem}
        Есть алгоритм, минимизирующий ДКА.
    \end{theorem}

    \begin{proof}
        Уберём из автомата все недостижимые состояния. Язык не поменяется.

        В начале рассмотрим разбиение всех состояний $\Omega_0 := \{F; Q \setminus F\}$. Определим для всякого разбиения $\Omega$ множества $Q$ функцию $s_\Omega: Q \to \Omega$, которая сопоставляет всякому состоянию $q$, множество разбиения $\Omega$ в котором оно находится, и отношение $\sim_\Omega$ на $Q$ по правилу
        \[
            p \sim_\Omega q
            \quad \Longleftrightarrow \quad
            s_\Omega(p) = s_\Omega(q) \wedge \forall a \in \Sigma\; s_\Omega(\delta(p, a)) = s_\Omega(\delta(q, a)).
        \]
        Тогда построим последовательность $(\Omega_i)_{i=0}^\infty$, где $\Omega_0$ уже определено, а $\Omega_{i+1} = Q/{\sim}_{\Omega_i}$.

        Заметим следующее.
        \begin{itemize}
            \item $\Omega_{i+1}$ есть подразбиение $\Omega_i$.
            \item Всякие состояния, из которых принимаются одинаковые языки, лежат в одних и тех же множествах разбиения $\Sigma_0$. То же верно и для всякого $\Omega_i$, что можно доказать по индукции по $i$: действительно, если они не были разделены разбиением $\Omega_i$, то они эквивалентны по отношению $\sim_{\Omega_i}$, а значит не будут разделены разбиением $\Omega_{i+1}$.
            \item Разбиений $\Omega$ конечное множество. Значит с некоторого момента последовательность стабилизируется.
        \end{itemize}
        Таким образом в пределе имеется разбиение $\Omega$, для которого верно
        \[\Omega = Q/{\sim}_\Omega.\]

        Если есть какие-то два состояния $p$ и $q$, из которых принимаются разные языки, то есть слово $w \in L_A(p) \bigtriangleup L_A(q)$. Значит $\delta^*(p, w)$ и $\delta^*(q, w)$ разделены разбиением $\Omega_0$, а значит и $\Omega$. Но если бы $p$ и $q$ не были бы разделены разбиением $\Omega$, то и $\delta^*(p, w)$ и $\delta^*(q, w)$ не были бы. Значит $\Omega$ --- разбиение по принимаемым из состояний языкам.

        Построение последовательности $\Omega_i$ реализуется алгоритмически, а вместе с ней и проверка $\Omega_{i+1} = \Omega_i$. Значит можно построить разбиение $\Omega$ и склеить вершины по этому разбиению (рассмотреть автомат по модулю разбиения как отношения эквивалентности). Получим автомат, реализующий тот же язык, но без недостижимых состояний, где языки, принимаемые из состояний, попарно различны. Значит данный автомат минимален.
    \end{proof}

    \subsection{Двухсторонние автоматы}

    \begin{definition}
        \emph{Двухсторонний детерминированный конечный автомат} (также ``2ДКА'' или ``2DFA'') $A$ --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item начального состояния $q_0 \in Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times \Sigma \cup \{\vdash; \dashv\} \to Q \times \{+1; -1\}$.
        \end{itemize}
        Выполнены следующие условия:
        \begin{itemize}
            \item $\vdash$ и $\dashv$ не лежат в $\Sigma$.
            \item Для любого $q \in Q$
                \[\delta(q, \vdash) = (p, +1) \qquad \text{ и } \qquad \delta(q, \dashv) = (r, -1)\]
                для некоторых $p$ и $r$.
        \end{itemize}
        Входными данными является конечная строка $w = s_1 \dots s_l$, преобразуемая в ленту длины $l+2$, на которой написано
        \[s_0 := \vdash;\; s_1;\; \dots;\; s_l;\; s_{l+1} := \dashv.\]
        Состояние вычисления после $k$ шагов --- это совокупность некоторого состояния автомата $q_k \in Q$ и числа $i_k \in \{0; \dots; l+1\}$. Начальное состояние вычисления (оно же состояние вычисления после $0$ шагов) --- совокупность начального состояния автомата $q_0$ и $i_0 = 0$. Каждым шагом состояние $(q_k, i_k)$ заменяется на $(q_{k+1}, i_{k+1})$, где
        \[(q_{k+1}, i_{k+1} - i_k) := \delta(q_k, s_{i_k}).\]
        Т.е. формально вычисление --- это последовательность состояний $((q_k, i_k))_{k=0}^\infty$, где
        \begin{itemize}
            \item $q_0$ --- начальное состояние автомата,
            \item $i_0 = 0$,
            \item $(q_{k+1}, i_{k+1} - i_k) := \delta(q_k, s_{i_k})$.
        \end{itemize}
        Входная строка принимается автоматом, если есть такое $n$, что $q_n \in F$ и $i_n = l+1$.

        \emph{Язык автомата} $A$ или \emph{язык, распознаваемый автоматом} $A$, --- это множество $L(A)$ всех строк, распознаваемых (принимаемых) автоматом $A$. Язык, распознаваемый хоть каким-нибудь автоматом называется \emph{регулярным}.
    \end{definition}

    \begin{theorem}
        Всякий 2DFA можно свести к DFA.
    \end{theorem}

    \begin{proof}
        \todo[inline]{Написать.}
    \end{proof}

    \begin{theorem}[Майхилла-Нероуда]
        Пусть дан язык $L$. Введём отношение эквивалентности $\equiv_L$ на $\Sigma^*$ по правилу
        \[u \equiv_L v \qquad \Longleftrightarrow \qquad \forall w \in \Sigma^* \quad uw \in L \Leftrightarrow vw \in L.\]
        Тогда $L$ регулярен тогда и только тогда, когда количество классов эквивалентности $|\Sigma^*/{\equiv_L}|$ конечно.
    \end{theorem}

    \begin{proof}
        Пусть $L$ регулярен. Тогда есть минимальный автомат $A$, порождающий язык $L$. Для всякого слова $u$ можно определить состояние $q_u := \delta^*(q_0, u)$. Тогда множество слов $w \in \Sigma^*$, что $uw \in L$ образует алфавит $L_A(q_u)$. Следовательно,
        \[
            u \equiv_L v
            \qquad \Longleftrightarrow \qquad
            L_A(q_u) = L_A(q_v)
            \qquad \Longleftrightarrow \qquad
            q_u = q_v
        \]
        (последний переход верен в силу минимальности $A$). Таким образом
        \[|\Sigma^*/{\equiv_L}| = |Q|, \qquad \Sigma^*/{\equiv_L} = \{\{u \in \Sigma^* \mid \delta^*(q_0, u) = q\}\}_{q \in Q}.\]

        Теперь пусть $\Sigma^*/{\equiv_L}$ конечно. Рассмотрим ДКА
        \[
            A = (\Sigma, \Sigma^*/{\equiv_L}, [\varepsilon]_{\equiv_L}, F, \delta), \text{ где }
            \qquad
            F := \{N \in \Sigma^*/{\equiv_L} \mid N \cap L \neq \varnothing\},
            \qquad
            \delta([u]_{\equiv_L}, a) := [ua]_{\equiv_L}.
        \]
        Несложно проверить, что $\delta$ определено корректно. При этом понятно, что
        \[\delta^*([\varepsilon]_{\equiv_L}, u) = [u]_{\equiv_L}.\]
        Заметим для всякого $N \in \Sigma^*/{\equiv_L}$, что если $N \cap L \neq \varnothing$, то есть $v \in N \cap L$, поэтому $v\varepsilon \in L$, а значит для всякого $u \in N$ верно, что $u\varepsilon \in L$, т.е. $N \subseteq L$. Поэтому понятно, что
        \[
            v \in L
            \qquad \Longleftrightarrow \qquad
            [v]_{\equiv_L} \cap L \neq \varnothing
            \qquad \Longleftrightarrow \qquad
            \delta^*([\varepsilon]_{\equiv_L}, v) \cap L \neq \varnothing
            \qquad \Longleftrightarrow \qquad
            \delta^*([\varepsilon]_{\equiv_L}, v) \in F.
        \]
        Это значит, что $L(A) = L$.
    \end{proof}

    \begin{remark*}
        Заодно мы также показали, что
        \[L = \bigcup_{u \in L} [u]_{\equiv_L}.\]
    \end{remark*}

    \subsection{Вероятностные конечные автоматы}

    \begin{definition}
        \emph{Вероятностный конечный автомат} (также ``ВКА'' или ``PFA'') $A$ --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item начального состояния $q_0 \in Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times \Sigma \to [0; 1]^Q$,
        \end{itemize}
        что для любых $q \in Q$ и $a \in \Sigma$ 
        \[\sum_{p \in Q} \delta(q, a)(p) = 1.\]
        Входными данными является конечная строка $w = s_1 \dots s_n$. Состояние вычисления после $k$ шагов --- это некоторое распределение вероятности между состояниями автомата $f_k: Q \to [0; 1]$. Соответственно, начальное состояние вычисления (оно же состояние вычисления после $0$ шагов) --- распределение $f_0(q) := [q = q_0]$. Каждым шагом состояние $f_k$ заменяется на $f_{k+1} := \sum_{p \in Q} f_k(p) \delta(p, s_{k+1})$. Т.е. формально вычисление --- это последовательность распределений вероятности $(f_k)_{k=0}^n$, где
        \begin{itemize}
            \item $f_0$ --- начальное состояние автомата,
            \item $f_{k+1} := \sum_{p \in Q} f_k(p) \delta(p, s_{k+1})$.
        \end{itemize}
        Распределение $f_n$ называется \emph{результатом вычисления}. Также говорят, что автомат принимает строку $w$, если $\sum_{q \in F} f_n(q) \geqslant \frac{1}{2}$, и отвергает в ином случае.

        \emph{Язык автомата} $A$ или \emph{язык, распознаваемый автоматом} $A$, --- это множество $L(A)$ всех строк, распознаваемых (принимаемых) автоматом $A$. Язык, распознаваемый хоть каким-нибудь автоматом называется \emph{регулярным}.
        
        Также определяют \emph{условие ограниченной ошибки} --- условие, заключающееся в том, что вероятность принятия для любого слова всегда либо $\geqslant \frac{2}{3}$, либо $\leqslant \frac{1}{3}$. Будем рассматривать ВКА, удовлетворяющие этому свойству.
    \end{definition}

    \begin{theorem}
        Для всякого ВКА есть ДКА, распознающий тот же язык.
    \end{theorem}

    \begin{proof}
        Пусть дан ВКА $A$. Пронумеруем его состояния: $M := |Q_A|$, $Q = \{q_i\}_{i=1}^M$. Тогда всякое состояние вычисления есть вектор распределения вероятности $(a_i)_{i=1}^M$ ($a_i$ --- вероятность попадания в $a_i$; $\sum_{i=1}^M a_i = 1$). Также для всякого слова $u \in \Sigma^*$ определим вектора $p(u)$ и $q(u)$, где $p_i(u)$ --- вероятность попадания в вершину $q_i$ по прохождению по слову $u$, а $q_i(u)$ --- вероятность попадания в принимающее состояния, выходя из $q_i$ и идя по слову $u$. В частности, $p(u) \cdot q(v)$ --- вероятность принятия слова $u \cdot v$.
        
        \begin{thlemma}
            Пусть для некоторых слов $u$ и $u'$ верно, что $\|p(u) - p(u')\| := \max_i |p_i(u) - p_i(u')| \leqslant \varepsilon$. Тогда для любого слова $v$
            \[|p(u)q(v) - p(u')q(v)| \leqslant n \varepsilon.\]
        \end{thlemma}

        \begin{proof}
            \begin{align*}
                |p(u)q(v) - p(u')q(v)|
                &= \left|\sum p_i(u)q_i(v) - \sum p_i(u')q_i(v)\right|\\
                &= \left|\sum (p_i(u) - p_i(u'))q_i(v)\right|\\
                &\leqslant \sum |p_i(u) - p_i(u')|q_i(v)\\
                &\leqslant \sum |p_i(u) - p_i(u')|\\
                &\leqslant n \|p(u) - p(u')\|\\
                &= n \varepsilon
            \end{align*}
        \end{proof}

        \begin{corollary}
            Если $\|p(u) - p(u')\| < \frac{1}{3n}$, то из распределений $p(u)$ и $p(u')$ принимаются одинаковые языки, т.е. для всякого слова $v$ верно $uv \in L \Leftrightarrow u'v \in L$.
        \end{corollary}

        \begin{proof}
            Как мы показали разница в вероятностях принятия $uv$ и $u'v$ равна
            \[|p(u)q(v) - p(u')q(v)| \leqslant n \|p(u) - p(u')\| < \frac{1}{3}.\]
            Поскольку $A$ удовлетворяет условию ограниченной ошибки, то вероятности принятия $uv$ и $u'v$ либо обе $\geqslant \frac{2}{3}$, либо обе $\leqslant \frac{1}{3}$, т.е. $uv$ и $u'v$ либо оба принимаются, либо оба не принимаются. Отсюда и выходит требуемое.
        \end{proof}

        Вспомним, что все возможные вектора $p(u)$ лежат в пространстве $[0; 1]^M$ (в реальности можно ещё поставить условие, что сумма координат равна $1$, но это не обязательно). Тогда разобьём его по каждой координате на отрезки длины $1/(3n+1)$; получится $(3n+1)^M$ кубиков, на которые распалось всё пространство $[0; 1]^M$. Как мы показали, для любых двух векторов $p(u)$ и $p(u')$ из одного кубика $\|p(u) - p(u')\|$, а значит языки принимаемые внутри каждого кубика одинаковы (если в кубике есть хоть один вектор $p(u)$).

        Пусть $L$ --- язык, распознаваемый автоматом $A$. Тогда мы имеем, что $|\Sigma^*/{\equiv_L}|$ конечно, а значит есть ДКА, реализующий тот же язык.
    \end{proof}

    \begin{definition}
        \emph{Двухсторонний вероятностный конечный автомат} (также ``2ВКА'' или ``2PFA'') $A$ --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$,
            \item конечного множества состояний $Q$,
            \item начального состояния $q_0 \in Q$,
            \item множество принимающих состояний $F \subseteq Q$,
            \item функция перехода $\delta: Q \times (\Sigma \cup \{\vdash; \dashv\}) \to [0; 1]^{Q \times \{+1; -1\}}$.
        \end{itemize}
        Выполнены следующие условия:
        \begin{itemize}
            \item $\vdash$ и $\dashv$ не лежат в $\Sigma$.
            \item Для любых $q, p \in Q$
                \[
                    \delta(q, \vdash)(p, -1) = 0
                    \qquad \text{ и } \qquad
                    \delta(q, \dashv)(p, +1) = 0.
                \]
            \item Для любых $q \in Q$ и $a \in \Sigma \cup \{\vdash; \dashv\}$ 
                \[\sum_{t \in Q \times \{+1; -1\}} \delta(q, a)(t) = 1.\]
        \end{itemize}
        Входными данными является конечная строка $w = s_1 \dots s_n$, преобразуемая в ленту длины $l+2$, на которой написано
        \[s_0 := \vdash; s_1; \dots; s_l; s_{l+1} := \dashv.\]
        Автомат также блуждает по полосе как $2DFA$, но каждый раз делает то или иное действие случайно с заданным распределением вероятностей. И как для $PFA$ мы принимаем строку, если вероятность её принять хотя бы $\frac{1}{2}$, а также будем требовать условие ограниченной ошибки.
    \end{definition}

    \begin{example}
        2ВКА распознают больше языков, чем только регулярные. Для примера построим 2ВКА, распознающий $\{a^n b^n\}_{n \in \NN}$.

        Автомат будет работать следующим образом. Он проверит, что строка имеет вид $a^i b^j$, где $i \equiv j \pmod{3}$ (это можно сделать с помощью 2ДКА, а значит и с помощью 2ВКА). Затем автомат будет до бесконечности проходить по всему слову, на каждом символе (отличном от граничных) подбрасывая монетку. Назовём успехом символа $a$ проход, после которого на каком-то символе $a$ выпал орёл, но ни на одном символе $b$ он не выпал; аналогично назовём успех символа $b$. В течение процесса проходов будем считать успехи символов (на оба символ будет хватать счётчиков до 3). Если в какой-то момент выпали 3 успеха одного из символов и ни один успех другого, то будем отвергать строку; если же в какой-то момент у каждого символа будет успеха, но у каждого символа их меньше трёх, то будем принимать строку.

        Теперь покажем, что автомат действительно распознаёт описанный язык. В случае, если строка не подошла шаблону $a^i b^j$, где $i \equiv j \pmod{3}$, строка будет отвергнута с вероятностью $1$ --- правильно. Следовательно, будем рассматривать только строки такого шаблона.
        
        Если $i = j$, то вероятность выпадения успеха $a$ равна вероятности выпадения успеха $b$. Т.е. вероятность выпадения успеха $a$ при условии выпадения хоть какого-нибудь успеха равна $1/2$. Следовательно, вероятность вероятность выпадения хотя бы трёх каких-нибудь успехов равна $1$, а вероятность выпадения 1 успеха $a$ и двух успехов $b$ или наоборот равна $6/8 = 3/4$. Таким образом вероятность принятия равна $3/4 > 2/3$.

        Если $i \neq j$, то WLOG $i > j$, т.е. $i - 3 \geqslant j$. Значит вероятность успеха $a$ при условии выпадения какого-нибудь успеха равна
        \[
            \frac{1/2^j (1 - 1/2^i)}{1/2^j (1 - 1/2^i) + 1/2^i (1 - 1/2^j)}
            = \frac{2^i - 1}{2^i + 2^j - 2}
            \geqslant \frac{2^i - 1}{2^i + 2^{i-3} - 2}
            = \frac{8 \cdot 2^{i-3} - 1}{9 \cdot 2^{i-3} - 2}
            = \frac{8}{9} + \frac{7/9}{9 \cdot 2^{i-3} - 2}
            > \frac{8}{9}.
        \]
        Таким образом вероятность трёх успехов $a$ подряд $>(8/9)^3 > 2/3$. Т.е. вероятность отвержения $>2/3$.

        Итого автомат принимает только описанный язык и удовлетворяет условию ограниченной ошибки.
    \end{example}

    \subsection{Формальные грамматики}

    \begin{definition}
        \emph{Граматика} $G$ --- это совокупность
        \begin{itemize}
            \item $\Sigma$ --- конечный алфавит языка, который мы определяем,
            \item $N$ --- конечный алфавит ``нетерминальных символов'', которые являются переменными задания грамматики,
            \item $R$ --- конечное множество правил грамматики, т.е. конечное подмножество $N \times (\Sigma \cup N)^*$
            \item $S \in N$ --- ``начальный символ'', выделенный нетерминальный, с которого начинается построение.
        \end{itemize}
        
        Определим следующие объекты.
        \begin{itemize}
            \item Отношение $\mathrel{\underset{G}{\Rightarrow}}$ (выводимость в один шаг) на $(\Sigma \cup N)^*$ задаётся по правилу:
                \[
                    x \mathrel{\underset{G}{\Rightarrow}} y
                    \qquad \Longleftrightarrow \qquad
                    \exists u, v, p, q \in (\Sigma \cup N)^* \colon \quad x = upv \wedge (p; q) \in P \wedge y = uqv.
                \]
                (Из $x$ выводится $y$ в один шаг тогда и только тогда, когда $x$ имеет вид $upv$, $y$ --- $uqv$, а $p \to q$ --- правило в грамматике $G$.)
            \item Отношение $\mathrel{\overset{*}{\underset{G}{\Rightarrow}}}$ (выводимость) --- рефлексивно-транзитивное замыкание отношения $\mathrel{\underset{G}{\Rightarrow}}$.
            \item Сентенциальная форма (также ``sentential form'') --- всякое $w \in (\Sigma \cup N)^*$, что $S \mathrel{\overset{*}{\underset{G}{\Rightarrow}}} w$.
            \item \emph{Предложение, построенное грамматикой $G$} --- всякое $w \in \Sigma^*$, являющееся сентенциальной формой.
            \item \emph{Язык грамматики} $G$ --- множество всех предложений, построенных грамматикой $G$.
        \end{itemize}
    \end{definition}

    \begin{remark*}
        Часто правило записывают не в виде $(p; q)$, а $p \to q$. А когда имеется много правил $p \to q_1$, \dots, $p \to q_n$, то обычно пишут $p \to q_1 \mid \dots \mid q_n$.
    \end{remark*}

    \begin{remark*}
        Всякое слово, полученное из некоторого нетерминала удобно изображать в виде дерева (с введённым на нём порядком "слева направо"), где каждая вершина хранит символ, а переход от родителя к детям соответствует правилам грамматики.
    \end{remark*}

    \begin{example}[синтаксис арифметических выражение]
        Неформально, арифметическое выражение можно построить так.
        \begin{itemize}
            \item Переменная $x$ --- арифметическое выражение.
            \item Число $1$ --- арифметическое выражение.
            \item Если $e$ и $e'$ --- выражения, то $e + e'$ и $e \cdot e'$ --- тоже выражения.
            \item Если $e$ --- выражение, то $(e)$ --- тоже.
        \end{itemize}

        Формально она строится грамматикой $G = (\Sigma, N, R, S)$, где
        \begin{itemize}
            \item $\Sigma := \{x; 1; {+}; {\cdot}; \text{``(''}; \text{``)''}\}$,
            \item $N := \{S\}$,
            \item $R := \{(S; x); (S; 1); (S; S+S); (S; S \cdot S); (S; \text{``}(S)\text{''})\}$.
        \end{itemize}
        То есть, изображая правила проще, имеем
        \[S \to x \mid 1 \mid S + S \mid S \cdot S \mid (S).\]
    \end{example}

    \begin{remark}
        Изначально множество правил могло являться подмножеством $((\Sigma \cup N)^* \setminus \{\varepsilon\}) \times (\Sigma \cup N)^*$. B в таком случае была введена \emph{иерархия Хомского}:
        \begin{itemize}
            \item \textbf{Тип 0. ``Рекурсивно перечислимые'' грамматики.} Это грамматики без каких-либо ограничений на правила (кроме, как уде говорилось, того, что заменяемое слово в каждом правиле должно быть непусто).
            \item \textbf{Тип 1. ``Контекстно-зависимые'' грамматики.} Это грамматики, где правила имеют вид $\alpha A \beta \to \alpha \gamma \beta$, где $\alpha, \beta \in (\Sigma \cup N)^*$, $\gamma \in (\Sigma \cup N)(\Sigma \cup N)^*$, $A \in N$.
            \item \textbf{Тип 2. ``Контекстно-свободные'' грамматики.} Это грамматики, где правила имеют вид $A \to \alpha$, где $\alpha\in (\Sigma \cup N)^*$, $A \in N$.
            \item \textbf{Тип 3. ``Регулярные'' грамматики.} Это грамматики, где правила имеют вид $A \to a$ или $A \to aB$, где $a \in \Sigma$, $A, B \in N$.
        \end{itemize}
        Например, несложно понять, что регулярные грамматики равносильны ДКА. \textbf{Мы же будем обсуждать только тип 2!!!}
    \end{remark}

    \begin{definition}
        Пусть дана грамматика $G$, а $A$ --- нетерминал в ней. \emph{Язык, задаваемый нетерминальным символом} $A$ --- это язык слов $w$, что $A \mathrel{\overset{*}{\underset{G}{\Rightarrow}}} w$.
    \end{definition}

    \subsection{Операции над грамматиками.}

    \begin{lemma}\ 
        \begin{enumerate}
            \item Если языки $L$ и $M$ задаются грамматиками, то и $L \cup M$ задаётся грамматикой.
            \item Если языки $L$ и $M$ задаются грамматиками, то и $LM$ задаётся грамматикой.
            \item Если языки $L$ задаётся грамматикой, то и $L^*$ задаётся грамматикой.
            \item Всякий регулярный язык задаётся грамматикой.
        \end{enumerate}
    \end{lemma}

    \begin{proof}
        \begin{enumerate}
            \item Пусть $(\Sigma, N_L, R_L, S_L)$ и $(\Sigma, N_M, R_M, S_M)$ задают языки $L$ и $M$. Рассмотрим грамматику $(\Sigma, N, R, S)$, где
                \begin{itemize}
                    \item $N := N_L \cup N_M \cup \{S\}$,
                    \item $R := R_L \cup R_M \cup \{S \to S_L; S \to S_M\}$.
                \end{itemize}
                Понятно, что тогда такая грамматика задаёт $L \cup M$.
            \item Пусть $(\Sigma, N_L, R_L, S_L)$ и $(\Sigma, N_M, R_M, S_M)$ задают языки $L$ и $M$. Рассмотрим грамматику $(\Sigma, N, R, S)$, где
                \begin{itemize}
                    \item $N := N_L \cup N_M \cup \{S\}$,
                    \item $R := R_L \cup R_M \cup \{S \to S_L S_M\}$.
                \end{itemize}
                Понятно, что тогда такая грамматика задаёт $LM$.
            \item Пусть $(\Sigma, N_L, R_L, S_L)$ задаёт язык $L$. Рассмотрим грамматику $(\Sigma, N, R, S)$, где
                \begin{itemize}
                    \item $N := N_L \cup \{S\}$,
                    \item $R := R_L \cup \{S \to S_L S; S \to \varepsilon\}$.
                \end{itemize}
                Понятно, что тогда такая грамматика задаёт $L^*$.
            \item Пусть ДКА $(\Sigma, Q, q_0, \delta, F)$ задаёт язык $L$. Рассмотрим грамматику $(\Sigma, N, R, S)$, где
                \begin{itemize}
                    \item $N := \{A_q\}_{q \in Q}$,
                    \item $R := \{A_q \to a A_{\delta(q, a)}\}_{\substack{q \in Q\\a \in \Sigma}} \cup \{A_q \to \varepsilon\}_{q \in F}$,
                    \item $S := A_{q_0}$.
                \end{itemize}
                Понятно, что тогда такая грамматика задаёт $L$.
        \end{enumerate}
    \end{proof}

    \begin{theorem}
        Пусть язык $L$ задаётся грамматикой, а $M$ регулярен. Тогда $L \cap M$ задаётся грамматикой.
    \end{theorem}

    \begin{proof}
        Пусть $L$ порождается грамматикой $(\Sigma, N, R, S)$, а $M$ --- автоматом $(\Sigma, Q, q_0, \delta, F)$. Рассмотрим грамматику $(\Sigma, N', R', S')$, где
        \begin{itemize}
            \item $N' := \{A_{p, r}\}_{\substack{A \in N\\p, r \in Q}} \cup \{S'\}$,
            \item
                \begin{align*}
                    R'
                    &:= \left\{A_{p, r} \to u_0 (B_1)_{r_0, p_1} u_1 \dots u_{n-1} (B_n)_{r_{n-1}, p_n} u_n \left|
                        \begin{gathered}
                            (A \to u_0 B_1 u_1 \dots u_{n-1} B_n u_n) \in R\\
                            {}\wedge p_0, r_0, \dots, p_n, r_n \in Q\\
                            {}\wedge \forall i \; \delta(p_i, u_i) = r_i\\
                            {}\wedge p_0 = p \wedge r_0 = r
                        \end{gathered}
                    \right.\right\}\\
                    &\cup \{S' \to S_{q_0, q}\}_{q \in F}.
                \end{align*}
        \end{itemize}
        $A_{p, r}$ работает как состояние $A$ из старой грамматики, но теперь с условием, что порождаемое слово должно переводить состояние $p$ в состояние $r$ в данном автомате. Таким образом
        \[L(A_{p, r}) = \{w \in L(A) \mid \delta(p, w) = r\}.\]
        Следовательно,
        \[L(S') = \bigcup_{q \in F} L(S_{q_0, q}) = \{w \in L(S) \mid \delta(q_0, w) \in F\} = L(S) \cap M = L \cap M.\] 
    \end{proof}

    \begin{theorem}
        Пусть есть язык $L$, задающийся грамматикой. Тогда язык префиксов $L$ задаётся грамматикой. 
    \end{theorem}

    \subsection{Лемма о накачке}

    \begin{lemma}[о накачке, aka Бар-Хиллель, Перлес, Шамир, 1961]
        Пусть язык $L$ задаётся грамматикой. Тогда есть константа $p \geqslant 1$, что для всякого слова $w \in L$ длины хотя бы $p$ есть разбиение $w = xuyvz$, что $|uyv| \leqslant p$, $uv \neq \varepsilon$, и для всякого $n \geqslant 0$ слово $x u^n y v^n z \in L$.
    \end{lemma}

    \begin{proof}
        Пусть грамматика $G = (\Sigma, N, R, S)$ задаёт $L$. Пусть $m$ --- наибольшая длина подстановочного слова в $G$, т.е.
        \[m := \max_{(A \to \alpha) \in R} |\alpha|.\]
        Пусть $p := m^{|N| + 1}$. Возьмём любое слово $w$ на $\geqslant p$ символов и рассмотрим минимальное (в смысле числа вершин) дерево разбора этого слова. Заметим, что в нём хотя бы $m^{|N|}$ нелистовых вершин, так как терминальные символы могут порождены только такими вершинами, а каждая вершина порождает не более $m$ символов (любых, а значит и терминальных). Если без листов дерево имеет глубину $\leqslant |N|$, то в нём не более $\frac{m^{|N|} - 1}{m-1}$ вершин, т.е. у него глубина хотя бы $|N| + 1$, т.е. есть путь глубины $\geqslant |N| + 1$. Рассмотрим его постфикс длины $|N| + 1$. В нём будет два одинаковых нетерминальных символа, а значит блок с верхнего по нижний можно дублировать у получать правильные деревья разбора. Это и значит, что некоторые $w = xuyvz$, а новые слова --- $x u^n y v^n z$. При этом $uv \not \varepsilon$, так как иначе дерево разбора без этого куска будет деревом разбора того же слова $w$, что противоречит с минимальностью изначального дерева. С другой стороны $|uyv| \leqslant p$, так как верхняя из найденных одинаковых вершин находится на уровне $|N| + 1$ снизу или ниже, а значит её поддерево содержит $\leqslant m^{|N|}$ вершин, а значит порождаемое подслово содержит $\leqslant m^{|N| + 1} = p$ символов; и этим словом является $uyv$.
    \end{proof}

    \begin{example}
        Язык $\{a^n b^n c^n\}_{n \in \ZZ}$ не задаётся грамматикой.

        Предположим противное. Тогда по лемме о накачке есть некоторая константа $p$. Возьмём слово $w = a^p b^p c^p$. По лемме $w = xuyvz$, что $|uyv| \leqslant p$, $uv \neq \varepsilon$, а $x u^n y v^n z$ лежит в языке. Но так как $|uyv| \leqslant p$, то $uyv$ точно не захватывает хотя бы один из блоков $a^p$, $b^p$ и $c^p$. Но тогда в слове $x u^n y v^n z$ будет не одинаковое количество $a$-шек, $b$-шек и $c$-шек. 
    \end{example}

    \begin{remark}
        Как следствие, пересечение грамматизируемых языков не обязательно грамматизируемо. Например, если $L := \{a^n b^n c^m \mid n, m \geqslant 0\}$, а $M := \{a^n b^m c^m \mid n, m \geqslant 0\}$, то $L$ и $M$ задаются грамматиками, а $L \cap M = \{a^n b^n c^n\}_{n \geqslant 0}$ не задаётся.
    \end{remark}

    \begin{lemma}[Огдан, 1968]
        Пусть язык $L$ задаётся грамматикой. Тогда есть константа $p \geqslant 1$, что для всякого слова $w \in L$ длины хотя бы $p$ и всякого $P \subseteq \{1; \dots; |w|\}$, что $|P| \geqslant p$, есть разбиение $w = xuyvz$, что $uyv$ содержит не более $p$ позиций из $P$, а $uv$ --- хотя бы одну позицию из $P$, и для всякого $n \geqslant 0$ слово $x u^n y v^n z \in L$.
    \end{lemma}

    \begin{proof}
        Пусть грамматика $G = (\Sigma, N, R, S)$ задаёт $L$. Пусть $m$ --- наибольшая длина подстановочного слова в $G$, т.е.
        \[m := \max_{(A \to \alpha) \in R} |\alpha|.\]
        Пусть $p := m^{|N| + 1}$. Возьмём любое слово $w$ на $\geqslant p$ символов, выберем любое множество позиций $P \subseteq \{1; \dots; |w|\}$ мощности $\geqslant p$ и рассмотрим дерево разбора этого слова. Назовём вершину дерева вершиной ветвления, если у хотя бы двух её детей есть символы-потомки с позициями из $P$. Тогда в дереве можно выделить позиции из $P$ и вершины ветвления и они образуют ``поддерево''; назовём его поддеревом для $P$.
        
        Заметим, что в нём хотя бы $m^{|N|}$ нелистовых вершин, так как терминальные символы могут порождены только такими вершинами, а каждая вершина порождает не более $m$ символов (любых, а значит и терминальных). Если без листов поддерево (для $P$) имеет глубину $\leqslant |N|$, то в нём не более $\frac{m^{|N|} - 1}{m-1}$ вершин, т.е. у него глубина хотя бы $|N| + 1$, т.е. есть путь глубины $\geqslant |N| + 1$. Рассмотрим его постфикс длины $|N| + 1$. В нём будет два одинаковых нетерминальных символа, а значит блок с верхнего по нижний можно дублировать у получать правильные деревья разбора. Это и значит, что некоторые $w = xuyvz$, а новые слова --- $x u^n y v^n z$. При этом $uv$ содержит хотя бы одну позицию из $P$, так как у каждой вершины поддерева есть хотя бы два ребёнка, а значит хоть какая-то позиция из $P$ попала в повторяемый блок. С другой стороны $|uyv|$ содержит $\leqslant p$ позиций из $P$, так как верхняя из найденных одинаковых вершин находится в поддереве для $P$ на уровне $|N| + 1$ снизу или ниже, а значит её поддерево содержит $\leqslant m^{|N|}$ вершин, а значит порождаемое подслово содержит $\leqslant m^{|N| + 1} = p$ позиций из $P$; и этим словом является $uyv$.
    \end{proof}

    \begin{example}
        Язык $L := \{a^l b^m c^n \mid l, m, n \geqslant 1 \wedge l \neq m \neq n \neq l\}$ удовлетворяет лемме о накачке, но не лемме Огдена.

        Действительно, пусть $p = 7$. Возьмём любое слово $w$ длины хотя бы $p$. Т.е. $w = a^{l_a} b^{l_b} c^{l_c}$, $l_a$, $l_b$ и $l_c$ попарно различны, а $l_a + l_b + l_c \geqslant 7$. Пусть $s \in \{a; b; c\}$ --- такой символ, что $l_s = \max(l_a, l_b, l_c)$. Заметим, что $l_s \geqslant 4$, так как иначе $l_a + l_b + l_c \leqslant l_c + (l_c - 1) + (l_c - 2) = 3l_c - 3 \leqslant 6$. Тогда пусть $k$ --- наименьшее натруальное число, что $k \notin \{l_s - l_a; l_s - l_b; l_s - l_c\}$. Одно из $l_s - l_a$, $l_s - l_b$ и $l_s - l_c$ является нулём, а остальные положительны и различны. Значит $k \leqslant 3$, и следовательно, $k < l_s$. Тогда возьмём такое разбиение $w = xuyvz$, что $u = s^k$, а $yv = \varepsilon$. Тогда $x u^n y v^n z$ тоже будет лежать в $L$ для всех $n \geqslant 0$.

        При этом пусть $L$ задаётся грамматикой. Тогда лемма Огдана даёт нам константу $p$. Тогда рассмотрим строку $w = a^p b^{p + p!} c^{p + 2p!} \in L$ и выделим первые $p$ позиций. Тогда есть разбиение $w = xuyvz$ как в лемме Огдана. При этом если $u$ или $v$ захватывает захватывает разные символы, то тогда при повторениях $u$ и $v$ получаемая строка не будет сортированной. Значит $u$ и $v$ содержат символы только одного вида. При этом, $uv$ содержит хотя бы один символ $a$ по лемме Огдана. Значит $u$ --- подслово в блоке $a^p$, а $v$ --- подслове в одном из блоков $a^p$, $b^{p + p!}$ и $c^{p + 2p!}$. Если $v$ находится в блоке $b^{p + p!}$, то в слове $x u^n y v^n z$, где $n = \frac{2p!}{|u|}$, блок $a$-шек будет иметь ту же длину, что и блок $c$-шек, что противоречит лемме Огдана; аналогично, если $v$ будет в блоке $c^{p + 2p!}$. Таким образом $u$ и $v$ находятся в блоке $a^p$. Тогда в слове $x u^n y v^n z$, где $n = \frac{p!}{|uv|}$, блоки $a$-шек и $b$-шек будут одной длины, что тоже противоречит лемме Огдана.
    \end{example}

    \begin{theorem}
        Языки над односимвольным алфавитом, задающиеся грамматикой, регулярны.
    \end{theorem}

    \begin{proof}
        WLOG $\Sigma = \{a\}$. Пусть $L$ задаётся грамматикой. По лемме о накачке есть $p > 0$, что для всякого $k \geqslant p$ если $a^k \in L$, то есть $q \in [1; p]$, что $a^{k - q + qn} \in L$ для всякого $n \geqslant 0$. Следовательно $a^{k + p! n} \in L$ для всех $n$. Т.е. если какой-то остаток по модулю $p!$ реализуется, то все реализации, начиная с некоторой задаются. Т.е. множество всех возможных $k$, что $a^k \in L$ периодично с некоторого места, значит $L$ задаётся автоматом.
    \end{proof}

    \begin{definition}
        \emph{Нормальный вид Хомского} --- это грамматика, где каждое правило имеет один из следующих видов.
        \begin{itemize}
            \item $A \to BC$, где $A \in N$, $B, C \in N \setminus \{S\}$.
            \item $A \to a$, где $A \in N$, $a \in \Sigma$.
            \item (Иногда добавляют. Влияет только лишь на то, разрешаем ли мы пустой строке присутствовать в языке или нет.) $S \to \varepsilon$.
        \end{itemize}
    \end{definition}

    \begin{theorem}
        Всякая грамматика приводится к нормальному виду Хомского (не изменяя порождаемого языка). Точнее, пусть имеется грамматика $G = (\Sigma, N, R, S)$. Тогда можно проделать следующие операции (в заданном порядке).
        \begin{enumerate}
            \item Можно подправить грамматику, чтобы каждое правило имело вид $A \to \alpha$, где $|\alpha| \leqslant 2$. (``Нарезание правил.'')
            \item Можно подправить грамматику, чтобы не было правил $A \to \varepsilon$ для $A \in N \setminus \{S\}$.
            \item Можно подправить грамматику, чтобы не было правил $A \to B$ для $A, B \in N$. (``Удаление единичных (цепных) правил.'')
            \item Можно подправить грамматику, чтобы не было правил $A \to bX$ и $A \to Xb$ для $A, X \in N$, $b \in \Sigma$.
            \item Можно подправить грамматику, чтобы всякое правило имело вид $N \to (\Sigma \cup N \setminus \{S\})^*$.
            \item Построенная таким образом грамматика будет иметь размер $O(n^2)$, где $n$ --- размер изначальной грамматики. Размер грамматики есть $\sum_{(A \to \alpha) \in R} |\alpha| + 2$.
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        \newcommand{\Nullable}{\mathrm{Nullable}}
        \begin{enumerate}
            \item Просто каждый раз всякое правило $A \to \alpha X$ ($X \in \Sigma \cup N$, $\alpha \in (\Sigma \cup N)^*$), где $|\alpha| \geqslant 2$, заменим на правила $A \to TX$ и $T \to \alpha$, где $T$ --- новый нетерминальный символ.

            \item Пока будем добиваться данной цели с возможностью потери $\varepsilon$ в $L(G)$. Пусть $\Nullable := \{A \in N \mid L_G(A) \ni \varepsilon\}$. Заметим, что $\Nullable$ строится ``за $|N|+1$ шаг''.
            
                Действительно, пусть $\Nullable_k$ --- множество нетерминалов $A \in N$, что есть дерево разбора из $A$ глубины не более $k+2$ (верхний уровень имеет глубину $1$) для $\varepsilon$. Тогда $\Nullable_0 = \{A \in N \mid (A \to \varepsilon) \in R\}$, а
                \[\Nullable_{k+1} = \{A \in N \mid \exists (A \to \alpha) \in R\colon \; \alpha \in \Nullable_k^*\},\]
                и
                \[\Nullable = \bigcup_{k=0}^\infty \Nullable_k.\]
                Тогда $\Nullable_0$ легко строится само по себе, а $\Nullable_{k+1}$ легко получается из $\Nullable_k$. При этом $\Nullable_{k+1} \supseteq \Nullable_k$, и если $\Nullable_{k+1} = \Nullable_k$, то для всякого $m \geqslant k$ верно $\Nullable_m = \Nullable_k$. Следовательно
                \[\Nullable = \bigcup_{k=0}^{|N|} \Nullable_k.\]

                Тогда рассмотрим пересоставим множество правил $R$, чтобы получить $R'$. Для всякого правила $A \to \Theta_0 X_1 \Theta_1 \dots X_k \Theta_k$ из $R$, где $\Theta_i \in \Nullable^*$, $X_i \in \Sigma \cup N$, а $k > 0$, добавим в $R'$ правило $A \to X_1 \dots X_k$. (Фактически, одно правило может перевращено в несколько. Например, если есть правило $A \to \Theta_1 \Theta_2$, где $\Theta_1, \Theta_2 \in \Nullable$, то оно будет превращено в правила $A \to \Theta_1 \Theta_2$, $A \to \Theta_1$ и $A \to \Theta_2$.) Тогда всякое старое непустое слово порождается новой грамматикой, так как достаточно в дереве разбора отрубить ветви, которые порождают $\varepsilon$ (это и есть замена у каждой вершины подстановки $A \to \Theta_0 X_1 \dots x_k \Theta_k$ на $A \to X_1 \dots X_k$, так как ветви каждого $\Theta_i$ порождали пустые строки). А всякое новое слово, порождается старой грамматикой, так как в каждой подстановке $A \to X_1 \dots X_k$ у всякой вершины $A$ можно добавить дополнительных детей $\Theta_i$, получая подстановку $A \to \Theta_0 X_1 \dots X_k \Theta_k$ из старых правил, а на каждого ребёнка повесить какое-нибудь дерево, дающее пустую строку. Следовательно, язык новой грамматики --- $L(G) \setminus \{\varepsilon\}$.

                Чтобы вернуть на место пустую строку, добавим $S \to \varepsilon$.

            \item Просто вместо того делать цепочку $A \to B_1 \to \dots \to B_k \to C \to \alpha$ будем теперь сразу писать $A \to \alpha$. Для этого просто добавим в $R$ правила $A \to \alpha$ для всяких $A$ и $\alpha$, для которых есть $B_1, \dots, B_k \in N$ ($k > 0$), что $(A \to B_1) \in R$, $(B_{i} \to B_{i+1}) \in R$, $(B_k \to \alpha) \in A$.

            \item Для всякого $b \in \Sigma$ заведём символ $S_b$ и правило $S_b \to b$, и если есть правило $A \to bX$, то заменим его на правило $A \to S_b X$; аналогично для $A \to X b$.

            \item Заменим $S$ везде на новый нетерминал $S'$, а также добавим правило $S \to S'$. Тогда $S$ не будет использоваться нигде кроме правила $S \to S'$, а значит не будет в подставляемых частях правил. Правило $S \to \varepsilon$ не трогается (не заменяется на $S' \to \varepsilon$).
            
            \item Нарезание правил линейно изменит размер грамматики. Удаление правил $A \to \varepsilon$ линейно изменит размер грамматики. Удаление цепных правил квадратично изменит размер грамматики. Подправление правил $A \to bX$ и $A \to Xb$ линейно изменит размер грамматики. Удаление $S$ из подставляемых частей увеличит грамматику на константу. Итого грамматика изменится не более чем квадратично.
        \end{enumerate}
    \end{proof}

    \begin{theorem}
        Пусть фиксирована грамматика $G$ в нормальном виде Хомского. Тогда для всякой строки $w$ можно за $O(|w|^3)$ времени и $O(|w|^2)$ памяти либо сказать, что $w \notin L(G)$, либо построить дерево разбора $w$.
    \end{theorem}

    \begin{proof}
        Пусть $w = a_1 \dots a_n$. Определим для всяких $i$ и $j$, где $0 \leqslant i < j \leqslant n$,
        \[T_{i, j} := \{A \in N \mid a_{i+1} \dots a_j \in L_G(A)\}.\]
        Тогда заметим, что
        \[T_{i-1, i} = \{A \in N \mid (A \to a_i) \in R\}\]
        и для $i < j-1$
        \[T_{i, j} = \{A \in N \mid \exists (A \to BC) \in R, k \in \{i+1; \dots; j-1\}\colon \; B \in T_{i, k} \wedge C \in T_{k, j}\}.\]
        При этом такое определение $T_{i, j}$ использует другие $T_{\dots}$ с меньшим значением $j - i$. Таким образом можно запустить динамическое вычисление, по одному вычисляя уровни $j - i = \const$ от $j-i = 1$ до $j-i = n$.
        
        Вычисление каждого $T_{i, j}$ проводится за $O(j-i-1)$. При этом всего пар $(i, j)$ примерно $n^2$. Значит это всё можно проделать за $n^3$ времени. Память же выделяемая на каждый $T_{i, j}$ равна $O(1)$, поэтому суммарная память имеет размер $O(n^2)$.

        Чтобы понять, лежит ли $w$ в $L$, надо проверить пусто ли $T_{0, n}$. Чтобы построить дерево разбора, нужно для каждого $A \in T_{i, j}$ вместе с ним хранить правило для подстановки, и тогда дерево восстанавливается спуском вниз.
    \end{proof}

    \begin{lemma}
        В двоичном дереве с $n$ листьями есть поддерево, где листьев $> \frac{1}{3}n$ и $\leqslant \frac{2}{3}n$.
    \end{lemma}

    \begin{proof}
        Будем спускаться от вершины к ребёнку с большим количеством вершин, пока не попадём в вершину, чьё поддерево содержит $\leqslant \frac{2}{3} n$ листьев. Поскольку каждый спуск уменьшает количество листьев не более чем вдвое, то у полученного поддерева $> \frac{1}{3} n$ листьев.
    \end{proof}

    % \begin{corollary}
    %     В двоичном дереве с $n$ выделенными листьями есть поддерево, где выделенных листьев $> \frac{1}{3}n$ и $\leqslant \frac{2}{3}n$.
    % \end{corollary}

    \todo[inline]{Тут должна быть пара страшных алгоритмов, которые мне лень писать. (\href{https://users.math-cs.spbu.ru/~okhotin/teaching/tcs_fl_2021/okhotin_tcs_fl_2021_l8.pdf}{см.})}

    \begin{theorem}[Льюис, Стинрс, Хартманис]
        Пусть фиксирована грамматика $G$ в нормальном виде Хомского. Тогда для всякой строки $w$ можно за $n^{O(\log n)}$ времени и $O((\log n)^2)$ памяти либо сказать, что $w \notin L(G)$, либо построить дерево разбора $w$.
    \end{theorem}

    \begin{theorem}[Руззо, Брент и Гольдшлягер; Риттер]
        % Пусть фиксирована грамматика $G$ в нормальном виде Хомского. Тогда для всякой строки $w$ можно за $n^{O(\log n)}$ времени и $O((\log n)^2)$ памяти либо сказать, что $w \notin L(G)$, либо построить дерево разбора $w$.
        \dots
    \end{theorem}

    \subsection{Неразрешимость задач для грамматик}

    \begin{definition}
        Пусть дана машина Тьюринга $M = (\Sigma, \Gamma, Q, q_0, \delta, q_{acc})$. Пусть также машина $M$ после $i$ шагов вычисления на $w$ находится в состоянии $q_0$, на символе $a$, что слева от неё написана (в хотя бы раз посещённых клетках) строка $u$, а справа --- $w$. Тогда будем обозначать эту конфигурацию машины $M$ за
        \[C_i(M, w) := uqav \in \Gamma^* Q \Gamma \Gamma^*.\]
        Также иногда, если машина и входная строка подразумеваются контекстом будем писать будем просто $C_i$.

        Также если $M$ останавливается на $w$, то будем записывать всю историю вычислений $M$ на $w$ за
        \[C_M(w) := C_0 \# C_1 \# \dots \# C_n \$ C_n^R \# \dots \# C_0^R \in (\Gamma \cup Q \cup \{\#; \$\})^*.\]

        Множество всех историй принимающих вычислений $M$ обозначается за $\VALC(M)$.
    \end{definition}

    \begin{lemma}\label{VALC-grammars-lemma}
        Для всякой машины Тьюринга $M$ существуют и \todo{Смущает фраза ``'эффективно построены'' + ассимптотика?} могут быть эффективно построены такие грамматики $G_1$ и $G_2$, что $L(G_1) \cap L(G_2) = \VALC(M)$. Кроме того, существуют грамматики $G'_1$ и $G'_2$, задающие дополнения этих языков: $L(G'_i) = \overline{L(G_i)}$ для $i \in \{1; 2\}$ --- и потому есть и грамматика, задающая язык $\overline{VALC(M)}$.
    \end{lemma}

    \begin{proof}
        Пусть $M = (\Sigma, \Gamma, Q, q_0, \delta, q_{acc}, q_{rej})$.

        Хотим построить грамматику $G_1$, что она будет строить строку вида
        \[A_{0,c} \# \dots \# A_{n-1,c} \# B_n \$ A_{n-1,n}^R \# \dots \# A_{0,n}^R \# B_0^R,\]
        где $A_{i, c}$, $A_{i, n}$ и $B_i$ являются корректными описаниями конфигураций $M$ (т.е. элементами $\Gamma Q \Gamma \Gamma^*$), и при этом $A_{i,n}$ было бы следующей конфигурацией после $A_{i,c}$, а $B_0$ --- корректной начальной конфигурацией. От $G_2$ хотим, чтобы он распознавал язык $\{w\$w \mid w \in (\Gamma \cup Q \cup \{\#\})^*\}$. Если эти требования будут выполнены, то $L(G_1) \cap L(G_2)$ будет образован словами вида
        \[A_0 \# \dots \# A_n \$ A_n^R \# \dots \# A_0^R,\]
        где $A_{i+1}$ --- конфигурация, следующая за $A_i$.

        Грамматика $G_2$ задаётся просто:
        \begin{align*}
            S &\to aSa \quad (\forall a \in \Gamma \cup \{\#\})&
            S &\to \$.
        \end{align*}

        Грамматика $G_1$ задаётся следующим образом:
        \begin{align*}
            S &\to Aaq_0 \quad (a \in \Sigma)\\
            A &\to Aa \quad (a \in \Sigma)\\
            A &\to S_1 \#\\
            A &\to S_2 \$\\
            S &\to S_1 \# \spacesymbol q_0\\
            S &\to S_2 \$ \spacesymbol q_0\\
            S_1 &\to B\\
            B &\to bBb \quad (b \in \Gamma)\\
            B &\to aqbCb'aq' \quad (a, b \in \Gamma, q \in Q, \delta(q, b) = (q', b', -1))\\
            B &\to qbcCcq'b' \quad (b, c \in \Gamma, q \in Q, \delta(q, b) = (q', b', +1))\\
            C &\to bCb \quad (b \in \Gamma)\\
            C &\to \# S_1 \#\\
            C &\to \# S_2 \$\\
            S_1 &\to qbCb'\spacesymbol q' \quad (b \in \Gamma, q \in Q, \delta(q, b) = (q', b', -1))\\
            B &\to qb\#S_1\#\spacesymbol q'b' \quad (b \in \Gamma, q \in Q, \delta(q, b) = (q', b', +1))\\
            B &\to qb\#S_2\$\spacesymbol q'b' \quad (b \in \Gamma, q \in Q, \delta(q, b) = (q', b', +1))\\
            S_2 &\to D\\
            D &\to bD \quad (b \in \Gamma)\\
            D &\to q_{acc}bE \quad (b \in \Gamma)\\
            E &\to bE \quad (b \in \Gamma)\\
            E &\to \varepsilon
        \end{align*}
        Давайте разбираться в ней.

        Мысленно разделим задачу на 3 части: построение блока $B_0^R$, построение последовательности пар блоков $A_{i, c}$ и $A_{i, n}^R$ и построение блока $B_n$. За них будут ``отвечать'' символы $S$, $S_1$ и $S_2$ соответственно.

        Сначала нужно построить блок $B_0^R$. Заметим, что сам блок $B_0$ выглядит либо как $q_0 w$, где $w$ --- входная строка и $w \neq \varepsilon$ ($w \in \Sigma^*$), либо, если $w = \varepsilon$, $q_0 \spacesymbol$. Первый случай реализуют правила:
        \begin{align*}
            S &\to Aaq_0 \quad (a \in \Sigma)\\
            A &\to Aa \quad (a \in \Sigma).
        \end{align*}
        После этого мы либо должны написать $\#$ и перейти к построению блоков $A_{i, c}$ и $A_{i, n}$, т.е. написать $S_1 \#$, либо (при отсутствии блоков $A_{i, c}$ и $A_{i, n}$) сразу перейти к построению блока $B_n$, т.е. написать $S_2 \$$. Это реализуется правилами
        \begin{align*}
            A &\to S_1 \#\\
            A &\to S_2 \$.
        \end{align*}
        При этом во втором случае ($w = \varepsilon$) и построение блока $B_0^R$ и переход к следующему этапу реализуется правилами
        \begin{align*}
            S &\to S_1 \# \spacesymbol q_0\\
            S &\to S_2 \$ \spacesymbol q_0.
        \end{align*}

        Теперь нужно построить блок \dots
        \todo[inline]{Дописать по \href{https://users.math-cs.spbu.ru/~okhotin/teaching/tcs_fl_2021/okhotin_tcs_fl_2021_l8.pdf\#protolemma.4}{см.}}
    \end{proof}

    \begin{theorem}
        Следующие задачи алгоритмически неразрешимы:
        \begin{enumerate}
            \item пустота пересечения для двух данных грамматик;
            \item однозначность данной грамматики (т.е. отсутствие строк с двумя и более различными деревьями разбора);
            \item определяет ли данная грамматика множество всех строк;
            \item равносильность двух данных грамматик (определяют ли они один и тот же язык);
            \item регулярность языка, порождаемого данной грамматикой.
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        Вспомним, что проверка принимаемого языка машины Тьюринга на пустоту --- алгоритмически неразрешимая задача.

        \begin{enumerate}
            \item Если бы пустота пересечения грамматик была бы алгоритмически разрешимой, то можно было бы построить машину, которая для всякой машины Тьюринга генерировала бы грамматики $G_1$ и $G_2$ как в лемме \ref{VALC-grammars-lemma} и проверяла бы пустоту $L(G_1) \cap L(G_2)$. Такая машина проверяла бы принимающий язык любой машины Тьюринга на пустоту --- противоречие.
            \item Заметим, что для однозначных грамматик $G_1$ и $G_2$ непустота $L(G_1) \cap L(G_2)$ равносильна однозначности грамматики
                \[(\Sigma, N_1 \cup N_2 \cup \{S\}, R_1 \cup R_2 \cup \{S \to S_1; S \to S_2\}, S),\]
                где $G_1 = (\Sigma, N_1, R_1, S_1)$, $G_2 = (\Sigma, N_2, R_2, S_2)$.
                Несложно также заметить, что грамматики $G_1$ и $G_2$ из леммы \ref{VALC-grammars-lemma} однозначны. Значит можно опять построить машину, проверяющую пустоту машины Тьюринга.
            \item Аналогичное противоречие можно получить, если проверять $L(\overline{G}_1) \cup L(\overline{G}_2)$ (что задаётся грамматикой) на равенство $\Sigma^*$.
            \item Аналогичное противоречие можно получить, если проверять равносильность грамматик для $L(\overline{G}_1) \cup L(\overline{G}_2)$ (что задаётся грамматикой) и для $\Sigma^*$.
            \item \dots \todo[inline]{Дописать по \href{https://users.math-cs.spbu.ru/~okhotin/teaching/tcs_fl_2021/okhotin_tcs_fl_2021_l8.pdf\#prototheorem.3}{см.}}
        \end{enumerate}
    \end{proof}

    \section{Сложность вычислений}

    \begin{remark*}
        Если не оговорено обратное, будем подразумевать, что алфавит $\Sigma = \{0; 1\}$.
    \end{remark*}

    \begin{definition}
        \emph{Индивидуальная задача} --- пара $(\text{условие}; \text{решение}) \in \Sigma \times \Sigma$. \emph{Массовая задача} --- некоторое множество индивидуальных задач, т.е. отношение на $\Sigma$.
    \end{definition}

    \begin{remark*}
        Говоря по-человечески, массовая задача --- формализация задачи, которую мы будем пытаться решать машинами Тьюринга и т.п.
    \end{remark*}

    \begin{example}
        Задача нахождения нетривиального делителя числа:
        \[\{(n, d) \mid n \divided d \wedge 1 \leqslant d \leqslant n\}.\]
        Формально, $n$ и $d$ должны записываться строками из $\Sigma^*$.
    \end{example}

    \begin{definition}
        Говорим, что ``алгоритм'' \emph{решает задачу поиска для массовой задачи $R$}, если для всякого условия $x$ (т.е. просто строки $x \in \Sigma^*$, называемой ``условием'') он находит решение $w$ (т.е. строку $w \in \Sigma^*$), удовлетворяющее $(x, w) \in R$.
    \end{definition}

    \begin{definition}
        Всякой массовой задаче $R$ можно сопоставить язык
        \[L(R) := \{x \mid \exists w \colon \; (x, w) \in R\}.\]
        Т.е. можно строить задачу распознавания (есть ли для данного $x$ решение).
    \end{definition}

    \begin{definition}
        Детерминированная машина Тьюринга (ДМТ) --- это совокупность
        \begin{itemize}
            \item входного алфавита $\Sigma$ --- конечного алфавита входных данных,
            \item символ начала строки $\triangleright \notin \Sigma$,
            \item символ пробела (нетронутой клетки) $\_ \notin \Sigma \cup \{\triangleright\}$,
            \item конечного множества внутренних состояний $Q$,
            \item начального состояния $q_S$, принимающего состояния $q_Y$ и конечного состояния $q_N$,
            \item количества рабочих лент $k$
            \item и функции переходов $\delta: Q \times (\Sigma \cup \{\triangleright; \_\})^{k+1} \to Q \times \{-1; 0; +1\} \times ((\Sigma \cup \{\triangleright; \_\}) \times \{-1; 0; +1\})^{k+1}$.
        \end{itemize}
        Это та же МТ, но теперь есть входная лента (read-only), выходная лента (write-only) и $k$ независимых рабочих лент. И все ленты бесконечны, но только вправо. При этом ставтся условия о том, что ДМТ намеренно не выезжает за пределы ленты и не рисует и не стирает символы $\triangleright$.

        Входными данными программы является конечная строка $s_1 \dots s_l$, которая превращается в запись $(a_{i, j})_{\substack{i \in \NN\\ 0 \leqslant j \leqslant k + 1}}$ на лентах по правилу
        \[
            a_{i, j} = 
            \begin{cases}
                \triangleright& \text{ если } i = 0\\
                s_i& \text{ если } j = 0 \wedge 1 \leqslant i \leqslant l\\
                \_ & \text{ иначе.}
            \end{cases}
        \]
        Состояние каждого момента вычисления --- это совокупность
        \begin{itemize}
            \item состояния ленты $(a_{i, j})_{\substack{i \in \NN\\ 0 \leqslant j \leqslant k + 1}}$, где $a_{i, j} \in \Sigma$, $a_{0, j} = \triangleright$ и все $a_{i, j}$ кроме конечного числа являются пробелами $\_$,
            \item положений головок $(n_j)_{0 \leqslant j \leqslant k + 1}$ на лентах и
            \item состояния машины $q \in Q$.
        \end{itemize}
        Состояния начального момента вычислений образуется Из
        \begin{itemize}
            \item состояния ленты, полученного из входных данных,
            \item положений головок по умолчанию $(n_j)_{0 \leqslant j \leqslant k + 1} = (0)_{0 \leqslant j \leqslant k + 1}$,
            \item начального состояния машины $q_S$.
        \end{itemize}
        Каждым шагом состояние $((a_{i, j}), (n_j), q)$ заменяется на состояние $((a'_{i, j}), (n'_j), q')$, где $a'_{i,j} = a_{i,j}$ для всех $(i, j)$ кроме $(n_j, j)$ для $1 \leqslant j \leqslant k+1$ и
        \[
            (q', n'_0 - n_0, a'_{n_1, 1}, n'_1 - n_1, \dots, n'_k - n_k, a_{n_{k+1}, k+1}, n'_{k+1} - n_{k+1}) = \delta(q, a_0, \dots, a_k).
        \]
    \end{definition}

    \begin{definition}
        ДМТ \emph{принимает} входное слово, если она заканчивает работу свою работу в $q_Y$ и \emph{отвергает} -- если в $q_N$. ДМТ $M$ \emph{распознаёт язык} $A$, если принимает все $x \in A$ и отвергает все $x \notin A$. Пишем $A = L(M)$. ДМТ может также \emph{вычислять функцию} (решать задачу поиска). Значением этой функции над данном входе будем считать содержимое входной ленты после достижения $q_Y$.

        \emph{Время работы} $M$ на входе $x$ --- количество шагов (применений инструкций) до достижения $q_Y$ или $q_N$. \emph{Используемая память} --- суммарное крайнее правое положение всех головок на рабочих лентах.
    \end{definition}

    \begin{definition}
        \emph{Универсальная машина Тьюринга} --- такая МТ $M(a, x)$, которая принимает описание $a$ машины $M_a$ и её вход $x$, и выдаёт тот же результат, что и $M_a(x)$.
    \end{definition}

    \begin{lemma}
        Вместо любого алфавита можно рассматривать только двусимвольный.
    \end{lemma}

    \todo[inline]{Надо написать?}

    % \begin{proof}
        
    % \end{proof}

    \begin{lemma}
        Двусторонняя лента эмулируется на односторонней с константным замедлением. Т.е. для всякой ДМТ $M$ на $k$ двусторонних лентах есть ДМТ $M'$ на $k$ односторонних лентах, выдающая те же ответы с константным замедлением. При этом $|\sigma(M')| = O(|\sigma(M)|^2)$, а сама $M'$ алгоритмически построима за полиномиальное от $\sigma(M)$ время.
    \end{lemma}

    % \begin{proof}
    %     Давайте просто положительную часть ленты хранить на чётных значениях, а отрицательную --- на нечётной. Следовательно, в таком случае один такт вычислений моделируется не более тремя ходами, а для каждого старого перехода добавится три дополнительных состояния, т.е. количество новых состояний будет $|Q|(1 + 3(|\Sigma| + 2))$. Следовательно, запись машины возрастёт не более чем в $(1 + 3(|\Sigma| + 2))^2$ раз, т.е. $|\sigma(M')| = O(|\sigma(M)|^2)$ При этом запись $M'$ можно построить за $O(|\sigma(M')|)$ действий, каждое из которых будет заключаться в пробежке по $\sigma(M)$, изменении промежуточных данных и принятии решений о том, что написать в вывод. Каждое действие будет выполняться за полиномиальное от $|\sigma(M)|$ время, а значит и всё построение будет за полиномиальное время.
    % \end{proof}

    \begin{theorem}
        Существует универсальная ДМТ $M(a, x)$, использующая лишь две рабочих ленты и выдающая результат за время $O(f(|a|) t \log(t))$, где $t$ --- время работы $M_a$ на $x$, а $f$ --- некоторая функция.
    \end{theorem}

    \todo[inline, caption={На лекции было сопосатвление алгоритма, а не единый на всех алгоритм.}]{На лекции не было показано алгоритмического построения автомата, который читает любую машину и выполняет её код. Вместо этого всякой машине сопоставлялась новая на двух лентах.}

    \begin{proof}
        Давайте попытаемся эмулировать ДМТ нескольких лент на двух лентах. Одна из лент будет вспомогательной. Сначала заметим, что мы можем хранить все $k$ лент на одной, если писать $i$-ую ленту на клетках с отсатком $i$ по модулю $k$.
        
        Первая оптимизация времени работы в том, что будем двигать не головки по лентам, а ленты вдоль фиксированной головки. Т.е. будем сдвигать каждую из $k$ компонент нашей ленты в зависимости от результата функции перехода.
        
        Но двигать всю ленту очень долго. Поэтому будем оптимизировать время работы задачи ``сдвинуть компоненту на 1''. Для этого будем хранить ленту (компоненту) в разреженном состоянии. Для этого будем хранить на ленте последовательность блоков $L_n \dots L_1 H R_1 \dots R_n$, где размер блоков $L_i$ и $R_i$ --- $2^i$, а блок $H$ состоит из одного элемента, на который смотрит головка. Будем делать так, чтобы в каждый момент в блоках $L_i$ и $R_i$ было либо $0$, либо $2^{i-1}$, либо $2^i$ элементов хранимой ленты (всё остальное занимают специальные пробелы), а также для всякого $i$ в блоках $L_i$ и $R_i$ было суммарно ровно $2^i$ элементов.

        Тогда пусть нам нужно сдвинуться влево. Найдём минимальное $m$, что блок $L_m$ заполнен хотя бы на половину. Если такого блока нет, то поднимем $n$ на один, создав полный блок $L_n$ и пустой блок $R_n$ (в таком случае $m = n$). Тогда половину из блока $L_m$ (это $2^{m-1}$) символов перенесём в блоки $L_{m-1}$, \dots, $L_1$ и $H$, что $L$-блоки будут заполнены на половину (т.е. $2^{m-1}$ будет разделено на части как $2^{(m-1)-1} + 2^{(m-2)-1} + \dots + 2^{(m-(m-1))-1} + 1$). При этом символы из $H$, $R_1$, \dots, $R_{m-1}$ будут перенесены в $R_m$ как новая половина (где $R_m$ как раз пуст хотя бы на половину).

        Каждая такая операция будет произведена за $O(2^m)$ при этом ближайшие $2^{m-1}-1$ шагов блоки $L_m$ и $R_m$ тронуты не будут (т.е. блоки $L_i$ и $R_i$ будут тронуты не чаще однго раза в $2^{i-1}$ ходов). При этом максимальный номер блока не больше $\log_2(t)$. Следовательно, время работы алгоритма будет не более 
        \[\sum_{i=1}^{\log(t)} C \cdot 2^i \cdot \frac{t}{2^{i-1}} = 2C \cdot t \log (t) = O(t \log(t)).\]
    \end{proof}

    \begin{definition}
        \emph{Недетерминированная машина тьюринга (НМТ)} получается из детерминированной таким же образом, как НКА из ДКА. Т.е. $\delta$ становится многозначной функцией, и появляется, так называемое, \emph{дерево вычислений}, а мы говорим, что машина принимает вход, если есть вычисление, заканчивающееся принятием (состоянием $q_Y$).

        При этом если есть вычислимая за разумное время (конкретно, за собственное, т.е. двоичная запись $f(n)$ должно вычисляться за $f(n)$) верхняя граница (от $n$) на время работы какой-нибудь принимающей ветви для всякой входной строки длины $n$, то мы можем встроить ``будильник'': измерить длину входа, вычислить и записать верхнюю границу и на каждом ходу уменьшать этот счётчик, чтобы когда он достигнет нуля, насильно отвергнуть вход. Тогда у всякого входы длины $n$ время работы любой ветви вычислений будет длиться не дольше данного времени (формально, не больше $O(f)$, где $f$ --- данная функция верхней границы). Действительно, если хранить время в двоичной записи, и всё время пробегаться от разряда единиц до ближайшего ненулевого разряда, уменьшать его на единицу, потом идти назад, заменяя все нули на единицы. То каждый раз придётся делать не более $O(\log_2(f))$ ходов. Но реально, количество ходов равно $\Theta(i)$, где $i$ --- номер найденного разряда. Но к нему надо ходить раз в $2^{-i}$ раз. Следовательно, количество ходов в среднем будет
        \[
            \Theta\left(\sum_{i=0}^{\log_2(f)} 2^{-i}\right)
            = \Theta\left(\frac{1 - 2^{-\log_2(f)-1}}{1-2^{-1}}\right)
            = \Theta\left(2 - \frac{1}{2f}\right)
            = \Theta(1).
        \]
        При этом ранее отвергаемые входы будут отвергаться, так как принимающих ветвей не появилось, а ранее принимаемые --- приниматься, так как есть принимающее вычисление, попадающее в рамки будильника, и следовательно, которое останется принимающим. Таким образом можно считать, что время работы машины на любом входе заданной длины ограничено независимо от направления вычисления.
    \end{definition}

    \begin{definition}[альтернативное]
        НМТ --- это ДТМ, принимающая в себя два аргумента: $x$ и $w$, и принимающая строку $x$ тогда и только тогда, когда существует $w$, что вход $(x, w)$ принимается. 
    \end{definition}

    \begin{definition}
        Функция $t: \NN \to \NN$ называется \emph{конструируемой по времени}, если
        \begin{itemize}
            \item $t(n)$ не убывает,
            \item $t(n) \geqslant n$,
            \item двоичная запись $t(|x|)$ вычислима по входу $x$ на ДМТ за $t(|x|)$ шагов.
        \end{itemize}

        $\DTime(f)$ --- класс языков $L$, для которых есть ДМТ $M$, принимающая $L$ за время $O(f)$. $\NTime(f)$ --- класс языков $L$, для которых есть НМТ $M$, принимающая $L$ за время $O(f)$.
        \[\Pclass := \bigcup_{c \geqslant 1} \DTime(n^c), \qquad \NPclass := \bigcup_{c \geqslant 1} \NTime(n^c)\]
    \end{definition}

    \begin{definition}
        Массовая задача $R$ \emph{полиномиально ограничена}, если существует полином $p$, ограничивающий длину кратчайшего решения:
        \[\forall x (\exists u \colon (x, u) \in R \Rightarrow \exists w \colon ((x, w) \in R \wedge |w| \leqslant p(|x|))).\]
        Массовая задача $R$ \emph{полиномиально проверяема}, если существует полином $q$, ограничивающий время проверки решения: для любой пары $(x, w)$ можно проверить принадлежность $(x,w) \overset{?}{\in} R$ за время $q(|(x, w)|)$.

        $\widetilde{\NPclass}$ --- класс задач поиска полиномиально ограниченных полиномиально проверяемых.
        
        $\widetilde{\Pclass}$ --- класс задач поиска из $\widetilde{\NPclass}$, разрешимых за полиномиальное время, т.е. задаваемых отношениями $R$, такими, что $\forall x \in \{0; 1\}^*$ за полиномиальное время можно найти $w$, для которого $(x, w) \in R$.
    \end{definition}

    \begin{definition}[альтернативное]
        $\NPclass$ --- класс языков (задач распознавания), задаваемых полиномиально ограниченными полиномиально проверяемыми массовыми задачами, т.е. $\NPclass = \{L(R) \mid R \in \widetilde{\NPclass}\}$. Иначе говоря, $L \in \NPclass$, если имеется полиномиально ограниченное полиномиально проверяемое $R$, такая, что $\forall x \in \{0; 1\}^* \; x \in L \Longleftrightarrow \exists w\colon (x, w) \in R$.
    \end{definition}

    \begin{definition}
        \emph{Сведение языков по Карпу (``many-one'')}: $L_1 \to L_2$. Если имеется полиномиально вычислимая (на ДМТ) функция $f: \Sigma^* \to \Sigma^*$, что для всякого $x \in \Sigma^*$ верно $x \in L_1 \Leftrightarrow f(x) \in L_2$.
        
        \emph{Сведение задач поиска по Левину}: $R_1 \to R_2$. Если имеются полиномиально вычислимые функции $f: \Sigma^* \to \Sigma^*$ и $g, h: (\Sigma^*)^2 \to \Sigma^*$, что
        \begin{itemize}
            \item для всяких $x, y \in \Sigma^*$ верно $R_1(x, y) \Rightarrow R_2(f(x), g(x, y))$,
            \item для всяких $x, y \in \Sigma^*$ верно $R_2(f(x), y) \Rightarrow R_1(x, h(f(x), y))$.
        \end{itemize}

        Пусть есть какое-то отображение $f: \Sigma^* \to \Sigma^*$. \emph{Оракульной машиной Тьюринга} $M^{\cdot}$ называется (обычно детерминированная) МТ, где выделены состояния $q_{\mathrm{in}}$ и $q_{\mathrm{out}}$, но не определён переход в $\delta$ из состояния $q_{\mathrm{in}}$. За $M^f$ обозначается ``машина'', которая из всех состояний кроме $q_{\mathrm{in}}$ считает по правилам $M^\cdot$, а при попадании в $q_{\mathrm{in}}$ она определённым образом двигает головки, но на выделенной (третьей) ленте заменяет всё содержимое $s$ на $f(s)$ (и это считается одним ходом).

        \emph{Сведение чего-угодно по Тьюрингу}: $A \to B$. Если имеется оракульная полиномиальная по времени машина $M^\cdot$, что $M^B$ решает $A$. То есть если $A$ --- язык, то имеется ввиду $A = L(M^B)$, а если $A$ --- массовая задача, то $M^B$ её решает; если $B$ --- язык, то под $M^B$ подразумевается $M^{\chi_B}$, а если массоваая задача, то подразумевается $M^f$, где $f$ решает задачу поиска в $B$.
    \end{definition}

    \begin{theorem}\ 
        \begin{enumerate}
            \item Классы $\Pclass$ и $\NPclass$ замкнуты относительно сведений по Карпу.
            \item Классы $\Ptilde$ и $\NPtilde$ замкнуты относительно сведений по Левину.
            \item Классы $\Pclass$ и $\Ptilde$ замкнуты относительно сведений по Тьюрингу.
        \end{enumerate}
    \end{theorem}

    \begin{proof}
        \begin{enumerate}
            \item Если $L_1$ сведён по Карпу к $L_2$, то задачу проверки $x \mathbin{\overset{?}{\in}} L_1$ можно за полиномиальное время на ДМТ свести к задаче $f(x) \mathbin{\overset{?}{\in}} L_2$. Т.е. из определения следует, что $x \in L_1$ тогда и только тогда, когда $f(x) \in L_2$, а $f(x)$ можно вычислить за полномиальное время. Следовательно, если вторая решается за полиномиальное время на ДМТ (НМТ), то и исходная задача решается за полиномильное время на ДМТ (НМТ).

            \item Если $R_1$ сведена по Левину к $R_2$, то задачу поиска для $x$ в $R_1$ можно за полиномиальное время на ДМТ свести к задаче поиска для $f(x)$ в $R_2$. Т.е. из определения следует, что у $x$ есть решение в $R_1$ тогда и только тогда, когда у $f(x)$ есть решение в $R_2$. При этом если мы нашли решение $y_2$ входа $f(x)$ в $R_2$, то за полиномиальное время мы можем получить решение $h(f(x), y_2)$ входа $x$ в $R_1$, а если хотим проверить решение $y_1$ входа $x$ в $R_1$, то за полиномиальное время можем свести задачу к проверке решения $g(x, y_1)$ входа $f(x)$ в $R_2$.
            
                Следовательно, если $R_2$ полиномиально ограничено, то и $R_1$ полиномиально ограничено (так как $f$ на строке полиномиального размера сможет сделать строку только полномиального размера), если $R_2$ полиномиально проверяема, то и $R_1$ полиномиально проверяема, а если $R_2$ полномиально разрешима, то и $R_1$ полиномиально разрешима.

            \item Без нормального доказательства.
            
            % Если нечто $f$ полиномиально вычислимо, то можно заменить $M^f$ на полноценную машины Тьюринга $N$, которая делает то же самое, но работает медленнее $M^f$ на $c_M \cdot t_f \circ i$, где $c_M$ --- количество вызовов $f$, $t_f$ --- время вычисления $f$, а $i$ --- максимальный размер входа $f$. Так как $c_M$ не превышает время работы $t_M$ машины $M^f$, то полиномиально; $i$ не больше количества написанных символов, т.е. $t_M$, значит полиномиально; $t_f$ полиномиально по определению. Следовательно, время работы $N$ --- $t_M + c_M \cdot t_f \circ i$ --- полиномиально.

            %     Следовательно, если $B \in \Pclass$, а $A$ сводится к $B$ по Тьюрингу, то $A \in \Pclass$. Если 
        \end{enumerate}
    \end{proof}

    \begin{definition}
        Пусть дан класс задач $C$. Тогда задача $X$ называется
        \begin{itemize}
            \item \emph{$C$-трудной}, если всякая задача $Y \in C$ сводима к $X$,
            \item \emph{$C$-полной}, если она $C$-трудная и лежит в $C$.
        \end{itemize}
    \end{definition}

    \begin{theorem}
        Если задача $A$ $\NPclass$-трудна и лежит в $\Pclass$, то $\Pclass = \NPclass$.
    \end{theorem}

    \begin{proof}
        Если есть $\NPclass$-полная задача $B$, то для неё
        \[B \in \Pclass \Leftrightarrow \Pclass = \NPclass.\]
        Поскольку $A$ лежит в $\Pclass \subseteq \NPclass$, то она $\NPclass$-полная, а тогда $\Pclass = \NPclass$.
    \end{proof}

    \subsection{$\NPclass$-полные задачи}

    \begin{definition}[задача об ограниченной остановке]
        $\BHtilde(\langle M, x, 1^t \rangle, w)$ принимает в себя запись НМТ $M$, входную строку $x$, $t$ в унарном виде и подсказку $w$ и отвечает, правда ли $M(x, w)$ принимает и делает это за $t$ шагов.
    \end{definition}

    \begin{theorem}
        Задача об ограниченной остановке $\NPtilde$-полна, а соответствующий ей язык $\NPclass$-полон.
    \end{theorem}

    \begin{proof}
        Покажем $\NPtilde$-трудность. Пусть имеется $R \in \NPtilde$ и $M^*$ будет проверять $R$, а также дано $x$. Просится найти $\omega$, что $M^*(x, \omega) = 1$. Поскольку $M^*$ полиномиально проверяет пару $(x, \omega)$, то есть некоторый полином $p(|x|)$, за время которого этот ввод будет принят. Тогда построим функцию
        \[f(x) := \langle M^*, x, 1^{p(|x|)} \rangle.\]
        Очевидно, что результат функции $f$ построим за полиномиальное время от $|x|$. Также определим функции
        \[g(x, \omega) = h(y, \omega) := \omega,\]
        которые тоже вычисляются за полиномиальное время. При этом заметим, что если $(x, \omega) \in R$, то это значит $M^*$ остановится и примет $(x, \omega)$ за $p(|x|)$ шагов, а тогда $(\langle M^*, x, 1^{p(|x|)} \rangle, \omega) = (f(x), g(x, \omega))$ является решением задачи $\BHtilde$. А если $(f(x), \omega) = (\langle M^*, x, 1^{p(|x|)} \rangle, \omega)$ решает задачу $\BHtilde$, то $M^*$ примет $(x, \omega) = (x, h(f(x), \omega))$ за полиномиальное время. Таким образом мы получили сведение $R$ к $BHtilde$ по Левину. Также принадлежность $BHtilde$ к $\NPtilde$ очевидна, так как существует универсальная НМТ.

        $\NPclass$-полнота $\BH$ следует из $\NPtilde$-полноты $\BHtilde$.
    \end{proof}

    \todo[inline, caption={Тут есть нюанс, \dots}]{Тут есть нюанс, который я не понял: бывают решения $\omega$ неполиномиальной (более чем полиномиальной) длины (точнее их длина вылезает за рамки $p(|x|)$), но которые принимаются $M^*$ за полномиальное от $|(x, \omega)|$ (от длины обеих строк!) время (это и есть определение полиномиальной проверяемости). Но при этом $M^*$ очевидно не примет этот вход, так как $M^*$ не то что принять не успеет за время $p(|x|)$ эту пару, она не прочтёт её, а больше времени нет, так как задача $\BHtilde$ обрежет её на этом моменте.
    \vspace{12pt}
    
    \textbf{То есть формальная придирка: верность перехода $R(x, \omega) \Rightarrow \BHtilde(f(x), g(x, \omega))$ пояснена неверно.}
    \vspace{12pt}
    
    \textit{Пример}: пусть $R = \{(1^x; 1^y) \mid x < y\}$. (Вспомним, что $2^n \geqslant n$.) Тогда понятное дело строку $(1^n; 1^{2^n}) \in R$, $(f(1^n), g(1^n, 1^{2^n})) = (\langle M^*, 1^n, 1^{p(n)} \rangle, 1^{2^n})$ (где $M^*$ --- тривиальная машина, принимающая $R$, а $p$ --- любой полином, за который можно хоть какую-нибудь пару принять) не принадлежит $\BHtilde$, так как $M^*$ не успеет прочитать, а значит, и принять $(1^n, 1^{2^n})$ за полиномиальное время (точнее не будет успевать с некоторого $n$), а значит это не сведение по Левину.}

    \begin{definition}
        \emph{Булева схема} $C$ --- это ориентированный граф без циклов, где вершины делятся на три типа: ``входы'', ``операции'' и ``операции-выходы'', во входные ничего не входит, из выходных -- не выходит, а в вершинах-операциях стоят бинарные, унарные или 0-арные операции, и их входная степень совпадает с арностью оператора в них. Тогда \emph{значение $C$ на некотором входе $w$} --- значение последовательности выходов, где во входы записали значения из $w$ (по некоторому определённому контекстом соответствию), а в каждой вершине значение определяется рекуррентно как значение оператора в этой вершине, применённого к значениям из входящих в него по рёбрам вершин (соответствие между вершинами и аргументами оператора тоже является частью структуры булевой схемы).

        Также проще булеву схему определять просто как набор из нескольких булевых выражений нескольких (одних и тех же) переменных.

        Тогда задача $\CURCUITSATtilde$ --- есть множество пар $(C, w)$ булевых схем $C$ с одним выходом и входом, которые выполняют схему (схема на этом выходе даёт $1$: $C(w) = 1$).
    \end{definition}

    \begin{theorem}
        $\BHtilde$ сводится к $\CURCUITSATtilde$, а значит $\CURCUITSATtilde$ $\NPtilde$-полна.
    \end{theorem}

    \begin{proof}
        
    \end{proof}

    % \section{Теория информация}
\end{document}