 \documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\emptyset
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

\let\yield\Rightarrow

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prpfrom[#1]{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }
\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0} }
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem)  } }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.  } }
\def\prsubrstar{\medskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$)  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}
\begin{document}
\centerline{\LARGE Задание 8}

\medskip

\begin{center}
	{\Large Замкнутость КС-языков}
\end{center}

\bigskip



{\bf Ключевые слова }\footnote{минимальный необходимый объем понятий и навыков по
этому разделу)}:{\em  язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. %примеры нерегулярных языков;
%поиск подстрок, алгоритм Кнута- Морисса- Пратта.

%языки скобочных выражений (языки Дика). 
}

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

Одна из целей изучения леммы о накачке для регулярных языков -- упрощение понимания леммы о накачке для КС-языков, где она уже жизненно необходима. Сформулируем лемму.

\begin{Lemma}
	Для любого КС-языка $L$ существует константа $p$, такая что для любого слова $w$ из языка $L$, такого что $|w| \geq p$ существует разбиение слова $w = xuyvz$, причём
	\begin{itemize}
		\item $|uyv| \leq p$
		\item $|uv|\geq 1$
		\item $\forall i \geq 0: w_i = xu^iyv^iz \in L$
	\end{itemize}
\end{Lemma} 

\begin{Example} 
	Язык $L = a^nb^nc^n$ не является КС-языком.
\end{Example}
\begin{proof}
	Предположим, что $L\in \CFL$, тогда для некоторого числа $p$ выполнена лемма о накачке. Рассмотрим слово $w = a^pb^pc^p$ (заметим, что число $p$ является параметром, а не каким-то конкретным числом). Тогда подслово $uyv$ из разбиения слова $w$, существующего по лемме о накачке, либо состоит из одинаковых букв ($a^l$ или $b^l$ или $c^l$) или имеет вид $a^lb^r$ или $b^lc^r$. Три различные буквы подслово $uyv$ содержать не может, поскольку его длина ограниченна числом $p$. Но тогда $uv$ -- слово, в котором нет одной из трёх букв. Пксть это будет буква $c$ для определённости. Взяв $i = 0$, получаем, что по лемме о накачке $w_0 = a^{n-k}b^{n-m}c^n \in L $, при этом $k+m \geq 1$, откуда следует, что слово $w_0$ не принадлежит языку $L$. 
\end{proof}

\upr Покажите, что КС-языки замкнуты относительно объединения.

\upr Покажите, что КС-языки не замкнуты относительно пересечения.

\upr Покажите, что КС-языки не замкнуты относительно дополнения.

\prp Покажите, что КС-языки замкнуты относительно пересечения с регулярными. То есть, если $L \in \CFL, R \in \REG$, то $L \cap R \in \CFL $.

\prpstar Решите предыдущую задачу используя представление КС-языка не МП-автоматом, а грамматикой.

\smallskip
\noindent \textbf{Указание:} пусть регулярный язык задан конечным автоматом, тогда постройте грамматику $G^\prime$ для языка $L \cap R$, используя грамматику $G$, порождающую язык $L$, которая будет иметь нетерминалы вида $[qXp]$, где $q \in Q_\A$, $X \in N_G$.

\prp Докажите, что язык $\{ w\,|\, |w|_a = |w|_b = |w|_c \} \subseteq \{a,b,c\}^*$ не является КС-языком.

\prp Докажите, что язык $\{ w\,|\, w = uu, u \in \Sigma^* \}, \Sigma = \{a,b\}$,  не является КС-языком.

\prp Верно ли, что язык $\{ a^nb^mb^nc^m \,|\, n, m \geq 0 \}$ является КС-языком? В случае положительного ответа построить КС-грамматику или МП-автомат для данного языка.

\end{document}