 \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\ins{\mathbf{in}}
\def\out{\mathbf{out}}
\def\test{\mathbf{test}}


%прочее
\def\quotient{\backslash\negthickspace\sim}
\begin{document}
	\centerline{\LARGE Задание 3}

	\medskip

%	\centerline{\Large НКА и ДКА;\\ Лемма о накачке;\\ Автоматы и распознавание текстов. }

\begin{center}
	{\Large НКА и ДКА
	
		Алгоритмы обработки текстов I 
		
		%\vspace{0.5ex}
		
		%Автоматы и распознавание текстов
		}
\end{center}

	\bigskip

	


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

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

	Из алгоритма детерминизации НКА следует, что если НКА $\A$ имеет множество состояний $Q_\A$, то построенный по нему ДКА $\B$ имеет множество макросостояний $Q_\B \subseteq 2^{Q_\A}$, где $2^{Q_\A}$ -- множество всех подмножеств множества $Q_\A$. Таким образом, на число состояний автомата $\B$ мы имеем верхнюю оценку $|Q_\B| \leq 2^{|Q_\A|} $. То есть, число состояний ДКА ограниченно экспоненциальной функцией от числа состояний НКА, но существует ли язык, для которого эта оценка достигается? На самом деле, когда мы говорим об оценках такого рода, нам требуется рассматривать ни один какой-то язык, а последовательность языков, по которым мы и сможем установить экспоненциальную зависимость.

	\prp Определим язык $L_i = \{w\,|\, |w|= n, w[n-i] = 1 \}$, то есть в язык $L_i$ входят все слова, в которых $1$ стоит на $i$-ом месте от конца\footnote{Во избежании путаницы, первый с конца символ -- это последний символ слова.}. Постройте НКА, распознающий язык $L_3$. По построенному НКА постройте ДКА. 

	\prpstar Докажите, что на языках $L_i$ между НКА и построенными по ним ДКА достигается экспоненциальный разрыв.
	
	\upr Почему для доказательства экспоненциального разрыва необходима бесконечная последовательность языков, а не достаточно конечной?



	


	\section{Алгоритм Кнута-Морриса-Пратта}

	Одно из простых и естественных применений регулярных выражений -- поиск в тексте (слове)~$t$ вхождения некоторого слова $w$. В терминах регулярных выражений, задача состоит в проверке принадлежности слова $t$ языку, порождаемому РВ~$\Sigma^*w\Sigma^*$. Однако, сходу придумать алгоритм, который выполняет эту проверку за линейное время не очень просто. Таким алгоритмом является алгоритм Кнута-Морриса-Пратта (КМП) и здесь мы опишем его на языке автоматов. С самим алгоритмом можно познакомиться, например в 10-ой главе книги А. Шеня «Программирование. Теоремы и задачи». Её можно в свободном доступе скачать \href{http://mccme.ru/free-books}{здесь}. Я рекомендую изучить КМП-алгоритм по этой книге, в этом разделе я лишь скажу пару слов о его связи с автоматами, а точнее дам на эту тему пару задач. 

	Для того, чтобы описать КМП-алгоритм, нам потребуется сначала ввести понятие префикс-функции.

	 \begin{Def}
			Назовём \emph{префикс-функцией} функцию $l: \Sigma^* \to \Sigma^*$, которая возвращает самый длинный собственный\footnote{То есть префикс, не совпадающий со всем словом $w$.} префикс слова $w$, являющийся одновременно его суффиксом. 
		\end{Def}

		\begin{Example} Приведём пример вычисления префикс-функции.
	\bigskip		
	\vspace{-1em}		
	\begin{multicols}{2} 
		\vspace*{-7ex}
		\begin{align*}
			l(a^{n+1}) &= a^n\\ 
			l(ababa) &= aba\\
			l(abb) &= \eps
		 \end{align*}					
		 \begin{align*}   
			l(aabaaabaa) &= aabaa\\ 
			l(aabaa) &= aa
		\end{align*}
	\end{multicols}		
	\end{Example}

	 У префикс-функции есть важное свойство -- все собственные префиксы слова $w$, которые являются его суффиксами лежат в последовательности $l(w), l(l(w)),\ldots$
	
	\upr Докажите это свойство.
	\medskip

	Зафиксируем слово $w$. Обозначим через $w[i,j]$ подслово $w_iw_{i+1}\ldots w_j$ слова $w = w_1w_2\ldots w_n$, здесь всюду $w_k \in \Sigma$. Для удобства будем считать, что $w[0,0] = \eps$, а $w[0,k] = w[1,k]$ при $k > 0$. Определим автомат, который будем называть \emph{автоматом Кнута-Морриса-Пратта} или КМП-автоматом для слова $w$.

	\begin{Def} КМП-автоматом $\A_w$ для слова $w \in \Sigma^*$ длины $n$, называется автомат, который задан набором $(Q,\; \Sigma,\; q_0,\; \delta,\; F)$, где
	\medskip

		\begin{itemize}
			\item $Q = \{\; w[0,0],\; w[0,1],\; w[0,2], \ldots,\; w[0,n]\; \}$;
			\item $q_0 = w[0,0]$;
			\item $ \delta(w[0,k], a) = \begin{cases}

						\vspace{0.5ex}

					\, w[0,k+1], & \text{при } w[0,k+1] = w[0,k]a \text{ и }  k < n;\\

					\vspace{0.5ex}

					\, l(w[0,k]a), & \text{при } w[0,k+1] \neq w[0,k]a \text{ и }  k < n;\\

					\, w[0,n], & \text{при } k = n.
			\end{cases} $
			\item $F = \{ w[0,n] \}$.
		\end{itemize}

	\end{Def}

	\bigskip

	\begin{Remark}
		В качестве множества состояний КМП-автомата выступает множество слов, поэтому применение для состояний операций со словами, например <<$w[0,k+1] = w[0,k]a$>>, при определении функции переходов корректно и осмысленно. % выражения вида <<$w[0,k+1] = w[0,k]a$>> осмысленны и в случае интерпретации . %, поэтому использование операций со словами при определении функции переходов корректно и осмысленно.
	\end{Remark}
      
	\upr Убедитесь, что КМП-автомат для слова $bababa$, почти совпадает с ДКА, построенным на семинаре по НКА для $\Sigma^*bababa\Sigma^*$

	\prp Постройте КМП-автомат для слова $abababb$ и продемонстрируйте его работу на слове $ababababb$.
	\medskip
	
	Алгоритм построения КМП-автомата кажется довольно простым. Однако, его ключевое место -- вычисление префикс функции. Очевидное переборное вычисление префикс-функции осуществляется квадратичным алгоритмом ( за $O(|w|^2)$). Оказывается, префикс-функцию специального вида, $l(w[0,k]a), w[k+1] \neq a$, можно вычислить линейным алгоритмом! Примерно это и реализует оригинальный КМП-алгоритм, который работает за линейное время. В книжке Шеня представлен модифицированный вариант КМП-алгоритма, который чуть проще реализовать; он также работает за линейное время -- оценка следует из амортизационного анализа (см. задачу 10.4.3 этой).    %Как же он это делает?
	
%Хитрость тут вот в чём. Оказывается чтобы найти такое $m$, что $l(w[0,k])a = w[0,m]$ нужно последовательно вычислять префикс-функцию от $w[0,k]$: $$w[0,k_1] = l(w[0,k]), w[0,k_2] = l(l(w[0,k])), w[0,k_3] =   l(l(l(w[0,k]))), \ldots $$
%до тех пор, пока $w[0,k_i+1] = w[0,k_i]a$ для $k_i$ с наименьшим $i$ -- искомое $m$ и будет равно $k_i$.

	\section{Структура данных <<Словарь>>}

	Под словарём понимают структуру данных, с помощью которой можно проверять вхождение слова в множество. У этой структуры данных есть следующие операции:
	\begin{itemize}
		\item $\ins$: добавить слово $x$ в словарь;
		\item $\test$: проверить входит ли слово $x$ в словарь;
		\item $\out$: удалить слово $x$ из словаря.
	\end{itemize}                                       

	Эту структуру данных можно реализовать с помощью автомата. На рис.~\ref{Vocabulary} показан пример словаря с содержимым $S = \{a,\, ba,\, ab,\, abb,\, abab \}$, который реализован через ДКА. ДКА~$\A$ принимает слово $x$ тогда и только тогда, когда $x \in S$.

	\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)                      {$\eps$};
		  \node[state, accepting]          (a) [below right = of eps] {$a$};
		  \node[state]          (b) [above right =of eps] {$b$};
		  \node[state, accepting]          (ba) [right =of b] {$ba$};
		  \node[state, accepting]          (ab) [above right = 2cm of a] {$ab$};
		  \node[state, accepting]          (abb) [right = 3cm of ab] {$abb$};
	      \node[state]          (aba) [below = of abb] {$aba$};
		  \node[state, accepting]          (abab) [right = 3cm of aba] {$abab$};
		 % \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{ДКА~$\A$ реализует словарь}\label{Vocabulary}
	\end{figure}  


	\prp Постройте алгоритмы, реализующие операции $\ins$ и $\out$ для ДКА, реализующих словарь. В результате этих операций должен получиться ДКА, который реализует словарь с соответственно изменившимся содержимым.

	\prp Постройте алгоритм, который получает на вход конечное множество слов $S$ и возвращает ДКА, реализующий словарь с содержимым $S$. Используйте при построении только известные из курса алгоритмы для регулярных множеств (выражений) и конечных автоматов.          

	\medskip

	\noindent\textbf{Замечание.} В задачах, в которых требуется построить алгоритм, необходимо доказательство его корректности.

	\medskip


	\prp Постройте ДКА для словаря $\{ac, acb, b, ba, c, cbb\}$. Добавьте в полученный словарь слово $ab$ и удалите слово $ac$.



		\section{Дополнительные задачи}	

		\prp Приведите протокол работы КМП-алгоритма при поиске подслова $abba$ в слове $abbbababbab$.
		
     \begin{Remark}
     	          Здесь идёт речь именно о КМП-алгоритме, а не о демонстрации работы КМП-автомата! Кроме того, префикс функция должна быть вычислена по алгоритму, описанному в книжке Шеня, а не методом внимательного вглядывания.
     \end{Remark}

\end{document}
