 \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\varnothing
\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{}

\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}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{prvar}


\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\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;({\rm\Rnum{\theprvar}}).  }\setcounter{subproblem}{0} }
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}. \setcounter{subproblem}{0} }

\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\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}{\sf \thesubproblem .} }
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\sf \thesubproblem)} }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{$\mathsf{\thesubproblem^*}$\negthickspace.  } }
\def\prsubrstar{\medskip\noindent\stepcounter{subproblem}{\sf $\mathsf{\thesubproblem^*}$)  } }

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem 
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0} 
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0} 
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem 
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}
%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$ 
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}



\def\prend{
	\bigskip
	
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Other text macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%прочее

\def\xquad{\noindent\phantom{X}\quad}

\begin{document}
\centerline{\LARGE Задание 6}

\medskip

\begin{center}
	{\Large Контекстно-свободные языки}
\end{center}

\bigskip



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

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


\section{Задачи}

\prp
 Решите уравнения с регулярными коэффициентами. В каждом пункте нужно выполнить три задания: 

 \xquad 1) найти частное решение;\\
 \xquad 2) найти решение, минимальное по включению;\\
 \xquad 3) найти все решения.


\begin{comment}

	 $$\prsub\;\; X=((101)^*+110^*)X;$$

	$$\qquad\qquad\qquad\quad\;\;\;\prsub\;\; X=(00+01+10+11)X+(0+1+\eps);$$

	$$\qquad\prsub\;\;
	\left\{
	\begin{array}{rcl}
	Q_0&=& Q_0 0 + Q_1 1 +\varepsilon \\
	Q_1&=& Q_0 1 + Q_2 0\\
	Q_2&=&Q_1 0 + Q_2 1.\\
	\end{array}
	\right.
	$$

	
\end{comment}


\begin{align*}
	\prsub&\;\; X=((101)^*+110^*)X;\\
	\\
	\prsub&\;\; X=(00+01+10+11)X+(0+1+\eps);\\
	\\
	\prsub&\;
	\left\{
	\begin{array}{rcl}
	Q_0&=& Q_0 0 + Q_1 1 +\varepsilon \\
	Q_1&=& Q_0 1 + Q_2 0\\
	Q_2&=&Q_1 0 + Q_2 1.\\
	\end{array}
	\right.
\end{align*}

\prend

\begin{Def}
	Грамматика называется линейной, если в правые части правил вывода входит не более одного нетерминала. 
\end{Def}

\medskip

\prp  Верно ли, что для любой линейной грамматики $G$, $L(G) \in \REG$?

\prend

\prp Язык $L^=$ является языком всех слов с равным числом символов $a$ и $b$.

 \prsub  Покажите индукцией\footnote{Другие доказательства, кроме индукции, не принимаются.} по длине слова, что КС-грамматика с правилами $S \to SS  \mid  aSb  \mid  bSa  \mid   \eps$  порождает язык $L^=$.


 \prsub   Покажите, что язык $L^=$ не порождается никакой линейной КСГ.

\prend

\begin{Def}
	Палиндромами называют слова, которые одинаково читаются слева-направо и справа-налево, например, «ротор».
\end{Def}

На семинаре мы показали, что язык палиндромов является КС-языком.

\medskip

\prp  Покажите, что язык всех непалиндромов (то есть дополнение языка палиндромов) является КС-языком.

\prend

Ещё раз напоминаю, что задачи, помеченные $\dagger$ являются дополнительными, поэтому списывать их из книжек -- бессмысленное увеличение энтропии.

\begin{Def}
	Для языка $L \subseteq \{\sigma_1,\sigma_2,\ldots,\sigma_n\}^* = \Sigma_n^*$ и языков $L_{\sigma_1}, L_{\sigma_2}, \ldots, L_{\sigma_n} \subseteq \Sigma_n^* $, подстановкой  в $L$ языков $L_{\sigma_1},\ldots, L_{\sigma_n}$ назовём язык $L^{\prime} $, такой что для всех слов $w = w[1]\ldots w[n]$ из языка $L$ справедливо $ L_{w[1]}L_{w[2]}\ldots L_{w[n]} \subseteq L^{\prime}$
\end{Def}

\prdag Доказать, что регулярные языки замкнуты относительно операции подстановки.

\begin{Def}
	Даны алфавиты $\Sigma$ и $\Delta$. Для языка $L \subseteq \Sigma\times \Delta$ определены операции проекции на $\Sigma^*$ и $\Delta^*$. Проекцией $L$ на $\Sigma^*$ называется язык $L_\Sigma = \{ w \in \Sigma^*\, |\, \exists v \in \Delta^* : (w,v) \in L \}$. Проекция $L$ на $\Delta^*$ определяется аналогичным образом.
\end{Def}

\prdag Доказать, что регулярные языки замкнуты относительно операции проекции.

\begin{Def}
	Для языка $L_\Sigma \subseteq \Sigma^*$, $\Delta$-целиндром называется язык $L$, такой что $L = \{w\, |\, w = (u, v), u \in L_\Sigma, v \in \Delta^* \}$
\end{Def}

\prdag Показать, что $\Sigma$-проекция $\Delta$-цилиндра $L$ есть $L$. Доказать, что регулярные языки замкнуты относительно операции цилиндра.





\end{document}