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

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

\def\PAL{\mathsf{PAL}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\centerline{\LARGE Задание 7}

\medskip

\begin{center}
	{\Large Грамматики}
\end{center}

\bigskip



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

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


\section{Грамматики}

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

\begin{Def}
	Грамматика $\Gamma$ определяется через
	\begin{itemize}
		\item $N$ -- множество нетерминальных символов
		\item $T$ -- множество терминальных символов
		\item $P$ -- множество правил вывода, $P \subseteq (N\cup T)^* \times (N\cup T)^*$.
		\item $S$ -- аксиома, $S \in N$.
	\end{itemize}
	Все множества из описания грамматики конечные. При этом, $N\cap T = \es$. Принято обозначение $\Gamma = G(N, T, P, S)$.
	При описании грамматики приняты следующие соглашения. Нетерминалы обозначают заглавными буквами $A, B, C,\ldots$ терминалы обозначают строчными буквами, смешанные цепочки из $(N\cup T)^*$ обозначают греческими буквами $\alpha, \beta, \gamma$. Слово $w \in T^*$ порождается грамматикой $\Gamma$, если существует последовательность правил вывода, начинающаяся с правила вида $S \to \alpha$, в результате применения которых порождается слово $w$. Под применением правила $\alpha \to \beta$, понимается, что подслово $\alpha$ заменяется на подслово $\beta$
\end{Def}


В зависимости от ограничений, налагаемых на правила вывода, получаются разные классы языков. В рамках этого задания нас пока интересует только два последних типа.
\begin{itemize}
	\item Если на множество правил $P$ не накладывается ограничений, то есть правила имеют вид $\alpha \to \beta$, то грамматика называется грамматикой типа $0$ по Хомскому
	\item Грамматики, в которых правила имеют вид $\alpha A \beta \to \alpha \gamma \beta,\ |\gamma| > 0 $ называются грамматиками типа $1$  или Контекстно-зависимыми. В качестве исключения грамматике может принадлежать правило $S \to \eps$, но тогда нетерминал $S$ не может встречаться в правых частях. 
	\item Грамматики, в которых правила имеют вид $A \to \alpha$, называются грамматиками типа $2$ или Контекстно-Свободными грамматиками.
	\item Грамматики, в которых правила имеют вид $A \to xB $ или  $A \to x $, $x \in T^*$, называются грамматиками типа $3$ или праволинейными грамматиками.
\end{itemize}

В определении КЗ-грамматики существенно, что она является \emph{неукорачивающей}, т.е. правая часть правил всегда длинее левой. Эквивалентное определение из книги Серебрякова гласит, что в КЗ-грамматике все правила, кроме быть может $S \to \eps$, имеют вид $ \alpha \to \beta $, $|\alpha| < |\beta|$. Опять-таки, если есть правило $S \to \eps$, то нетерминал $S$ в правых частях правил встречаться не может.


Очень часто грамматиками типа $3$ называют грамматики, в которых правила вывода имеют вид $A \to xB $ или  $A \to x $, $ x \in T $, также допускается правило $S \to \eps$  с всё той же оговоркой, что аксиома не может встречаться в правой части. Такие грамматики называются \emph{праволинейными регулярными} грамматиками.

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


\begin{Def}
	Грамматика типа 3 является \emph{неоднозначной}, если существует более одного вывода хотя бы для одного слово из языка, порождённого грамматикой.
\end{Def}

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


Леволинейные грамматики определяются аналогично праволинейным: в них правила имеют вид $A \to Bx $ или $A \to x$.


Приведём пример КС-грамматики. При записи правил используют вспомогательное обозначение $A \to \alpha | \beta$, которое означает, что в грамматике есть два правила: $A \to \alpha$ и $A \to \beta$.

\begin{Example}\label{Gex}
	Грамматика $ G $ задана правилами:
	\begin{align*}
		S &\to aAB\\	
		A &\to aA | a\\
		B &\to bB | b\\
	\end{align*}
	Слово $aabb$ выводится грамматикой. Последовательность применений правил вывода такая:
	\begin{align*}
		S &\to aAB\\	&a\underline{A}B\\
		A &\to a\\	&aa\underline{B}\\
		B &\to bB\\ 	&aab\underline{B}\\
		B &\to b\\	&aabb
	\end{align*}
\end{Example}

\subsection{Вывод, левый вывод, дерево разбора}

\emph{Выводом} цепочки $\alpha$ называется такая последовательность применений правил с указанием раскрываемого нетерминала, что применяя правила из неё начиная с аксиомы получается цепочка $\alpha$. Если цепочка $\alpha$ не содержит нетерминалов, то $\alpha$ принадлежит языку, порождаемому КС-грамматикой. Нам будет удобно пользоваться такими понятиями как левый вывод и правый вывод.  \emph{Левым выводом} называют такой вывод, что на каждом его шаге раскрывается самый левый нетерминал в промежуточной цепочке. Вывод в примере \ref{Gex} является левым. Правый вывод определяется аналогично.


Также мы будем использовать деревья вывода. С формальным определением дерева вывода вы можете познакомиться, например, в книге Хопкрофта, Мотвани и Ульмана, а мы рассмотрим пример деревьев вывода и затем дадим неформальное описание этого понятия. 

\begin{Example}\label{GTree}
	Грамматика $G$, $T = \{a, +, *\}$ задана правилами:
	\begin{align*}
		S &\to E\\
		E &\to E+E\\
		E &\to E*E\\
		E &\to I\\
		I &\to a\\
	\end{align*}

	Построим деревья вывода для слова $a + a * a$:

	
	\begin{multicols}{2}
		\begin{flushleft}
			
		\begin{tikzpicture}
			\node {$S$} %root
			child{ node   {$E$} 
				child   { node {$I$}
					child{node {$a$}}
				}
			}
			child {node {$+$}}
			child{ node  {$E$}
				child { node  {$E$}
					child  { node {$I$}
						child{node {$a$}}
					}
				}
				child{ node {$*$}}
				child{ node {$E$}
					child{ node {$I$}
						child{node {$a$}}
					}
				}			
			};
		\end{tikzpicture}
				\end{flushleft}
		\begin{flushright}
			
		\begin{tikzpicture}
			\node {$S$} %root
			child{ node   {$E$} 
				child { node  {$E$}
					child  { node {$I$}
						child{node {$a$}}
					}
				}
				child{ node {$+$}}
				child{ node {$E$}
					child{ node {$I$}
						child{node {$a$}}
					}
				}
			}
			child {node {$*$}}
			child{ node  {$E$}
				child   { node {$I$}
					child{node {$a$}}
				}			
			};
		\end{tikzpicture}
				\end{flushright}	
	\end{multicols}
	
   Теперь опишем понятие дерева вывода, которое также называется деревом разбора. Зафиксируем грамматику $G$. \emph{Деревом вывода} для слова $w$  называется упорядоченное дерево, в корне которого находится аксиома $S$, каждая вершина помечена нетерминалом, терминалом или пустым словом, если вершина помечена терминалом или $\eps$, то эта вершина является листом, если же вершина помечена нетерминалом $A$, то для некоторого правила $ A \to X_1X_2\ldots X_n \in P$ ($X_i \in N\cup T$) вершины-дети $A$ помечены символами $X_1, X_2\ldots X_n$ слева направо. Листья дерева вывода образуют слово $w$.
	
	Как мы видим, синтаксически деревья вывода принципиально разные: в первом случае выражение интерпретируется как  $a + (a*a)$, а во втором как $(a+a)*a$, что приводит к непредсказуемому результату при выполнении стандартных операций!
	
\end{Example}

Эта проблема приводит нас к новому важному понятию -- неоднозначности. Грамматика $G$ является \emph{неоднозначной}, если хотя бы для одного слова существует два различных дерева вывода.




Левый и правый вывод помимо удобства важны тем, что они фактически задают порядок обхода дерева вывода, поэтому каждому левому выводу соответствует ровно одно дерево разбора, а каждому дереву забора соответствует ровно один левый вывод.

\upr Доказать, что грамматика $G$ является однозначной тогда и только тогда, когда каждое слово, порождаемое $G$ имеет ровно один левый(правый) вывод.





\section{Задачи}

Внимание, все задачи на построение автоматов должны быть снабжены диаграммами! 

\prp
\begin{multicols}{2}
	
Предложите алгоритм построения праволинейной грамматики по автомату $\A$ и докажите его корректность. Постройте по автомату $\A$ регулярную праволинейную грамматику $G$ по предложенному алгоритму. Если вместо построения своего алгоритма, Вы возьмёте его из книжки, укажите это и не списывайте страницами, пожалуйста.
\vfill
 \columnbreak 
	
\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	\node[state, initial]	(q_0)							{$q_0$};
	\node[state] 		  	(q_1) [above right = of q_0]	{$q_1$};
	\node[state, accepting] 	(q_2) [right = of q_1]			{$q_2$};
	\node[state]			(q_3) [right = 2.5cm of q_0]			{$q_3$};
	\node[state, accepting]	(q_4) [below right = of q_0]	{$q_4$};
	\path[->]
		(q_0)	edge	node {$\eps$}	(q_1)			
				edge	node {$a$} 		(q_3)
		(q_1)	edge	node {$a$}		(q_2)
				edge	node {$b$}		(q_3)
		(q_2)	edge	node {$a$}		(q_3)
		(q_3)	edge	node {$b$}		(q_4)
		(q_4)	edge [bend left]	node {$a$} 		(q_0)
				edge [anchor=-5, pos=0.3]				node {$\eps$}	(q_0);
\end{tikzpicture}


\end{multicols}


\prp Постройте автомат по грамматике $G:$ $$ S\to abaA \mid abB \mid \eps,\ A\to aB\mid aa,\ B\to bA \mid aS$$
%\prsub Предложите алгоритм построения НКА по праволинейной грамматике.

%\prsub
%\prsub Постройте регулярное выражение для языка $L(G)$.

\prp Является ли грамматика $G$ из предыдущей задачи однозначной?

\prend

\prp  Язык $L$ задан КСГ: 
$S \to aSa\mid aSb\mid bSa\mid bSb\mid a$.
 
 \prsub Является ли $L$ регулярным языком?
 
 \prsub Является ли дополнение $L$ регулярным языком?


\prend

\prp Построить для следующих языков, заданных над алфавитом $\{a, b\}$, КС-грамматики:

\prsubr $\PAL=\{ w \mid w=w^R\}$;\quad  \prsubrinline $L = \{\, a^nb^m \mid n \leq m \leq 2n \,\}$;

\prsubr $\Sigma^*\setminus \{ a^nb^n \mid n \geq 0 \}$.



\begin{comment}
	\prp Верно ли, что праволинейная грамматика $G$ однозначна тогда и только тогда, когда построенный по ней автомат является детерминированным?

	\prp Назовём грамматику линейной, если в правой части её правил может быть не более одного нетерминала. Верно ли, что для любой линейной грамматики $G$, $L(G) \in \REG$?

	\bigskip

	Ещё раз напоминаю, что задачи, помеченные $\dagger$ являются дополнительными, поэтому списывать их из книжек -- бессмысленное увеличение энтропии.

	\begin{Def}
		Для языка $L \subseteq \{\sigma_1,\sigma_2,\ldots,\sigma_n\}^* = \Sigma_n^*$ и языков $L_{\sigma_1}, L_{\sigma_2}, \ldots, L_{\sigma_n} \subseteq \Sigma_n^* $, подстановкой  в $L$ языков $L_{\sigma_1},\ldots, L_{\sigma_n}$ назовём язык $L^{\prime} $, такой что для всех слов $w = w[1]\ldots w[n]$ из языка $L$ справедливо $ L_{w[1]}L_{w[2]}\ldots L_{w[n]} \subseteq L^{\prime}$
	\end{Def}

	\prdag Доказать, что регулярные языки замкнуты относительно операции подстановки.

	\begin{Def}
		Даны алфавиты $\Sigma$ и $\Delta$. Для языка $L \subseteq \Sigma\times \Delta$ определены операции проекции на $\Sigma^*$ и $\Delta^*$. Проекцией $L$ на $\Sigma^*$ называется язык $L_\Sigma = \{ w \in \Sigma^*\, |\, \exists v \in \Delta^* : (w,v) \in L \}$. Проекция $L$ на $\Delta^*$ определяется аналогичным образом.
	\end{Def}

	\prdag Доказать, что регулярные языки замкнуты относительно операции проекции.

	\begin{Def}
		Для языка $L_\Sigma \subseteq \Sigma^*$, $\Delta$-целиндром называется язык $L$, такой что $L = \{w\, |\, w = (u, v), u \in L_\Sigma, v \in \Delta^* \}$
	\end{Def}

	\prdag Показать, что $\Sigma$-проекция $\Delta$-цилиндра $L$ есть $L$. Доказать, что регулярные языки замкнуты относительно операции цилиндра.

	\prp На семинаре я «доказал», что грамматика $G: S \to aSb\,|\, SS \,|\, \eps $ порождает язык правильных скобочных выражений с одним типом скобок -- язык Дика $D_1$. На самом деле, я дал доказательство только в одну сторону: что любое слово, выведенное из этой грамматики будет правильным скобочным выражением. После чего порадовавшись, что меня никто за руку не поймал, в назидание оставляю доказательство в другую сторону в качестве домашней задачи. Напомню, что мы договорились считать, что слово $w$ является правильным скобочным выражением, если его скобочный итог $d(w)$ равен нулю, и при этом скобочный итог любого префикса $w$ неотрицательный. Скобочным итогом называется разница между числом открывающих и закрывающих скобок: $d(u) = |u|_a - |u|_b$.

	\prp Является ли грамматика $G$ для языка $D_1$ из предыдущей задачи однозначной?
	
\end{comment}



\end{document}