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

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
\usepackage{indentfirst}
%%\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\yields{\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 Задача $\mathbf{\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 Задание 9}

\medskip

\begin{center}
	{\Large Приведение Контекстно-Свободных грамматик}
\end{center}

\bigskip

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

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




\section{Приведённые КС-грамматики}

\begin{comment}
	

Как вы могли уже убедиться, при выполнении операций с КС-грамматиками, не все правила КС-грамматики могут быть использованы в выводе хотя бы одного слова из языка $L(G)$. 

Так, если из состояния $p$ автомата $M$ не выталкивается\footnote{Т.е. нет правил вида $\delta(p,u,Z) \vdash (q,\eps)$. } ни один из символов стека, то из нетерминала $[q_0Z_0p]$ не выводится ни одного слова. Таким образом, грамматика построенная по автомату в общем случае содержит слишком много лишних правил и даже лишних нетерминалов. И на практике от них очень часто требуется избавиться. 
\end{comment}

Вообще говоря, не все нетерминалы из описания КС-грамматики могут встретиться в выводе некоторого слова. Такие нетерминалы могут возникнуть в ходе различных алгоритмических преобразований --  ниже мы встретимся с такими преобразованиями. Для удобства, в частности для корректности работы многих алгоритмов, необходимо от таких бесполезных нетерминалов избавиться.


Выделяют два типа бесполезных нетерминалов. Нетерминал $A$ называется \emph{бесплодным}, если язык $L(G_A) = \{ w \,|\, A \yield^* w \}$ пуст. Нетерминал $A$ называется \emph{недостижимым}, если ни одна цепочка вида $\alpha A\beta$ не выводится из $S$. Грамматика $G$ называется \emph{приведённой}, если она не содержит недостижимых и бесплодных нетерминалов.

Для того, чтобы удалить все бесплодные символы нужно действовать по следующему алгоритму:
\begin{itemize}
	\item Множество $V_0 = T$.
	\item Множество $V_{i+1}$ строим по $V_i$ следующим образом. Положим в начале $V_{i+1} = V_i$. Если для правила $A \to \alpha $ справедливо $\alpha \in V^*_i$, то добавим нетерминал $A $ в множество $ V_{i+1}$.
	\item Как только $V_{i+1} = V_i$, объявляем $N = V_i\setminus T$, удаляем из $P$ все правила, которые содержат нетерминалы не из $V_i$ и заканчиваем работу.
\end{itemize}

\upr Доказать корректность данного алгоритма.
\medskip

Чтобы удалить все недостижимые символы нужно действовать по следующему алгоритму:

\begin{itemize}
	\item Множество $V_0 = {S}$
	\item Множество $V_{i+1}$ строим по $V_i$ следующим образом. Положим в начале $V_{i+1} = V_i$. Если $A \in V_i$ и $A \to \alpha B \beta$, то добавим нетерминал $B $ в множество $ V_{i+1}$.
	\item Как только $V_{i+1} = V_i$, объявляем $N = V_i$, удаляем из $P$ все правила, которые содержат нетерминалы не из $V_i$ и заканчиваем работу.
\end{itemize}
\upr Доказать корректность данного алгоритма.

\medskip

Для того чтобы по грамматике $G$ построить приведённую грамматику $G^\prime$, необходимо сначала удалить все бесплодные символы, а потом удалить все недостижимые символы. Действовать надо именно в таком порядке, потому что иначе после удаления бесплодных символов могут появится новые недостижимые символы, а после удаления недостижимых, новые бесплодные появиться не могут









\section{Задачи}

\prp $L = \{ xcy\,|\, x,y\in \{a,b\}^*; x \neq y^R \}$. Постройте детерминированный МП-автомат, распознающий язык $L$. Если не получается построить детерминированный, постройте хотя бы недетерминированный.

\medskip

%\prdag $L = \{ xy\,|\, x,y\in \{a,b\}^*; x \neq y \}$. Постройте  МП-автомат, распознающий язык $L$. 

%\medskip

\prpstar Пусть $L$ -- КС-язык. Докажите, что язык ${\rm Pref}(L) = \{ u\,|\, \exists v \in \Sigma^* : uv \in L\}$, язык префиксов всех слов языка $L$, является КС-языком.

\medskip

\prp Постройте по грамматике $G$ приведённую грамматику. Все построения должны быть выполнены строго по алгоритму. Грамматика $G$ задана правилами:
\vspace{-3ex}

\begin{multicols}{2}
	\begin{align*}
		S &\to A \mid B \mid C \mid E \mid AG \\
		A &\to C  \mid aABC \mid \eps\\
		B &\to bABa \mid aCbDaGb \mid \eps\\
	\end{align*}

	\begin{align*}
		C &\to BaAbC \mid aGD \mid \eps\\
		F &\to aBaaCbA \mid aGE\\
		E &\to A\\			
	\end{align*}	
\end{multicols}
\vspace{-2ex}

\prp Пусть $G$ -- грамматика в нормальной форме Хомского. Докажите, что любое слово длины $ n \geq 1$ выводимо ровно за $2n-1$ шаг.

\newpage

\prp Постройте по грамматике $G$ грамматику в нормальной форме Хомского.
\vspace{-5ex}

\begin{multicols}{2}
	\begin{align*}
		S &\to ABC \mid SBAC\\
		A &\to S \mid B \mid aCB \mid \eps		
	\end{align*}

	\begin{align*}
		B &\to ab \mid b \mid A\\
		C &\to A \mid B \mid aBbA		
	\end{align*}	
\end{multicols}


%$$ S \to ABC \mid SBAC ;  A \to S \mid B \mid aCB \mid \eps ; C \to A \mid B \mid aBbA ; B \to ab|b \mid A  $$


\begin{comment}
	S \to A|B|C|E|AG\qquad\qquad  & A \to C |aABC|\eps\\
	B \to bABa|aCbDaGb|\eps & C \to BaAbC|aGD\eps\\
	F \to aBaaCbA|aGE & E \to A\\		
	
\end{comment}





\end{document}