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


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


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

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


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

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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 Задача $\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
	\bigskip
}



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

\begin{center}
	{\Large LR-анализ}
\end{center}

\bigskip

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

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


Это трёхнедельное задание, которое не требуется сдавать на проверку. На семинаре я расскажу о том как строить LL и LR таблицы в \TeX с помощью специальной программы, поэтому при желании можете отправить это задание в качестве бонусного. Основными для обсуждения в качестве бонусных будут задачи на автомат Кнута. %Задачи 4-6 обсуждаемы в качестве бонусных на зачёте.


\section{Задачи}

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




\prp Язык $L$ задан неоднозначной КС-грамматикой $$G =  \{  \{ S \} ,  \{ (, ) \} ,  \{ S  \to  (S)  \mid  SS  \mid  () \} , S \}.$$ Написать $\LL(1)-$грамматику для языка $L$.
\prend

\prp	Дана грамматика $G =  \{\;  \{ A, S \} ,\;  \{ a, b, c \} ,\;  \{\; S  \to  Aa  \mid  b  \mid   \eps ;\; A  \to  Ab  \mid  c \;\} ,\; S\; \}$. Является ли грамматика $G$ $\LR(k)-$грамматикой? При положительном ответе на вопрос найти минимальное $k$ и построить соответствующий анализатор. Построить дерево разбора для цепочки $cbba$.

\prend

\prp Дана грамматика $G = \{\;  \{ A, S \} ,\;  \{ a \} ,\;  \{\; S  \to  A;\;$\linebreak $ A  \to  aAa  \mid  a\; \} ,\; S \}$. Является ли грамматика $G$ $\LR(k)-$грамматикой? При положительном ответе на вопрос найти минимальное $k$ и построить соответствующий анализатор. Построить дерево разбора для цепочки $aaaaa$.
\prend


\prp Дана грамматика $G =  \{\;  \{ A,S \} ,\;  \{ a, b, c \} ,\;  \{ S \to Aa\mid b;\; $\linebreak $A \to Ab\mid c\; \} ,\; S\; \}$ . Является ли грамматика $G$ $\LR(k)-$грамматикой? При положительном ответе на вопрос найти минимальное $k$ и построить соответствующий анализатор. Продемонстрировать работу анализатора на цепочке $cbbab$.

\prend






\prp Зафиксируем КС-грамматику $G$ и рассмотрим множество её $\LR(0)$-ситуаций. Будем говорить, что между двумя ситуациями $\alpha.X\beta$ и $\alpha X.\beta$ определён переход по $X\in N\cup T$.
Конечный автомат, в качестве состояний которого выступают $\LR(0)$-ситуации, а переходы определены по правилу, указанному выше, называют $\LR(0)$-автоматом или автоматом Кнута.

\prsub Выпишите все $\LR(0)$-ситуации для грамматики $G$, заданной правилами $S\to aS\mid b$.  

\prsub Постройте автомат Кнута для грамматики $G$.

\prsub Постройте $\LR(0)$-анализатор для грамматики $G$. Сравните автомат Кнута с таблицей переходов $\LR(0)$-анализатора для грамматики $G$.

\prend

\prp Грамматика $G$ задана правилами  $$S\to Ab,\quad
A\to aAa,\quad
A\to B,\quad
B\to b.$$ 

\prsub Построить $\LR(1)$ и $\LR(0)$-анализаторы для грамматики $G$ по алгоритму из курса. 


\prsub Постройте $\LR(0)$-анализатор по $\LR(1)$-анализатору из пункта {\sf 1} следующим образом. Сотрите все аванцепочки и постройте управляющую таблицу $\LR(0)$-анализатора по получившемуся автомату Кнута. Верно ли, что полученный $\LR(0)$-анализатор является аналиазтором для грамматики $G$? То есть для любого слова, порождаемого $G$, анализатор строит корректный правый разбор, а слова не порождаемые $G$, анализатор отвергает.

%\prsub Верно ли, что при стирании аванцепочек в таблицах для $\LR(1)$-анализатора и (соответствующего перестроения управляющей таблицы), получается анализатор, \aul{эквивалентный}\malert{Хорошо бы дать удачное определение эквивалентности.} построенному $\LR(0)$-анализатору?

\prsub Покажите, что $\LR(0)$-анализатор для грамматики $G$ из пункта {\sf 1} можно построить путём применения следующей процедуры, схожей с процедурой минимизации ДКА, к $\LR(0)$-автомату, полученному из\linebreak $\LR(1)$-анализатора в пункте {\sf 2}. 

В случае минимизации $\LR(0)$-автомата, все состояния с операциями свёртки оказываются на первом шаге в разных группах (разных ящиках), если свёртки происходят по разным правилам; состояния с операциями сдвига находятся в одном ящике. Далее процедура минимизации $\LR(0)$-автомата не отличается от процедуры минимизации ДКА.
\prend




\subsection{Контрольные вопросы}

\prp При построении $\LR(1)-$анализатора для грамматики $G$ в одном множестве оказались ситуации $[A \to .aA\alpha,b]$ и $[B \to \beta.a,a]$, где $\alpha, \beta $ некоторые цепочки из $ (N\cup T)^*$. Может ли грамматика $G$ быть $\LR(0)$-грамматикой?



\end{document}

