\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,trees}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{enumitem}


\usepackage{textcomp}
\usepackage{listings}
\lstset{tabsize=2,showstringspaces=false,literate={-}{-}0,columns=flexible,keepspaces=true}



%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\theoremstyle{definition}
\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}}}
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\def\LL{{\mathrm{LL}}}
\def\LR{{\mathrm{LR}}}


\def\attr{\mathsf{attr}}
\def\val{\mathsf{val}}
\def\ord{\mathsf{ord}}

\def\firstpos{\mathsf{firstpos}}
\def\lastpos{\mathsf{lastpos}}
\def\nullable{\mathsf{nullable}}
\def\followpos{\mathsf{followpos}}

\def\RExpr{\mathsf{RExpr}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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}
\renewcommand{\thesubrproblem}{\asbuk{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,footnote,#1,print}\ifthenelse{\equal{#2}{}}{}{#2 }% 
}
\pgfkeys{
 /prtemplate/.is family, /prtemplate,
 name/.default = {},
 name/.store in = \prname,
 label/.default = {},
 label/.store in = \prlabel,
 footnote/.default = {},
 footnote/.store in = \prfootnote, 
 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]\ifthenelse{\equal{\prfootnote}{}}{}{\footnote{\prfootnote}}.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}}


%%%\ifthenelse{\equal{\prfootnote}{}}{}{\footnote{\prfootnote}}.
%%%\ifthenelse{\equal{\prtype}{star} \OR \equal{\prtype}{circ}}{\!}{} %Уменьшить отступ до точки после * и \circ

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



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

\newcommand{\prwrite}[1][]{\ifthenelse{\equal{#1}{star}}{$\mathbf{\arabic{\prcounter}}^{*}$}{\ifthenelse{\equal{#1}{circ}}{$\mathbf{\arabic{\prcounter}}^{\circ}$}{\textbf{\arabic{\prcounter}}}}}
%\newcommand{\prwrite}[1][]{\ifthenelse{\equal{#1}{star}}{$\mathbf{\arabic{\prcounter}}^{*}$.}{\ifthenelse{\equal{#1}{circ}}{$\mathbf{\arabic{\prcounter}}^{\circ}$}{\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]{}}
\newcommand\prsubrstar[1][]{\prsubrtemplate[#1,type=star]{}}
\newcommand\prsubrstarinline[1][]{\prsubrtemplate[#1,type=star,display=inline]{}}
%\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\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\prsubtemplate[2][]{%
 \pgfkeys{/prsubtemplate,label,display,type,#1,print}\ifthenelse{\equal{#2}{}}{}{#2 }% 
}
\pgfkeys{
 /prsubtemplate/.is family, /prsubtemplate,
 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{subproblem}}{\refstepcounter{subproblem}\label{\prlabel}}\setcounter{subrproblem}{0}{\sf \prsubwrite[\prstype]\;}}
}
\newcommand{\prsubwrite}[1][]{\ifthenelse{\equal{#1}{star}}{{$\mathsf{\thesubproblem}^*.$}}
	{\ifthenelse{\equal{#1}{o}}{{$\mathsf{\thesubproblem}^{\circ}.$}}
		{\thesubproblem.}}}

\newcommand\prsub[1][]{\prsubtemplate[#1]{}}
\newcommand\prsubu[1][]{\prsubtemplate[#1,type=o]{}}
\newcommand\prsubinline[1][]{\prsubtemplate[#1,display=inline]{}}
\newcommand\prsubuinline[1][]{\prsubtemplate[#1,type=o,display=inline]{}}
\newcommand\prsubstar[1][]{\prsubtemplate[#1,type=star]{}}
\newcommand\prsubstarinline[1][]{\prsubtemplate[#1,type=star,display=inline]{}}

%\def\prsub{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{\sf \thesubproblem.}\;}
%\def\prsubstar{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{$\mathsf{\thesubproblem}^*$\negthickspace.}\;}


%\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}
\newenvironment{problem}[1][]{\prtemplate[name={Задача}, counter={problem}, #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} }


\newcommand\prp[1][]{\prtemplate[#1,name={Задача}]{}}
%\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 .*   }



\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{
	\medskip
%	\bigskip
}


\def\prskip{
	\smallskip
}


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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Отображение решений %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newif\ifsolshow
%\solshowfalse
\solshowtrue

\newif\ifstudver
%\studverfalse
\studvertrue


\usepackage{comment}
\ifsolshow
	\newenvironment{sol}[1][Решение.]{	
	\setcounter{prvar}{0}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\noindent\textbf{#1} %\ifthenelse{\equal{#1}{}}{\textbf{Решение.}}{\textbf{#1}}			
		}
		{		
			\qed
			\bigskip
		}
\else
	\excludecomment{sol}
\fi


\ifstudver
	\excludecomment{studhidebox}
\else
	\newenvironment{studhidebox}[1][]{	
	#1 %\ifthenelse{\equal{#1}{}}{\textbf{Решение.}}{\textbf{#1}}			
		}
		{		
		
		}
	
\fi



\newenvironment{quizsol}[1][]{\begin{sol}[К.В.~\ref{#1}.]}	{\end{sol}}

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

\newcommand{\ukaz}[1]{\noindent\textbf{Указание:} \textsl{#1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EoF Отображение решений %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

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

\begin{center}
	{\Large Атрибутные грамматики}
\end{center}

\bigskip

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

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

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

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

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

\pagebreak

\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{Атрибутные грамматики}

Следующий за синтаксическим анализом этап в процессе компиляции является генерация кода. В основе этого этапа лежат вычисления по дереву разбора, которые описывают с помощью атрибутных грамматик. Мы не будем детально изучать эту тему, а изучим лишь частный случай атрибутных грамматик (с синтезируемыми атрибутами).

\begin{Def}
КС-грамматика $G$ называется \emph{атрибутной с ситнезируемыми атрибутами}, если каждому нетерминалу поставлен в соответствие набор переменных (атрибутов), и при этом для каждого правила грамматики
	$$X_0 \to u_0X_1u_1X_2\ldots u_{n-1}X_nu_n,\; X_i \in N,\; u_i \in \Sigma^* $$
Задан набор правил вычисления некоторых атрибутов
	$$X_0[\attr] = f(\xi_1,\xi_2,\ldots,\xi_m),$$
где $\xi_i = X_k[\attr_j]$ -- значение атрибута $\attr_j$ для нетерминала $X_k$ , а $f$ -- некоторая функция. Набор правил вычислений атрибутов называют \emph{атрибутной схемой}.
\end{Def}

\begin{remark}
	В каждом правиле нетерминалы занумерованы; это нужно для корректного определения атрибутной схемы, если в правило входит несколько одинаковых нетерминалов. В случае, когда в правиле нетерминалы не повторяются, мы опускаем нумерацию для простоты обозначений.
\end{remark}

\begin{Example}
	Грамматика $G$ задана правилами $$S \to 1D \mid 0 \mid 1,\, D \to 1D\mid 0D\mid 1 \mid 0  $$ и порождает язык двоичных записей натуральных чисел. Определим атрибутную схему для этой грамматики
\begin{align*}                                                                                
	 &S \to 0		&	&S \to 1		& &S \to 1D						&	&D \to 1  	 	 &	 	&D \to 0  		\\
	 &S[\val] = 0 	&	&S[\val] = 1	& &S[\val] =  D[\ord] + D[\val]	&	&D[\val] = 1 	 &		&D[\val] = 0	\\ 	
	 &				&	&				& &                             &  	&D[\ord] = 2   	 &    	&D[\ord] = 2    
	\end{align*}                                            

	\begin{align*}                                                                                
	&D \to 0  	 &		&D_0 \to 1D_1  	 								   	&	 	&D_0 \to 0D_1  	 									&	\\	
	&D[\val] = 0 &		&D_0[\val] = D_1[\ord] + D_1[\val]  &		&D_0[\val] = D_1[\val]      			&	\\  
	&D[\ord] = 2 &	  	&D_0[\ord] = 2\times D_1[\ord] 			&  	&D_0[\ord] = 2\times D_1[\ord]		& 	
\end{align*}	                                                                             

\bigskip

%\pagebreak   
		
В случае, если правило содержит несколько одинаковых нетерминалов мы нумеруем их вхождение и различаем атрибуты как в случае двух последних правил.
Нетерминал $S$ имеет единственный атрибут $\val$, а нетерминал $D$ -- атрибуты $\val$ и $\ord$. Приведённая атрибутная схема вычисляет значение числа по его двоичной записи.
Атрибут $\ord$ равен $2^l$, где $l$ -- длина слова выведенного из $D$, атрибут $\val$ равен значению числа, двоичная запись которого выведена из нетерминала.

Приведём на рис.~\ref{Fig:ExAttrComputation} пример вычисления атрибутов для слова $1101$. Атрибуты вычисляются снизу вверх.

%\bigskip

\begin{figure}[h]
	
\begin{center}
	\begin{tikzpicture}
		\node (S) {$S$} %root
			child{
				node {$1$}
			}
			child{
				node (D1) {$D$}
				child{
					node {$1$}
				}
				child{
					node (D2) {$D$}
					child{
						node {$0$}
					}
					child{
						node (D3) {$D$}
						child{
							node {$1$}
						}					
					}
				}
			};
			\node (S[val]) 	[right = 0.5cm of S] {$S[\val] = 13$};
			\node (D1[val]) [right = 0.5cm of D1] {$D[\val] = 5$; $D[\ord] = 8$};
			\node (D2[val]) [right = 0.5cm of D2] {$D[\val] = 1$; $D[\ord] = 4$};
			\node (D3[val]) [right = 0.5cm of D3] {$D[\val] = 1$; $D[\ord] = 2$};
	\end{tikzpicture}
\end{center}
	\caption{вычисление атрибутов.}\label{Fig:ExAttrComputation}
\end{figure}
\end{Example}

\begin{comment}
	


\prp Грамматика $\RExpr = \langle \{E,T\}, \{a, b, +, {}^*, (, ) \}, P, E \rangle$ имеет множество правил $P:$  
$$ E \to  T+E \mid TE \mid T \qquad T \to (E) \mid T^* \mid a \mid b $$ 
и порождает регулярные выражения над алфавитом $\{a,b\}$.

%E -> T+E | TE |  T  
%T -> (E) |  T* | a | b




\prsub Постройте для грамматики $\RExpr$ $\LR(1)$-анализатор\footnote{Анализатор для этой грамматики довольно громоздкий. Постройте его с помощью программы, например на сайте \url{http://lrk.umeta.ru}, используйте программу для выполнения последующих пунктов.}.

\prsub Дополните грамматику $\RExpr$ до атрибутной так, чтобы она вычисляла атрибуты $\firstpos, \lastpos$ и $\nullable$ согласно алгоритму их вычисления при построении ДКА по РВ. Считайте атрибуты $\firstpos$, $\lastpos$ и $\nullable$ у терминалов заданными: на практике перед вычислением атрибутов происходит препроцессинг, во время которого могут быть заданы атрибуты терминалов, если это требуется.

\smallskip
\noindent\underline{{Указание}}. Вычисление атрибута нужно определять через функцию, которую можно описать на языке программирования или псевдокоде. Пример вычисления атрибута $\nullable$ для правила $E_0 \to T+E_1$:
%$$  \quad  =  $$

\medskip
\noindent$E_0[\nullable] = $ \textbf{function}( $T[\nullable]$, $E_1[\nullable]$)\{\\
\xquad	\textbf{if}( $T[\nullable]$ \textbf{or} $E_1[\nullable]$)\{\\
\xquad\quad		\textbf{return} \textsf{True};\\
\xquad	\}\,\textbf{else}\{ \textbf{return} \textsf{False}; \} \\
\}

\prsubstar Добавьте в атрибутную схему вычисление атрибута $\followpos$.

\prsub С помощью анализатора постройте дерево разбора для РВ~$(a+ab)^*+ab^*$ и вычислите атрибуты $\firstpos, \lastpos$, $\nullable$ (*$\followpos$) согласно атрибутной схеме (предварительно задав атрибуты у терминалов).

\prend

\end{comment}
Больше примеров можно найти в книге Серебрякова. Обратите внимание, что в ней приедено более общее определение атрибутных грамматик; определение атрибутных грамматик в этом задании эквивалентно определению синтезируемых атрибутных грамматик из книги Серебрякова, хотя там оно и имеет другой вид. Особенно рекомендую ознакомиться с примером 5.4 (главы 5): в нём иллюстрируется как с помощью атрибутных грамматик реализовать алгоритм символического вычисления производной от функции.

\subsection{Атрибутные грамматики и HTML}

Язык разметки web-страниц HTML был разработан так, что бы его код было легко разбирать интерпретатором. Код на HTML представляет собой правильное скобочное выражение, в котором скобки имеют имена и называются тегами: <tag> ... </tag>.
Внутри открывающей скобки <tag> могут быть атрибуты; в общем случае (открывающий) тег имеет вид <name attr1=\textquotedbl value\textquotedbl\, attr2=\textquotedbl value\textquotedbl\,  ... attrN=\textquotedbl\, value\textquotedbl>, т.\,е. сначала идёт имя тега, а потом перечисляются атрбиуты.

При интерпретации HTML-кода правильная скобочная последовательность тегов интерпретируется как дерево: если один тег вложен в другой, то внешний тег~"--- родитель внутреннего. Так, в случае кода 

\medskip

\centerline{<tag1> ... <t2>....</t2> <t3>....</t3>...</tag1>}

\medskip

\noindent тег~tag1 является родителем тегов t2 и t3.

Рассмотрим тег <div>, который является контейнером для разделения содержимого страницы. Будем рассматривать два атрибута: align и style. В случае вложенных тегов, атрибут align либо задан, например <div align=\textquotedbl center\textquotedbl>, либо наследуется от родителя. Атрибут style позволяет задавать (CSS) стиль элемента и устроен более сложно, чем align. Мы сосредоточимся только на задании с помощью атрибута style цвета фона у контейнера <div>. В случае вложенных <div>, если цвет фона не задан, то он наследуется у родителей.



\section{Задачи}

\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 Написать для грамматики  эквивалентную $\LL(1)$-грамматику, построить $\LL(1)$-анализатор и продемонстрировать его работу на слове $baab$. 
$$ S \to baaA\mid babA\qquad A\to \eps\mid Aa\mid Ab.$$



\prp Дополните грамматику $S\to 0S11,\; S\to 1S00,\; S\to \eps$ до атрибутной так, чтобы вычислялась максимальная длина непрерывной последовательности из единиц в порождаемом слове.

\prend



\prp[label={pr:Divs}] Постройте по коду на рис.~\ref{fig:prDivs} дерево html документа. Определите значение атрибута align у каждого из узлов div дерева, а также определите цвет фона элемента (атрибут background-color). Проверьте себя, сохранив текст ниже в файле с расширением .html и открыв файл в браузере.

\begin{figure}	
\begin{lstlisting}[language=HTML]
	<html>
	<head> 
	  <style>
	   div{border: 1px solid black; padding:1px;
	   	   margin: 1px; width:40%; height:40%;}
	  </style>
	</head>
	<body>
	<div style="background-color:lightblue; width:500px;
				height:500px;" align="center">1
		<div style="background-color:blue;" align="left">
			2
			<div align="right">
				3
				<div style="background-color:gray;" align="center">
					4
				</div>
			</div>
			<div>
				5
			</div>				
		</div>	
		<div>
			6
		</div>
	</div>
	</body>
	</html>	
\end{lstlisting}
\caption{HTML-код для задачи~\ref{pr:Divs}}\label{fig:prDivs}
\end{figure}

\bigskip

\noindent\textbf{Комментарий.} В HTML-документе код документа окружается тегом <html>, внутри тега <head> находятся вспомогательные данные (такие как заголовки), а содержимое документа находится в теге <body>. Внутри тега <style> описывается стиль элементов документа, в нашем коде там указан базовый стиль для тегов <div>: наличие границы, отступы и размер в процентах относительно размера тега-родителя. Браузер интерпретирует документ HTML как дерево, точнее модель документа называется DOM (Document Object Model).


\end{document}