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

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
\usepackage{indentfirst}

\usepackage{tabu}
\usepackage{enumerate}

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

%%%%%%%%%%%%%%  Fancy underline & comments %%%%%%%%%%%%%%%%
\usepackage[normalem]{ulem}
\usepackage{color} 
\usepackage{xcolor}

\usepackage{enumerate}

\usepackage{marginnote}

\newcommand{\malert}[2][]{\marginpar{\color{WildStrawberry}\ifthenelse{\equal{#1}{}}{\vspace{-2ex}}{\vspace{-2ex}\vspace{#1}}  #2}}
\definecolor{DarkGray}{HTML}{666666}
\newcommand{\mcomment}[2][]{\marginpar{\ifthenelse{\equal{#1}{}}{\vspace{-2ex}}{\vspace{-2ex}\vspace{#1}} \color{DarkGray} #2}}
\newcommand\reduline{\bgroup\markoverwith
      {\textcolor{red}{\rule[-0.5ex]{2pt}{0.4pt}}}\ULon}

\usepackage{dashrule}

\newcommand\alertuline{\bgroup\markoverwith
      {\color{WildStrawberry}{\hdashrule[-0.5ex]{2pt}{0.4pt}{1pt}}}\ULon}

\newcommand\commentuline{\bgroup\markoverwith
			      {\color{DarkGray}{\hdashrule[-0.5ex]{2pt}{0.4pt}{1pt}}}\ULon}


\newcommand\reddasheduline{\useunder{\uuline}{\bfseries}{\textbf}}

\newcommand{\acomment}[1]{
	\bigskip
	\centerline{\framebox{
	\begin{minipage}{13cm}
		\begin{center}
			\emph{
					#1
			}
		\end{center} 
	\end{minipage}
	}}
	\bigskip
}


\newcommand{\spoileralert}[1]{
	\bigskip
	\centerline{\framebox{
	\begin{minipage}{8cm}
		 \vspace*{2em}
		\begin{center}
			\emph{
					#1
			}
		\end{center} 
		\vspace*{1em}
	\end{minipage}
	}}
	\bigskip
}

\def\salert{\spoileralert{Spoiler Alert!}}


%%%%%% Shortcuts %%%%%

\let\rpar\reversemarginpar
\let\aul\alertuline
\let\cul\commentuline


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


%%%%%%%%%%%%%%%%%%%%%%%% Enumerations %%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

%%%%%%%%%%%%%%%%%%%%% EOF Enumerations %%%%%%%%%%%%%%%%%%%%%

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

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


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


%\usepackage{xkeyval}

%\define@key{myupr}{label}{}
%\def\myupr[#1]#2{
%	\setkeys{myupr}{#1}
%	#
%}

\usepackage{pgfkeys}


\newcommand\tstkeys[3][]{%
  #2 \pgfkeys{/tstkeys,label,#1,print} #3 11%
}
\pgfkeys{
 /tstkeys/.is family, /tstkeys,
 label/.default = {},
 label/.store in = \tstlabel,
% mandatory/.default = {(invalid)},
% mandatory/.store in = \tstkeysmandatory,
 print/.code = {{\medskip\noindent\refstepcounter{uproblem}\label{\tstlabel}{\bf Упражнение \theuproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}{\smallskip} },
}



\newcommand\prtemplate[2][]{%
 \pgfkeys{/prtemplate,name,counter,label,type,#1,print}\ifthenelse{\equal{#2}{}}{}{#2 }% 
}
\pgfkeys{
 /prtemplate/.is family, /prtemplate,
 name/.default = {},
 name/.store in = \prname,
 label/.default = {},
 label/.store in = \prlabel,
 counter/.default = {problem},
 counter/.store in = \prcounter,
 type/.default={},
 type/.store in=\prtype,
 print/.code =  {\medskip\noindent\ifthenelse{\equal{\prlabel}{}}{\stepcounter{\prcounter}}{\refstepcounter{\prcounter}\label{\prlabel}}{\bf \ifthenelse{\equal{\prname}{}}{}{\prname~}\prwrite[\prtype]\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
}

\newcommand{\prwrite}[1][]{\ifthenelse{\equal{#1}{star}}{$\mathbf{\arabic{\prcounter}}^{*}$\!\!.}
	{\textbf{\arabic{\prcounter}.}}}

%\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;
\newcommand\prsubrtemplate[2][]{%
 \pgfkeys{/prsubrtemplate,label,display,type,#1,print}\ifthenelse{\equal{#2}{}}{}{#2 }% 
}
\pgfkeys{
 /prsubrtemplate/.is family, /prsubrtemplate,
 label/.default = {},
 label/.store in = \prlabel,
 display/.default={},
 display/.store in=\prdisplay,
 type/.default={},
 type/.store in=\prstype,
 print/.code =  {\ifthenelse{\equal{\prdisplay}{inline}}{}{\medskip\noindent}\ifthenelse{\equal{\prlabel}{}}{\stepcounter{subrproblem}}{\refstepcounter{subrproblem}\label{\prlabel}}{\bf \prsubrwrite[\prstype]\;}}
}
\newcommand{\prsubrwrite}[1][]{\ifthenelse{\equal{#1}{star}}{{\bf \asbuk{subrproblem}$^{*}$\!)}}
	{\ifthenelse{\equal{#1}{o}}{{\bf \asbuk{subrproblem}$^{\circ}$\!)}}
		{\textbf{\asbuk{subrproblem})}}}}

\newcommand\prsubr[1][]{\prsubrtemplate[#1]{}}
\newcommand\prsubru[1][]{\prsubrtemplate[#1,type=o]{}}
\newcommand\prsubrinline[1][]{\prsubrtemplate[#1,display=inline]{}}
\newcommand\prsubruinline[1][]{\prsubrtemplate[#1,type=o,display=inline]{}}



%\pgfkeys{/line cap/.is choice}
%\pgfkeys{/line cap/round/.style={\pgfsetbuttcap}}

\newenvironment{quiz}[1][]{\prtemplate[name={Контрольный вопрос}, counter={kvproblem}, #1]{}}{\medskip}
\newenvironment{upr}[1][]{\prtemplate[name={Упражнение}, counter={uproblem}, #1]{}}{\medskip}
%\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
%\newcommand\pr[1][]{\prtemplate[#1]}
\newcommand\pr[1][]{\prtemplate[#1]{}}

		%\medskip\noindent\stepcounter{kvproblem}{\bf Контрольный вопрос \thekvproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
%			








\def\prinline{\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}

\def\pru{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
\def\pruinline{\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}

\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
\def\prpfrom[#1]{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

\def\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;$\langle${\rm\Rnum{\theprvar}}$\rangle$.}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}.\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

%\newenvironment{upr}
%	{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}{\smallskip}

%\newenvironment{quiz}
%		{\medskip\noindent\stepcounter{kvproblem}{\bf Контрольный вопрос \thekvproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}{\smallskip}

	
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{\sf \thesubproblem .}\;}
%\def\prsubr{\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;}
%\def\prsubru{\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem}$^\circ$\!)}\;}
%\def\prsubrinline{\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;}
%\def\prsubruinline{\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem}$^\circ$\!)}\;}
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{$\mathsf{\thesubproblem}^*$\negthickspace.}\;}

\def\prsubrstar{\medskip\noindent\stepcounter{subrproblem}{$\text{\bf \asbuk{subrproblem}}^*\text{\textbf{)}}\mathbf{}$}\;}
\def\prsubrstarinline{\noindent\stepcounter{subrproblem}{$\text{\bf \asbuk{subrproblem}}^*\text{\textbf{)}}\mathbf{}$}\;}


\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}\setcounter{subrproblem}{0}
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0}\setcounter{subrproblem}{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}\setcounter{subrproblem}{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{\Pr}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{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{\Prstar}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
		\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf$\mathbf{\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}\setcounter{subrproblem}{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}\setcounter{subrproblem}{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
%	\bigskip
}


\def\prskip{
	\medskip
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Comments and Other Meta  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\comments}[2][Комментарий]{\medskip\noindent{\bf #1:\;}{\textsl{#2}}}

\newcommand{\keywords}[1]{\noindent\textbf{Ключевые слова:} \textsl{#1}}

\newcommand{\answ}[1]{\textbf{Ответ:} \textsl{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Comments and Other Meta  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\def\quotient{\backslash\negthickspace\sim}
\begin{document}
\centerline{\LARGE Задание 9}

\medskip

\begin{center}
	{\Large Приложение КС-грамматик для сжатия данных. \\[2ex] Преобразования КС-грамматик-1}
\end{center}

\bigskip

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

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

\comments[Внимание]{Это двухнедельное задание. Оно может быть скорректированно, если мы что-то не успеем в следующую пятницу. Но все задачи из этого задания будут выданы.}


\section{Приложение КС-грамматик для\\ сжатия данных} 
  
Некоторые алгоритмы сжатия строк можно описать в терминах КС-грамматик. Мы рассмотрим два таких алгоритма. Первый из них носит название <<Straight-line program>> (SLP) и состоит в следующем. Слово $w$ описывают с помощью КС-грамматики $G_w$, которая порождает единственное слово: $L(G_w) = w$. Грамматику $G_w$ называют <<Straight-line grammar>> (SLG); этим же термином иногда называют и описываемый нами частный случай метода сжатия SLP: в роли программ выступают КС-грамматики.

\begin{Example}
	Грамматика, описываемая правилами
	$$ S \to A_1A_1,\quad A_1 \to A_2A_2, \quad A_2 \to A_3A_3,\quad \ldots \quad A_{n-1} \to A_nA_n, \quad A_n \to a, $$
	порождает единственное слово $a^{2^n}$. Длина описания грамматики не превосходит $cn$, для некоторой константы $c > 0$, то есть имеет длину порядка логарифма от длины порождаемого слова, что является хорошим коэффициентом сжатия.
\end{Example}                                                                    

\prp Постройте SLG~$G_n$, порождающую слово $$a^nba^{n-1}ba^{n-2}b\ldots ababa^2ba^3b\ldots a^nb.$$
Длина описания $G_n$ должна быть $cn, c > 0$. В качестве решения можно построить SLG~$G_5$.

\begin{Remark}\label{SLPremark}
	Преимуществом описанного метода сжатия является возможность эффективной проверки сжатого слова на регулярные события без разархивации. То есть  существует алгоритм, получающий на вход описание НКА~$\A$ и SLP~$G_w$ и проверяющий непустоту пересечения $L(\A)\cap L(G_w)$ за полиномиальное время от длин описаний $\A$ и $G_w$, но не $w$.	
\end{Remark}

\prpstar Постройте описанный выше алгоритм и докажите его корректность.
\medskip

Мы описали общий метод сжатия SLP, но не описали пока алгоритма сжатия строк в грамматики. Таких алгоритмов существует несколько, одним из популярных алгоритмов сжатия такого типа является алгоритм Лемпеля--Зива--Велча (Lempel--Ziv--Welch, LZW). Опишем работу этого алгоритма на примере сжатия конкретной строки: $a ab abb b ba aba abab$.                                                                                                                                               
%$a ab abb b ba aba abab$
%\begin{align*}
%	a&\mid& 	ab&\mid&	abb&\mid&	b&\mid&		ba&\mid&	aba&\mid& abab&\\	
%	A_1&\mid& A_2&\mid&		A_3&\mid&	A_4&\mid&	A_5&\mid&	A_6&\mid& A_7&
%\end{align*}
%\begin{align*}
%	&a&&\mid 	&ab\,&&\mid&	&abb&&\mid&	&b\;\,&&\mid&		&ba\,&&\mid&	&aba&&\mid& &abab\\  
%	&A_1&&\mid &A_2&&\mid&	&A_3&&\mid& &A_4&&\mid&		&A_5&&\mid&	&A_6&&\mid& &A_7\;
%\end{align*}
\medskip
\begin{figure}[h]

\begin{multicols}{6}
	\phantom{A}
	\columnbreak
	\phantom{A}	
	\columnbreak
	\columnbreak
	\phantom{A}	
	\columnbreak
	\phantom{A}	
	\columnbreak
	\phantom{A}		
	{\renewcommand{\figurename}{Таблица}\caption{}\label{LZWtable}}%\phantom{\!}
\end{multicols}
\vspace{-2ex}

\centerline{\textbf{Разбиение строки алгоритмом LZW}}
\smallskip

	\begin{center}
	\extrarowsep=3pt
	\begin{tabu} to 24em { *{6}{X[$c$,m]|}X[$c$,m] }%  |>{\bfseries}X[c,m]?*{4}{X[c,m]|} >{\ldots}X[1,c,m]|  
		  a& ab& abb& b& ba& aba& abab\\
	   \tabucline{1-7}
		  A_1& A_2& A_3& A_4& A_5& A_6& A_7
	\end{tabu}    
	\end{center}                           
%   \caption{Разбиение строки алгоритмом LZW}\label{LZWtable} }
\end{figure} 

Таблица~\ref{LZWtable} представляет собой словарь. Она устанавливает взаимно однозначное соответствие между нетерминалами и словами: слово $w_i$ в построенной в итоге грамматике будет выводимо из $A_i$ и только из $A_i$ (но не обязательно за один шаг вывода). Опишем алгоритм заполнения таблицы-словаря.

\begin{enumerate}[1.]
	\item В начале работы словарь пуст, слово $u$ -- необработанный суффикс слова~$w$ -- совпадает с $w$, $i=1$.
	\item Алгоритм ищет максимальный префикс $x$ необработанной части входа~$u$, который был добавлен в словарь. 
	\item Если $u = xav, a \in \Sigma$, то алгоритм добавляет в словарь слово $w_i = xa$, удаляет префикс $xa$ из $u$, увеличивает $i$ на 1 и переходит к предыдущему шагу, если $u \neq \eps$. Если же $u = \eps$, алгоритм заканчивает работу.
	\item Если $u = x$ и $x$ уже соответствует некоторому нетерминалу~$A_j$, то алгоритм добавляет в грамматику правило $A_i \to A_j$ и завершает работу. Обратим внимание, что $x$ на этом шаге является суффиксом $w$.
\end{enumerate}
                                          
\begin{comment}
	Во второй строке таблицы~\ref{LZWtable} стоят нетерминалы $A_i$; из каждого $A_i$ выводимо слово $w_i$, стоящее над ним (но не обязательно за один шаг вывода). Таблица~\ref{LZWtable} строится по следующему алгоритму. В начале работы алгоритма множество нетерминалов $\{A_i\}$ и множество слов $\{w_i\}$ пусты. Алгоритм обрабатывает $w$ буква за буквой пока обрабатываемая часть слова совпадает с началом некоторого $w_i$ и как только совпадение прекращается, алгоритм добавляет обработанное подслово в ячейку таблицы и продолжает работу до конца слова~$w$. Если последнее обрабатываемое подслово будет совпадать с некоторым $w_i$, то в таблице будет записан его нетерминал $A_i$.	
\end{comment}

Так, первая буква слова $w$ всегда будет приписана нетерминалу $A_1$; далее в нашем примере за первой $a$ идёт подслово $ab$, которое приписывается нетерминалу~$A_2$, поскольку первая буква подслова $a$ уже была приписана $A_1$; далее идёт подслово $abb$ -- подслово $ab$ уже было приписано~$A_2$ и т.д.

Нетрудно заметить, что искомая SLG имеет вид
$$ S \to A_1A_2\ldots A_7, \quad A_1 \to a,	\quad A_2 \to A_1b,	\quad A_3 \to A_2b, \quad     $$
$$ A_4 \to b, \quad A_5 \to A_4a, \quad A_6 \to A_2a,\quad A_7 \to A_6b. $$
Но как её эффективно построить алгоритмически, равно как и таблицу~\ref{LZWtable}? Для этого воспользуемся техникой, базирующейся на конечных автоматах.

\begin{figure}[h]
	
\begin{center}
	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]%, every state/.style={inner sep=3pt,minimum size=0pt}
	  %\draw[help lines] (0,0) grid (3,2);
	  \node[state,initial]  (eps)                      {$q_0$};
	  \node[state]          (a) [below right = of eps] {$A_1$};
	  \node[state]          (b) [above right =of eps] {$A_4$};
	  \node[state]          (ba) [right =of b] {$A_5$};
	  \node[state]          (ab) [above right = 2cm of a] {$A_2$};
	  \node[state]          (abb) [right = 3cm of ab] {$A_3$};
      \node[state]          (aba) [below = of abb] {$A_6$};
	  \node[state]          (abab) [right = 3cm of aba] {$A_7$};
	 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
	  \path[->] 
		(eps)	edge      node	{$a$}	(a)
			 	edge	  node	{$b$}	(b)
		(a)		edge      node	{$b$}	(ab)		
		(b)		edge      node	{$a$}	(ba)
		(ab) 	edge      node	{$a$}	(aba)     
		     	edge	  node	{$b$}	(abb)
		(aba) 	edge      node	{$b$}	(abab);     				  		
	\end{tikzpicture}
	\begin{comment}
		\node[state with output]          (a) [below right = of eps] {$a$ \nodepart{lower} $A_1$};
	  	\node[state with output]          (b) [above right =of eps] {$b$ \nodepart{lower} $A_4$};
	  	\node[state with output]          (ba) [right =of b] {$ba$  \nodepart{lower} $A_5$};
	  	\node[state with output]          (ab) [above right = 2cm of a] {$ab$  \nodepart{lower} $A_2$};
	  	\node[state with output]          (abb) [right = 3cm of ab] {$abb$  \nodepart{lower} $A_3$};
      	\node[state with output]          (aba) [below = of abb] {$aba$  \nodepart{lower} $A_6$};
	   	\node[state with output]          (abab) [right = 3cm of aba] {$abab$  \nodepart{lower} $A_7$};
	\end{comment}
\end{center}
	\caption{LZW-автомат}\label{LZWautomata}
\end{figure} 

\begin{comment}
	Алгоритм строит автомат (рис.~\ref{LZWautomata}) следующим образом. Сначала есть только начальное состояние $q_0$ и ни один переход не определён -- обозначим этот автомат~$\A_0$. Алгоритм подаёт на вход ДКА~$\A_i$ необработанную часть слова $w$ пока тот может её прочесть. Пусть автомат $\A_i$ не может выполнить переход по символу $a$ из состояния $A_j$. Тогда алгоритм достраивает его до автомата $\A_{i+1}$ путём добавления перехода $A_j \xrightarrow{a} A_{i+1}$, а в грамматику при этом добавляется правило $A_{i+1} \to A_ja$, после чего алгоритм переходит к следующему шагу. Как только слово $w$ будет обработано, алгоритм добавляет к грамматике правило $S \to A_1 \ldots A_n$, где $n$ -- номер последнего автомата последовательности, и возможно добавляет правило $A_n \to A_j$ аналогично шагу 4 алгоритма построения таблицы-словаря.	
\end{comment}

В процессе построения SLG по алгоритму LZW мы строим LZW-автомат (рис.~\ref{LZWautomata}), который, по сути, реализует словарь. Однако, помимо стандартных функций словаря, LZW-автомат помечает каждую вершину, кроме начальной, нетерминалом~$A_i$, устанавливая тем самым соответствие между словом $w_i$ и состоянием автомата:  $q_0 \xrightarrow{w_i} A_i$.

\medskip

\noindent\textbf{Алгоритм.} В начале работы алгоритма словарь (реализуемый LZW-автоматом) пуст; обозначим через~$u_i$ необработанную часть входа -- в начале работы $u_1 = w$. 

Алгоритм находит кратчайший префикс $x_i \neq \eps$ слова $u_i = x_iy_i$, которого ещё нет в словаре и добавляет его в словарь, помечая вершину, соответствующую этому слову новым нетерминалом $A_i$. Алгоритм повторяет этот процесс удалив из $u_i$ префикс $x_i$ ($u_{i+1} = y_i$) до тех пор пока либо слово~$u_{i+1}$ не окажется пустым, либо $u_i$ не будет содержаться в словаре. При этом, если префикс~$x_i$ добавляется в словарь, то $x_i = va, a \in \Sigma$. В процессе добавления слов в словарь, алгоритм добавляет правила в грамматику согласно следующим правилам.

\begin{enumerate}[(1)]
	\item Если $v= \eps$, то алгоритм добавляет в грамматику правило $A_i \to a$. %и слово $a$ ещё не было добавлено в словарь
	\item Если слово~$v$ непусто, то оно уже было добавлено в словарь и ему соответствует некоторый нетерминал~$A_j$. Тогда алгоритм добавляет в грамматику правило $A_i \to A_ja$.
	\item Если слово~$u$ целиком содержится в словаре, то ему уже соответствует нетерминал $A_j$ -- в этом случае алгоритм добавляет правило $A_i \to A_j$.
	\item После окончания построения LZW-автомата, алгоритм добавляет к грамматике правило $S \to A_1 \ldots A_n$, где $n$ -- номер последнего добавленного нетерминала.
\end{enumerate}

 
\medskip

\noindent\textbf{Корректность.} Пусть $x_1,\ldots, x_{n-1}, (x_n)$ -- последовательность слов добавленных в словарь в порядке добавления. Мы взяли $x_n$ в скобки, поскольку последняя небработанная часть входа~$u_n$ могла целиком оказаться в словаре, тогда мы полагаем, что $x_n = u_n$. %Будем полагать, что все слова последовательности различны, случай, когда последнее слово~$x_n$ совпадает с некоторым~$x_i$ отличается несущественно от общего. 
По построению, $w = x_1x_2\ldots x_n$, поскольку каждое слово $x_i$ последовательно отрезали от $w$ пока не осталось пустое слово. 

Каждая вершина словаря, кроме $q_0$, помечена некоторым нетерминалом~$A_i$. Докажем по индукции, что каждый нетерминал~$A_i$ порождает слово~$x_i$, которое соответсвует вершине графа~LZW-автомата.% автомата-словаря, то есть из начального состояния $q_0$ по слову~$x_i$ автомат переходит в $A_i$. 
\smallskip

\noindent\underline{База: $i=1$}. Поскольку словарь в начале не содержит слов, то первым добавленным словом~$x_1$ будет первая буква слова $w$. Тогда алгоритм добавляет в грамматику правило~$A_1 \to x_1$ согласно (1).
\smallskip
                                          
%Будем обозначать $S_i$ -- содержимое словаря на $i$-ом шаге. 
\noindent\underline{Шаг: от $i-1$ к $i$}. По предложению индукции, из каждого нетерминала~$A_j,\, j < i$, выводится слово $x_j$. Для слова $x_i$ возможно три случая. Первый: $x_i = a \neq x_j, \forall j < i$, здесь и далее~$ a \in \Sigma$; второй: $x_i = x_ja$ для некоторого $j < i$; третий: $x_i = x_j, j < i$ и необработанная часть слова пуста. В каждом из случаев утверждение для шага $i$ верно согласно случаям добавлений правил~(1)-(3) соответсвенно. Случай, когда слово $x_i$ не было добавлено в словарь ранее и при этом $x_i \neq x_ja$, невозможен -- алгоритм выбирает в качестве~$x_i$ кратчайший префикс необработанной части входа~$u_i$, который не входит в словарь.

После того как мы доказали, что $A_i \yields x_i$, согласно (4) получаем, что $S \yields x_1x_2\ldots x_n = w$.\qed
\medskip



\medskip

Приведённый алгоритм очевидно работает за линейное время (от длины $w$). Строку, сжатую алгоритмом~LZW легко декодировать как и строку, заданную произвольной~SLG: нужно вывести единственную строку из грамматики, при этом каждый нетерминал раскрывается единственным образом. Также для алгоритма~LZW справедливо замечание~\ref{SLPremark}.




\prp Постройте LZW-автомат и SLG~$G_w$ по описанному выше алгоритму для слова $w$:

\prsubr $w = a^8$;\quad \prsub $w = tobeornottobeortobeornot$.

\prp Постройте для слова $w = tobeornottobeortobeornot$ SLG, которая оптимальнее, чем построенная по алгоритму LZW. Численным показателем оптимальности является сумма длин правых частей всех правил SLG.


\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[из к.д.з.]
 Решите уравнения с регулярными коэффициентами. В каждом пункте нужно выполнить три задания: 

 \prsubr найти частное решение;
 
 \prsubr найти решение, минимальное по включению;
 
 \prsubr найти все решения.




\begin{align*}
	\prsub&\;\; X=((110)^*+111^*)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.\\
	Q_0&=& 0 Q_0 + 1 Q_1  +\varepsilon, \\
	Q_1&=& 1 Q_0  + 0 Q_2, \\
	Q_2&=& 0 Q_1  + 1 Q_2.\\
%	
	\end{array}
	\right.
\end{align*}

\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$ шаг.



       
\prp МП-автомат $M$, допускающий по пустому стеку, задан диаграммой:

\begin{figure}[h]            
	\begin{center}
	         \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,every node/.style={text centered},initial text=]
				\node [state,initial] (q_0)	{$q$};
				\node [state] (q_1) [right = 4cm of q_0 ] {$p$};
				\path[->]
					(q_0) edge [in=30,out=150,loop] node[sloped,align=center, above, text width=5em] { $a,Z_0/X$ $ a,X/XX$} (q_0) 
						  edge [in=330, out=210, loop] node[sloped,anchor=center,align=center,below, text width=5em]  {$b,X/XX$} (q_0)
						  edge node {$b,X/X$} (q_1)			
					(q_1) edge [in=30,out=150,loop] node[sloped,align=center, above, text width=5em] {$a,X/\eps $ $b,X/\eps $  } (q_1);
						 % edge [in=330, out=210, loop] node[sloped,anchor=center,align=center, ,below, text width=5em]  { $\eps,Z_0/\eps$} (q_1); 
			\end{tikzpicture}			
	 	\end{center} 
\end{figure}

Постройте по МП-автомату~$M$ КС-грамматику $G_M$ а по $G_M$ приведённую КС-грамматику~$G$.

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