 \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 Задание 3}

	\medskip

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

\begin{center}
	{\Large НКА и ДКА
	
		Лемма о накачке 
		
		\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{Лемма о накачке\footnote{Также известна как лемма о разрастании. Неудачные переводы неудачного термина «Pumping Lemma».}}

	В данном разделе мы поговорим о лемме о накачке -- одном из способов доказательства нерегулярности языка.

	\begin{Lemma}
		Для любого регулярного языка $L$ существует такая константа $p \geq 1$, что  для любого слова $w$ из $L$ длиннее $p$, справедливо:
		\begin{itemize}
			\item $w = xyz$
			\item $|y| \geq 1$
			\item $|xy| \leq p$
			\item $\forall i \geq 0, xy^iz \in L  $.
		\end{itemize} 
	\end{Lemma}
	\begin{proof}
		Поскольку $L \in \REG$, то существует ДКА $\A$ распознающий $L$. Пусть $\A$ имеет $N$ состояний. Возьмём $p = N+1$. Тогда, если если слово $w $ принадлежит $ L$  и  $|w| \geq p$, то это означает, что при обработке $w$ автомат $\A$ оказался в некотором сотоянии $q$ дважды. Пусть в первый раз автомат оказался в $q$ после прочтения префикса $x$, а второй раз, при прочтении префикса $xy$. Тогда $\delta(q, y) = q$, но поскольку $w = xyz$ принадлежит $L$, то это означает, что $\delta(q,z) = q_f \in F$, а значит все слова вида $xy^iz$, $i\geq 0$ лежат в $L$.
	\end{proof}

	Обратите внимание, что при доказательстве леммы, я использовал те же трюки, что и в доказательстве на семинаре того, что $a^nb^n$ -- нерегуляный язык. Также обратите внимание на то, что формула $w = xyz$ означает, что для слова $w$ существует такое разбиение $xyz$, для которого выполняются следующие свойства и утверждение леммы: часто студенты это равенство ошибочно воспринимают как «для любого разбиения».


	\begin{Example}
		Используем лемму о накачке для доказательства христоматийного примера нерегулярности языка $L = \{0^n1^n\ |\ n \geq 0\}$. 	
	\end{Example}
	\begin{proof}
		Допустим, что язык $L$ регулярный. Тогда, по лемме о накачке, существует константа $p$, что для любого слова  $w$ длиннее $p$, существует такое разбиение $xyz$, что $|xy| \leq p$ и слова $xy^iz$, $ i \geq 0$ принадлежат $L$.

		Рассмотрим $w = 0^p1^p$. Если такое разбиение существует, то $y$ имеет вид $0^k$ или $1^k$, $k \geq 1$ -- в противном случае, если $y = 0^k1^l$, то  $y^2 = 0^k1^l0^k1^l$, но в $L$ нет слов, в которых за $1$ следует $0$.
	Допустим, что $y = 0^k$. Тогда $x = 0^m$, $z = 0^l1^p$, $k+m+l = p$. Но тогда, по лемме о накачке $xy^2z \in L$, а значит, слово $0^{m+2k+l}1^l \in L$, но $m+2k+l > p$, т.к. $m+k+l = p$ и $k > 0$, поскольку $|y| \geq 1$. Аналогично приходим к противоречию когда $y = 1^k$.
	\end{proof}
	
	\begin{Remark}
		Для доказательства того, что некоторый язык является нерегулярным, при использовании леммы о накачке необходимо предъявить не одно конкретное слово, а последовательность слов, зависящих от $p$ (константы леммы). Если вы предъявите всего одно слово, то кто-то очень умный сможет просто взять б\'{о}льшую константу.
	\end{Remark}
	
\upr В предыдущем примере показано громоздкое доказательство: его можно сделать проще, убрав перебор случаев, воспользовавшись структурой слова. Постарайтесь получить доказательство в одну строчку или восстановить доказательство с семинара.

\bigskip

		У этой леммы слишком много недостатков. Во-первых, она не всегда применима: утверждение леммы справедливо для некоторых нерегулярных языков. Во-вторых, неаккуратное применение леммы влечёт громоздкие выкладки. Даже для такого простого примера как $L  = \{0^n1^n \mid n\geq 0 \}$, неподкованному в этой науке человеку потребуется применить много усилий, а в более сложных случаев перебор возможных $y$ может оказаться ещё более громоздким. Фактически лемма о накачке работает в тех же случаях, когда срабатывает техника, обсуждённая на семинаре, поэтому некоторым возможно будет удобно применять эту технику напрямую. Тем не менее, у этой леммы есть очень важный плюс -- учебный. Во-первых, лемма о накачке показывает структуру регулярного языка: разность длин двух последовательных слов из регулярного языка ограниченна линейной функцией. Во-вторых, существует ещё лемма о накачке для контекстно-свободных языков (которые мы изучим позже), для понимания которой стоит изучить более простую лемму о накачке для регулярных языков. В случае КС-языков, доказательство непринадлежности языка классу КС уже куда менее очевидно, так что лемма о накачке становится мощным и одним из основных инструментов.
		
%		\section{Задачи}
		%\prp Доказать, что регулярные языки замкнуты относительно операций объединения, пересечения и дополнения.
		%\medskip
		
%		\prp Применить лемму о накачке для доказательства нерегулярности языка $L = \{a^{2^n}\ |\ n \geq 0 \}$.
%		\medskip

\prp Будут ли регулярными следующие языки?

\medskip

 \prsub  $L = \{ a^{2013n+5}\mid n=0,1, \} \cap \{ a^{503k+29}\mid k=401,402,\ldots \}  \subseteq  \{ a^* \}$.

\medskip

 \prsub  $L_2 = \{ a^{200n^2+1}\mid n=1000,1001,\ldots \}  \subseteq  \{ a^* \}$.

\medskip


\prsub  Язык $L_3$ всех слов в алфавите  $\{ 0, 1 \}$, которые представляют числа в двоичной записи, дающие остаток два при делении на три (слово читается со старших разрядов). Например, $001010\, (1010_2=10_{10} = 3 \times 3+1)  \not\in  L_3$,
а $10001\, (10001_{2}=17_{10} = 5 \times  3+2)  \in  L_3 $.

				
\begin{comment}
	
				
		\prpfrom[6] Будут ли регулярными следующие языки:
		
		\prsub $L_1 = \{a^{2013n+5}\,|\, n = 0,1,\ldots \}\cap\{a^{509k+29}\,|\, k=401,402,\ldots\} \subseteq\{a^*\}$
		
		\prsub $L_2 = \{a^{200n^2+1}\,|\, n = 1000,1001,\ldots \} \subseteq\{a^*\}$
		
		\prsub  Язык $L_3$ всех слов в алфавите ${0, 1}$, которые представляют числа в двоичной записи, дающие остаток два при делении на три (слово читается со старших разрядов).
		Например,  $001010 (1010_2=1010 = 3\times3+1) \not\in L_3$, 
		а $10001 (10001_2=1710 = 5\times 3+2) \in L_3$ .
		
		\prsubstar Построить ДКА, распознающий язык $L_3$.
		
		\prpstar Показать, что лемма о накачке выполняется для языка $L = \{uvwxy\ |\ u,y \in \{0,1,2,3\}^*; v,w,x \in \{0,1,2,3\}, $ причём $v=w$ или $v=x$ или $x=w$ $ \} \cup \{w\ |\ w \in \{0,1,2,3\}^*, $ причём $\frac17$ букв в $w$ есть $3$  $ \}$. Более формально:\\
			$L = \{uvwxy\ |\ u,y \in \{0,1,2,3\}^*; v,w,x \in \{0,1,2,3\} \land (v=w\ \lor\ v=x\ \lor\ x=w ) \} \cup  \{w\ |\ w \in \{0,1,2,3\}^*,  \left\lceil\frac{|w|}7\right\rceil =  |w|_3   \}$

		\prsub Доказать, что $L \not\in \REG$.
		
\end{comment}	

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

		НКА -- очень удобный инструмент для описания автоматов, которые ищут слова в тексте. Например, автомат 
		\begin{center}
		 	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]
			  %\draw[help lines] (0,0) grid (3,2);
					\node	(A) {\large \quad$\A:$};
			  	\node[state,initial]		 	(q_0) [right = of A]	{$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, accepting] 					(q_4) [right = of q_3]	{$q_4$};
			  \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    {$a $} (q_4)
				(q_4)   edge [loop]	node	{$a,b$} ();
			\end{tikzpicture}
		\end{center}
		проверяет имеет ли поданное на вход слово подслово $abaa$.
		\medskip

\prp Постройте по НКА $\A$ ДКА $\B$.

\prend
		
		Как мы уже обсуждали, для алгоритмической проверки принадлежности слова языку, распознаваемому НКА, по нему следует строить ДКА. Однако, в специальных случаях, используемых на практике, подобно описанному выше, есть более удобные алгоритмы и один из них -- алгоритм Кнута-Морриса-Пратта. Этот алгоритм подробно описан в 10-ой главе книги А. Шеня «Программирование. Теоремы и задачи». Её можно в свободном доступе скачать \href{http://mccme.ru/free-books}{здесь}. Я рекомендую изучить КМП-алгоритм по этой книге, в этом разделе я лишь скажу пару слов о его связи с автоматами, а точнее дам на эту тему пару задач.


		В основе этого алгоритма -- использование для поиска слова вычисления префикс-функции.

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

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

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

\medskip
	\prpstar Докажите, что в ДКА, распознающем язык $\Sigma^*w\Sigma^*$ не может быть меньше состояний чем элементов последовательности $l(w), l(l(w)),\ldots$
\bigskip

Зафиксируем слово $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}
	В качестве множества состояний КМП-автомата выступает множество слов, поэтому применение конкатенации при определении функции переходов корректно и осмысленно.
\end{Remark}


\prp Постройте КМП-автомат для слова $abaa$.
	
\begin{comment}
		На семинаре мы разобрали алгоритм построения КМП-автомата. Он основывался на том, что КМП-автомат, который ищет в тексте $t$ (вход автомата) слово $w$ (фиксированный параметр автомата) имеет $|w|+1$ состояние, каждое из которых кодирует некоторый префикс слова $w$. Если автомат находится в $i$-ом состоянии , то это означает, что обработанный участок текста имеет вид
		$$ t_1t_2\cdot\ldots\cdot t_kw_1w_2\cdot\ldots\cdot  w_i $$
	Мы считаем, что нулевое состояние кодирует пустой префикс, а значит $w_0 = \eps$. При этом, $i$ -- максимальная длина суффикса текста, совпадающая с префиксом $w$. Таким образом, если следующий символ текста не совпадает с символом $w_{i+1}$, то тогда необходимо найти новый максимальный по длине суффикс текста, который является префиксом $w$ и сделать переход по отличающейся букве в состояние, соответствующее этому префиксу. При этом, оказывается, что его длина будет обязательно не превосходить $i$.

	\medskip
	\prp Почему?
	\bigskip

	Поскольку $w$ имеет конечное число префиксов, то вычислить переходы КМП-автомата можно на конечной памяти полным перебором безо всякой науки. Но это можно сделать и используя высокую науку, обсуждение которой я был вынужден вероломно прервать на семинаре. В какой-то момент я сформулировал и объяснил утверждение из следующей задачи, потом часть аудитории его успела забыть, и в итоге не осталось времени с ним разбираться. Тем не менее, это утверждение верное и позволяет ускорить вычисление переходов КМП-автомата.

	\medskip
	\prpstar Пусть $l(xay) = x$, где $x, y$ слова над алфавитом $\{a, b\}$. Тогда $l(xayb) = l(xb)$. Докажите это утверждение.
	\bigskip

	Результаты предыдущих задач позволяют говорить о том, что КМП-алгоритм можно представить в виде последовательного вычисление префикс-функции на словах вида
		$$w\#t_1\cdot\ldots\cdot  t_n$$
	При этом, вычисление $l(w\#t_1\cdot\ldots\cdot  t_nt_{n+1})$ по значению $l(w\#t_1\cdot\ldots\cdot  t_n)$ осуществляется за константное время, то есть ничего не стоит.
	
\end{comment}

\prpstar Докажите, что КМП-автомат для слова $w$ распознаёт язык $\Sigma^*w\Sigma^*$.


%	\prstar Приведите алгоритм построения ДКА для языка $\Sigma^*w\Sigma^*$, использующий префикс-функцию.


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

		\prp Приведите протокол работы КМП-алгоритма при поиске подслова $abba$ в слове $abbbababbab$.
		


\end{document}
