 \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\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{Теорема Хомского-Шютценберже}

Обозначим $D_n$ язык правильных скобочных выражений (язык Дика) с $n$ типами скобок. Язык $D_n$ определён над размеченым алфавитом $\Sigma = \Sigma_n\cup \bar \Sigma_n$ -- в $\Sigma_n$ входят открывающие скобки, в $\bar \Sigma_n$ закрывающие.

Будем говорить, что КС-язык $L \subseteq \Delta^* $ задан в представлении Хомского-Шютценберже, если определены язык Дика $D_n$, регулярный язык $R \subseteq \Sigma^*$ и морфизм $h : \Sigma^* \to \Delta^*$ и $L = h(R\cap D_n)$.

\begin{known}[Хомский, Шютценберже, 1963]
	Язык $L \subseteq \Delta^*$ является контекстно-свободным тогда и только тогда, когда
	существуют такое $n$, регулярный язык $R$ и морфизм $h : \Sigma^* \to \Delta^*$, что  $ h(D_n\cap R) = L$.

	
\end{known}
\begin{proof}
	
	Пусть КС-язык задан грамматикой $G = (N,\Sigma,P,S)$, где $N$ -- множество нетереминалов, $\Sigma$ -- алфавит, $P$ -- правила вывода, а $S$ -- аксиома. Без ограничения общности будем считать, что $G$ не содержит $\eps$-правил, кроме быть может $S \to \eps$, причём тогда нетерминал $S$ больше не входит в правые части правил.
	
	
	Зафиксируем язык $D_n$, где $n = |N| + |\Sigma|$. Поставим в соответствие каждому элементу  $X $ из $ N\cup \Sigma$  пару скобок $[_X$ и $_X]$. Неформально опишем язык $R$, описав все регулярные события\footnote{Свойства слов, проверяемые ДКА.}, которые допустимы в $R$.  Сначала опишем вспомогательную конструкцию. Для каждого нетерминала $A$, определим множество $R_A $, в которое, для каждого правило  $A \to X_1X_2\ldots X_n$ грамматики $G$, входит соответствующее слово $w = [_{X_n}[_{X_{n-1}}\ldots[_{X_{n-i}}\ldots[_{X_1}$.  
	
	$$
		R_A = \{ w = [_{X_n}[_{X_{n-1}}\ldots[_{X_{n-i}}\ldots[_{X_1} \,|\, A \to X_1X_2\ldots X_n \in P \}
	$$
	\newpage
	Теперь опишем регулярные события, задающие $R$.
	\begin{itemize}
		\item Любое слово из $R$ начинается со скобки $[_S$;
		\item После закрывающей скобки $]_A$ идёт слово из $R_A$, где $A \in N$;
		\item После открывающей скобки $[_\sigma $ может идти закрывающая скобка $ \,_\sigma]$;
		\item После закрывающей скобки $]_X $ может идти закрывающая скобка $ \,_Y]$, где $X, Y \in N\cup T$.
	\end{itemize}
	 
	
	Таким образом, если слово $w$ лежит в языке $D_n\cap R$, то оно является кодированием левого вывода некоторого слова $u$ в грамматике $G$: по подслову $]_A[_{X_n}[_{X_{n-1}}\ldots[_{X_{n-i}}\ldots[_{X_1}\ _{X_1}]$ однозначно восстанавливается правило $A \to X_1X_2\ldots X_n$.  Осталось определить морфизм $h$, который и даёт переход от слова $w \in R\cap D_n$ к слову $u \in L$. Он устроен следующим образом:
	$h(_\sigma]) = \sigma\ \forall \sigma \in \Sigma$, иначе $h(_X]) = \eps\ \forall X \in N$ и $h([_X) = \eps\ \forall X \in N\cup \Sigma$. Таким образом мы показали, что любой КС-язык представим в форме ХШ и привели эффективный алгоритм построения по языку формы ХШ.
	
	Пусть теперь язык задан в представлении ХШ $(D_n,R,h)$. Построим по нему МП-автомат, который будет недетерминировано угадывать прообраз $h^{-1}(w)$ слова $w$ и проверять удовлетворяет ли он регулярному ограничению $R$ и является ли он правильным скобочным выражением. Поскольку такой автомат можно построить, то язык, заданный в форме ХШ является КС-языком.
	
	%\textbf{\{ Не знаю стоит ли писать более строго, по-моему утверждения здесь достаточно очевидны.\}}
\end{proof}

\upr В доказательстве есть тонкое место про кодирование левого вывода. Для достаточной строгости это утверждение надо доказать по индукции. Проведите это доказательство.

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

\section{От МП-автоматов к КС-грамматикам}

Опишем алгоритм построения КС-грамматики $G$ по $N$-автомату\footnote{допускающему по пустому стеку} $M = (\Sigma, \Gamma, Q, q_0, Z_0, \delta, \es)$. $G = (N,T,P,S)$, причём

\begin{itemize}
	\item $T = \Sigma$;
	\item $N = \{ [qZp]\,|\, q,p \in Q, Z \in \Gamma \}$
	\item Если $\delta(q,u,Z) \vdash (q_1,Y_1,Y_2,\ldots Y_n)$, то $P$ содержит правила $[qZp] \to u[q_1Y_1r_1][r_1Y_2r_2]\ldots[r_{n-2}Y_{n-1}r_{n-1}][r_{n-1}Y_np]$, $u \in \Sigma\cup\eps$, для всевозможных наборов состояний $r_1,r_2,\ldots,r_{n-1}\in Q$. Если $\delta(q,u,Z) = (p,\eps)$, то $P$ содержит правило $[qZp] \to u $.
	\item  $\forall p \in Q\ S \to [q_0Z_0p] \in P$. 
\end{itemize}

Обратите внимание, что слова $u$ и $v$ которые будут фигурировать дальше в правилах либо буквы, либо пустые слова.
Идея алгоритма состоит в том, что левый вывод  слова $w$ в грамматике $G$ соответствует успешной последовательности конфигураций на входе $w$ автомата $M$.  Состояние $q$ в первом слева нетерминале и есть состояние, в котором находится автомат при обработке слова. Если автомат находясь в состоянии $q$, видя на верхушке стека $Z$, переходит в состояние $q_1$, и при этом кладёт что-то в стек, то в выводе грамматики нетерминал $[qZp]$ раскрывается как $u[q_1Y_1r_1][r_1Y_2r_2]\ldots[r_{n-2}Y_{n-1}r_{n-1}][r_{n-1}Y_np]$, таким образом в выводе грамматики слева опять оказывается текущее состояние автомата $q_1$, а также в нетерминалах закодировано содержимое его стека. Если же, автомат выталкивает символ $Y_1$ из стека читая $v$ и переходит из состояния $q_1$ в $r_1$, то в грамматике есть правило $[q_1Y_1r_1] \to v$,  таким образом $[qZp] \yield_L uv[r_1Y_2r_2]\ldots[r_{n-2}Y_{n-1}r_{n-1}][r_{n-1}Y_np]$ и опять таки в промежуточном шаге вывода закодировано текущее состояние автомата и содержание его стека. Вторые состояния в кодировке нетерминалов $[qZ\underline p]$ нужны для того, чтобы обеспечить корректность кодировки протокола переходов от одной поверхностной конфигурации к другой.


Перейдём к формальной части доказательства. Покажем что $ L(M) \subseteq L(G)$.

\begin{Claim}\label{conf_to_cfl}
	Если $(q_0, uv, Z_0) \vdash^* (q,v, Y_1Y_2\ldots Y_n)$, тогда для всевозможных состояний $r_1,r_2,\ldots r_n, p \in Q$ справедливо \[S \yield^*_L u[qY_1r_1][r_1Y_2r_2]\ldots[r_{n-2}Y_{n-1}r_{n-1}][r_{n-1}Y_np].  \]
\end{Claim}
\begin{proof}
	Докажем индукцией по числу тактов $k$ работы автомата $M$. 
	
\noindent\textbf{\underline{База:}} $k = 1$. Тогда, $(q_0, uv, Z_0) \vdash (q,v, Y_1Y_2\ldots Y_n)$, переход происходит за один такт работы. Построим соответствующий вывод. Сначала применим правило $S \to [qZp]$, а далее раскрываем нетерминал $[qZp]$ -- соответствующее  правило есть в $G$ по алгоритму построения.
\smallskip

\noindent\textbf{\underline{Переход:}} пусть утверждение верно для $k = n$ -- покажем, что оно верно для $k = n+1$. Пусть $(q_0, uv, Z_0) \vdash^* (q,v, Y_1Y_2\ldots Y_n)$ и переход выполнен за $n+1$ такт работы автомата $M$. Рассмотрим конфигурацию, соответствующую $n$-ому такту автомата. Пусть она имеет вид $(q_1,u_lv, Z_1Z_2\ldots Z_N)$ и при этом $(q_1,u_lv, Z_1Z_2\ldots Z_N) \vdash (q,v, Y_1Y_2\ldots Y_n)$. По предложению индукции,
 \[S \yields_L u_1\ldots u_{l-1}[q_1Z_1r^\prime_1][r^\prime_1Z_2r^\prime_2]\ldots[r^\prime_{n-2}Z_{n-1}r^\prime_{n-1}][r^\prime_{n-1}Z_Np]\]
За такт работы автомат раскрывает ровно один нетерминал, таким образом автомат делает переход $\delta(q_1,u_l,Z_1) \vdash (q,Y_1Y_2\ldots Y_m)$,  а $Y_{m+1} = Z_2, Y_{m+2} = Z_3, \ldots$ Но тогда в грамматике по построению есть правило \[[q_1Z_1r^\prime_1] \to u_l[qY_1r_1][r_1Y_2r_2]\ldots[r_{m-1}Y_mr_m][r^\prime_1Z_2r^\prime_2]\]
Тогда в результате переобозначения нетерминалов и в силу произвольности всех состояний, кроме $q$ получаем, что
\begin{align*}
 S &\yields_L  u_1\ldots u_{l-1}[q_1Z_1r^\prime_1][r^\prime_1Z_2r^\prime_2]\ldots[r^\prime_{n-2}Z_{n-1}r^\prime_{n-1}][r^\prime_{n-1}Z_Np] \yield_L \\ &\yield_L u_1\ldots u_{l-1}u_l[qY_1r_1][r_1Y_2r_2]\ldots[r_{n-2}Y_{n-1}r_{n-1}][r_{n-1}Y_np].
\end{align*}
Переход доказан.
\end{proof}

Из доказанного утверждения в частности следует, что если $(q_0,w,Z_0) \vdash^* (q,\eps,\eps)$, то $S \yield_L w$. Таким образом, мы показали, что $L(M) \subseteq L(G)$.

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

\upr Доказать, что $L(G) \subseteq L(M)$.


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

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

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

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

Для того, чтобы удалить все бесплодные символы нужно действовать по следующему алгоритму:
\begin{itemize}
	\item Множество $V_0 = T$.
	\item Множество $V_{i+1}$ строим по $V_i$ следующим образом. Если для правила $A \to \alpha $ справедливо $\alpha \in V^*_i$, то $A \in 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$ следующим образом. Если $A \in V_i$ и $A \to \alpha B \beta$, то $B \in 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$. Если не получается построить детерминированный, постройте хотя бы недетерминированный.

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

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

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

	\begin{align*}
		C &\to BaAbC|aGD|\eps\\
		F &\to aBaaCbA|aGE\\
		E &\to A\\			
	\end{align*}	
\end{multicols}


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


\prpstar Проверьте по алгоритму Кока-Янгера-Касами порождает ли грамматика $G$ из предыдущей задачи слово $abaaab$.

\prp Язык $L$ задан в ХШ-представлении: $(D_2, \Sigma^*, \varphi)$, где $D_2$ -- язык Дика с двумя типами скобок, регулярное ограничение $\Sigma^*$ означает, что на слова не накладывается регулярное ограничение, морфизм $\varphi$ определим следующим образом $\varphi : [_1 \to a; \,_1] \to b; [_2 \to b; \,_2] \to a  $. Докажите или опровергните, что $L = \{ w\,|\, |w|_a = |w|_b\}$.

\prp Возьмите любой детерминированный МП-автомат, допускающий по пустому стеку, как минимум с двумя состояниями, распознающий КС-язык, не являющийся регулярным. Можете взять язык из примера в задании $7$. Постройте по МП-автомату КС-грамматику, сделайте из неё приведённую грамматику. Будет ли она однозначна?



\end{document}