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

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\emptyset
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

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

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


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

\def\quotient{\backslash\negthickspace\sim}

\begin{document}

	\centerline{\LARGE Задание 2}

	\medskip

	\centerline{\Large НКА и алгоритмы поиска подстрок}

	\bigskip

	{\bf Литература: }
	\begin{enumerate}
		\item {\em Хопкрофт Д., Мотвани Р., Ульман Д.}\\ Введение в теорию автоматов, языков и вычислений.\\ М.: Вильямс, 2002.

	\item {\it Ахо А., Ульман Д.}\\ Теория синтаксического анализа, перевода и компиляции\\  М.: Мир, 1978. Гл. 0, 2.

	\item {\em Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.}\\ Теория и реализация языков программирования.\\ М.: МЗ-пресс, 2006.
	
	\item {\em Шень. А. Х. }\\ Программирование: теоремы и задачи \\ М.: МЦНМО, 2004.

	\item {\em Журавлёв Ю.И., Флёров Ю.А, Вялый М.Н.}\\ Дискретный Анализ. Формальные системы и алгоритмы. \\ М.: МЗ-пресс, 2010.

	\end{enumerate}

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

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

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



\section{Построение по регулярному выражению конечного автомата }
	
	На семинаре мы разобрали алгоритм построения детерминированного конечного автомата по регулярному выражению. Однако, его нельзя назвать простым. Построить недетерминированный автомат по регулярному выражению гораздо проще. В каком-то смысле, если вы имеете дело с регулярным выражением, вы имеете дело с НКА. 
	
	Напомним, что помимо обычных переходов недетерминированные автоматы, имеют также $\eps$-переходы, т.е. переходы вида $\delta(q_i, \eps) = q_j$. Наличие таких переходов означает, что попав в состояние $q_i$, автомат может перейти в состояние $q_j$ не обрабатывая следующий символ слова.
\begin{Example}
\quad\\
\begin{center}
	
 	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	  %\draw[help lines] (0,0) grid (3,2);
	  \node[state,initial]  (q_0)                      {$q_0$};
	  \node[state, accepting]          (q_1) [ right = of q_0] {$q_1$};
	 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
	  \path[->] 
		(q_0)	edge	[loop below]	node	{0}	()
				edge	[bend left] 	node	{1}	(q_1)
	 	(q_1)	edge	[bend left]		node	{$\eps$} (q_0);
	\end{tikzpicture}
\end{center}



	Легко видеть, что данный автомат принимает язык, состоящий из слов, оканчивающихся на $1$. При прочтении $1$, автомат переходит из состояния $q_0$ в $q_1$, дальше, если во входном слове ещё остались необработанные символы, автомат делает $\eps$-переход из состояния $q_1$ в $q_0$ и продолжает обработку слова.\
	
	

\end{Example}	

	Для построения НКА по РВ будем использовать определение регулярного языка.  Напомним определение класса регулярных языков $\REG$. 

	\begin{itemize}
		\item $\varnothing \in \REG$.
		\item $\forall \sigma \in \Sigma:\ \{ \sigma \} \in \REG $.
		\item $\forall X, Y \in \REG\ :\ X\cdot Y,\ X|Y,\ X^* \in \REG   $.
		\item Больше нет регулярных языков.
	\end{itemize}

	Мы будем строить НКА по РВ из каждого пункта данного определения. С первыми двумя пунктами проблем нет -- их я оставляю как лёгкое упражнение. Перейдём сразу к третьему пункту. Допустим уже построены автоматы $\A$ и $\B$ для регулярных языков $X$ и $Y$ соответственно.
	Мы будем предполагать, что оба автомата имеют всего одно принимающее состояние. Если в автомате несколько принимающих состояний, то можно построить эквивалентный ему автомат с единственным принимающим состоянием, добавив к множеству состояний состояние $q_F$, которое будет единственным принимающим, и добавив $\eps$-переходы в $q_F$ из старого множества $F$: $\forall q \in F: \delta(q, \eps) = q_F$. Будем схематично обозначать автоматы эллипсами, и помечать в них только начальное и принимающее состояние. Таким образом, автомат $\A$ имеет вид
	\begin{center}


	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	  %\draw[help lines] (0,0) grid (3,2);
	  \draw (1,0) ellipse (16mm and 10mm);
	  \node at (1,0) {$\A$};
	  \node[state,initial]  (q_0)                      {$q_0$};
	  \node[state, accepting]          (q_1) [ right = of q_0] {$q_F$};
	 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
	 \end{tikzpicture} 
	\end{center}


	В дальнейшем, мы будем предполагать, что начальное состояние на схеме находится слева, а принимающее справа.
	Построим явно автомат распознающий $X\cdot Y$, $L(\A) = X, L(\B) = Y$.


	\begin{center}



	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	  %\draw[help lines] (0,0) grid (3,2);
	  \draw (1,0) ellipse (16mm and 10mm);
	  \draw (3,0) ellipse (16mm and 10mm);
	  \node at (1,0) {$\A$};
	  \node at (3,0) {$\B$};
	  \node[state,initial]  (q_0)                      {$q^\A_0$};
	  \node[state]          (q_1) [ right = of q_0] {};
	  \node[state, accepting]          (q_2) [ right = of q_1] {$q^\B_F$};
	 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
	 \end{tikzpicture}
	\end{center}
	Для этого по автомату $\A$ распознающему язык $X$ и автомату $\B$, распознающему язык $Y$ мы строим автомат, распознающий $X\cdot Y$ объединяя множеcтва состояний $\A$ и $\B$ так, что $q_0 = q^\A_0$, $q^\A_F = q^\B_0$, $F = \{q^B_F\}$. Опять получили автомат с единственным принимающим состоянием.

	\upr Доказать, что построенный автомат распознаёт язык $X\cdot Y$.
	\medskip

	Для построения языка $X|Y$ используем следующую конструкцию:
	\begin{center}


	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	  %\draw[help lines] (0,0) grid (3,2);
	  \draw (2.4,1.4) ellipse (16mm and 10mm);
	  \draw (2.4,-1.4) ellipse (16mm and 10mm);
	  \node at (2.4,1.4) {$\A$};
	  \node at (2.4,-1.4) {$\B$}; 
	  \node[state ,initial] (q_e) 					 {$q_0$};
	  \node[state]		    (q_0) [ above right = of q_e ] {$q^\A_0$};
	  \node[state]          (q_1) [ right = of q_0] {$q^\A_F$};
	  \node[state]          (q_2) [ below right = of q_e  ] {$q^\B_0$};
	  \node[state]          (q_3) [ right = of q_2] {$q^\B_F$};
	  \node[state, accepting]          (q_f) [ below right = of q_1  ] {$q_F$};
	  \path[->] 
			(q_e)	edge		node	{$\eps$}	(q_0)
					edge		node	{$\eps$}	(q_2)
			(q_1)
					edge		node	{$\eps$}	(q_f)
			(q_3)
					edge		node	{$\eps$}	(q_f);
	 \end{tikzpicture}
	\end{center}

	\upr Доказать, что построенный автомат распознаёт язык $X| Y$.
	\medskip

	И наконец перейдём к построению автомата для языка $X^*$:
	\bigskip

	\begin{center}



	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	  %\draw[help lines] (0,0) grid (3,2);
	  \draw (3,0) ellipse (16mm and 9mm);
	  \node at (3,-0.5) {$\A$};
	  \node[state ,initial] (q_e) 					 {$q_0$};
	  \node[state]		    (q_0) [ right = of q_e ] {$q^\A_0$};
	  \node[state]          (q_1) [ right = of q_0] {$q^\A_F$};
	  \node[state, accepting]          (q_f) [ right = of q_1  ] {$q_F$};
	  \path[->] 
			(q_e)	edge		node	{$\eps$}	(q_0)
					edge [bend left] node {$\eps$}	(q_f)
			(q_1)
					edge		node	{$\eps$}	(q_f)
					edge [bend right] node {$\eps$}	(q_0);
	 \end{tikzpicture}
	\end{center}


	\upr Доказать, что построенный автомат распознаёт язык $X^*$.
	\medskip
	
	\prp Постройте НКА по регулярному выражению $(a(a|b))^*b$.
	\medskip
		
%	\prp Постройте по НКА, полученному в предыдущей задаче, ДКА.

\section{Распознавание текстов}	
	
С помощью НКА можно легко описать язык, в который входят все слова, содержащие в качестве подслова некоторое слово. Например, следующий автомат распознаёт
слова, содержащие подслово $ababa$.

\begin{center}
 	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
	  %\draw[help lines] (0,0) grid (3,2);
	  	\node[state,initial]		 	(q_0)                   {$q_0$};
	  	\node [state] 					(q_1) [right = of q_0]	{$q_1$};
	  	\node [state] 					(q_2) [right = of q_1]	{$q_2$};		
		\node [state] 					(q_3) [right = of q_2]	{$q_3$};
		\node [state] 					(q_4) [right = of q_3]	{$q_4$};
		\node [state, accepting] 		(q_5) [right = of q_4]	{$q_5$};
	 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
	  \path[->] 
		(q_0)	edge	[loop]	node	{$a,b$}	()
				edge	 	node	{$a$}	(q_1)
	 	(q_1)	edge		node	{$b$} (q_2)
		(q_2)	edge		node    {$a $} (q_3)
		(q_3)	edge		node    {$b $} (q_4)
		(q_4)	edge		node    {$a $} (q_5)
		(q_5)   edge [loop]	node	{$a,b$} ();
	\end{tikzpicture}
\end{center}

% \prp Постройте по НКА, полученному в предыдущей задаче, ДКА.

\prpstar Докажите, что по НКА данного вида ($\Sigma^*w\Sigma^*$) можно построить ДКА, число состояний которого не превосходит $|w|+1$.

\prp Постройте НКА, распознающий слова, в которых есть хотя бы одно из подслов $abba, abab, baa$.

%\prpstar Постройте по НКА из предыдущей задачи ДКА. Что можно сказать об оценке числа состояний для ДКА?

\section{Детерминированный конечный автомат}

В этом разделе представлены задачи на построение автоматов и изучение свойств ДКА. В случае, когда речь идёт об автомате $\A$, для сокращения записи мы будем подразумевать, 
что данный автомат задан набором 

$$ \A = (Q_\A,\; \Sigma,\; q^{\A}_0,\; \delta_\A,\; F_\A).  $$


\prp Постройте ДКА, который

\prsubr распознаёт язык, все слова которого содержат чётное число нулей;

\prsubr распознаёт язык, все слова которого содержат нечётное число единиц;

\prsubr распознаёт язык, все слова которого содержат чётное число нулей и нечётное число единиц.

\prend

%Мы изучили алгоритм построение НКА для объединения регулярных языков, заданных НКА. Однако существует и алгоритм построения ДКА для объединения двух языков, заданных ДКА.

Из определения регулярных языков следует, что они замкнуты относительно операции объединения. Следующий алгоритм показывает, что регулярные языки замкнуты относительно пересечения. Пусть заданы ДКА $\A$ и $\B$. Построим ДКА $\C$, распознающий язык $L(\A) \cap L(\B) $, следующим образом:

\medskip

\begin{itemize}
	\item $Q_\C = Q_\A \times Q_\B$;
	\item $q_0^{\C} = (q_0^{\A},q_0^{\B})$;
	\item $\forall \sigma \in \Sigma : \delta_\C((q_\A,q_\B), \sigma) = (\delta_\A(q_\A, \sigma), \delta_\B(q_\B, \sigma ) )$;
	\item $F_\C = F_\A \times F_\B$
\end{itemize}

\medskip

Конструкции такого типа -- в которых состояния итогового объекта являются парами исходных, а функция переходов согласована с исходными объектами, --  называются \emph{конструкциями произведения}. 

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

\prp Заменим в конструкции произведения для пересечения регулярных языков последний пункт на
\begin{itemize}
	\item  $F_\C = F_\A\times Q_\B \cup Q_\A \times F_\B $.
\end{itemize}
Верно ли, что тогда автомат $\C$ распознаёт объединение языков $L(\A) \cup L(\B)$?


\prp Постройте автомат из задачи {\bf4(3)} используя автоматы, построенные в первых двух пунктах и конструкцию произведения.

	
\section{О построении ДКА по РВ}





На семинаре мы изучили алгоритм построения ДКА по РВ. На первом этапе мы строили дерево и вычисляли значения атрибутов \emph{firstpos}, \emph{lastpos} и \emph{nullable}. Принцип вычисления этих атрибутов состоит в том, что имея значение атрибутов в дочерних узлах, мы можем вычислить атрибуты самого узла. Например для узла\smallskip

\begin{center}
	


\begin{tikzpicture}[level 1/.style={sibling distance=2.5cm}]
	\node {$\bullet$ }
		child{
			node  {$f_\alpha\  \alpha^T\  l_\alpha$}
		}
		child{
			node {$f_\beta\  \beta^F\  l_\beta$}
		};			
	
\end{tikzpicture}
\end{center}	
атрибуты узла $\bullet$ будут 
\smallskip
\begin{center}
	

\begin{tikzpicture}[level 1/.style={sibling distance=2.5cm}]
	\node { $\mkern-26mu f_\alpha \cup f_\beta\  \bullet^F\  l_\beta$ }
		child{
			node  {$f_\alpha\  \alpha^T\  l_\alpha$}
		}
		child{
			node {$f_\beta\  \beta^F\  l_\beta$}
		};			
\end{tikzpicture}
	\end{center}
потому что регулярное выражение $\alpha\cdot\beta$ порождает слово $w = uv$, такое что РВ $\alpha$ порождает $u$, РВ $\beta$ порождает $v$, при этом слово $u$ может быть пустым, а слово $v$ -- нет. Отсюда, если $u \neq \eps$, то $w$ начинается с тех же символов, что и $u$, а значит $f_\alpha \subseteq f_\bullet$, а если $u = \eps$, то $w$ начинается с тех же символов, что и слово $v$, поэтому $f_\beta \subseteq f_\bullet$, отсюда $f_\bullet  = f_\alpha \cup f_\beta$. Поскольку слово $w$ имеет непустой суффикс $v$, порождённый $f_\beta$, то $l_\bullet = l_\beta$.

\upr Найти алгоритм вычисления атрибутов во всех остальных случаев для узлов с операциями $\bullet$ и $|$. Если не получается придумать алгоритм, его можно найти в книге Серебрякова. Доказать корректность вычисления атрибутов.

\prpstar Мы рассматривали алгоритм построения ДКА по РВ, в котором не встречается пустое слово. В случае когда оно встречается, исходное РВ $R$ может быть преобразовано либо в выражение $R^\prime$, либо в выражение $R^\prime\, |\,\eps$,
где в выражение $R^\prime$ пустое слово уже не входит. Предложите алгоритм, который осуществляет такое преобразование.

\prpstar Мы рассматривали алгоритм построения ДКА по РВ, в котором не встречается пустое множество. В случае когда оно встречается, исходное РВ $R$ может быть преобразовано либо в выражение $R^\prime$, либо в выражение $R^\prime\, |\, \eps$, причём пустое множество и постое слово в выражение $R^\prime$  не входят. Предложите алгоритм, который осуществляет такое преобразование.

\textbf{Указание:} Введите новый атрибут в дерево.

\newpage



\end{document}
