 \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}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\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\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}{\rm \thesubproblem .  } }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}
\begin{document}
	\centerline{\LARGE Задание 3}

	\medskip

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

	\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{Алгоритм Кнута-Морриса-Пратта и его связь с автоматами}

		НКА -- очень удобный инструмент для описания автоматов, которые ищут слова в тексте. Например, автомат 
		\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] 					(q_5) [right = of q_4]	{$q_5$};
				\node [state, accepting] 		(q_6) [right = of q_5]	{$q_6$};
			 % \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		node    {$b $} (q_6)
				(q_6)   edge [loop]	node	{$a,b$} ();
			\end{tikzpicture}
		\end{center}
		проверяет имеет ли поданное на вход слово подслово $ababab$.

		
		Как мы уже обсуждали, для алгоритмической проверки принадлежности слова языку, распознаваемому НКА, по нему следует строить ДКА. Однако, в специальных случаях, используемых на практике, подобно описанному выше, есть более удобные алгоритмы и один из них -- алгоритм Кнута-Морриса-Пратта. Этот алгоритм подробно описан в 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
	
	На семинаре мы разобрали алгоритм построения КМП-автомата. Он основывался на том, что КМП-автомат, который ищет в тексте $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)$ осуществляется за константное время, то есть ничего не стоит.





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


	


\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}
	
\upr В предыдущем примере показано громоздкое доказательство: его можно сделать проще, убрав перебор кучи случаев, воспользовавшись структурой слова. Постарайтесь получить доказательство в одну строчку.

\bigskip

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

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

\end{document}
