 \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 принцип мат. индукции, язык, регулярные выражения, конкатенация, объединение, итерация,  
	%, порождающая грамматика,  КС- и автоматные грамматики;
	конечные автоматы (КА), детерминированные и недетерминированные КА, регулярные языки.
	%алгебра регулярных выражений,  примеры нерегулярных языков;
	%поиск подстрок, алгоритм Кнута- Морисса- Пратта.

	%языки скобочных выражений (языки Дика). 
	}
	
	\setcounter{section}{-1}
	\section{Ликбез}
		Задачи помеченные $\dagger$ не являются сложными, однако являются в какой-то мере дополнительными. Я рекомендую их решать, но жёстко этого не требую.
		\subsection{Отношение эквивалентности}

		\emph{(Бинарным) отношением} $R$ на множестве $X$ называется некоторое подмножество $R$ множества $ X\times X$.
		Говорят, что пара элементов $x$ и $y$ удовлетворяют отношению $R$, если пара $(x,y)$ принадлежит $R$. Это принято обозначать $xRy$.


			Отношение $R$ называется \emph{рефлексивным}, если для любого $x \in X$ справедливо $xRx$. Отношение называется симметричным, если из факта $xRy$ следует $yRx$. Отношение называется транзитивным, если из $xRy$ и $yRz$ следует $xRz$.

		\begin{Def}
			Бинарное отношение называется \emph{отношением эквивалентности}, если оно является рефлексивным, симметричным и транзитивным. Такие отношения обычно обозначаются $\sim_R$ или просто $\sim$, когда ясно о каком отношении идёт речь.
		\end{Def}

		\emph{Классом эквивалентности} $C(x)$ называется множество элементов эквивалентных $x$. То есть $C(x) = \{y\,|\, x \sim y \}$.

		\upr Показать, что классы эквивалентности $C(x)$ и $C(y)$ либо не пересекаются, либо совпадают.
		\medskip


		Множество $X$, над которым задано отношение эквивалентности $\sim$, можно представить в виде объединения попарно непересекающихся множеств -- классов эквивалентности, то есть \emph{факторизовать} по отношению эквивалентности. Фактормножество обозначается как $X\quotient\, $. То есть, $X\quotient\ = \{ C(x)\,|\, x \in X \} $. Мощность фактормножества называется \emph{индексом} отношения эквивалентности.
		
		\subsection{Морфизмы}
		 \begin{Def}
			Морфизмом называется  отображение $\varphi : \Sigma^* \to \Delta^*$, для которого справедливо:  $w = uv$, тогда $\varphi(w) = \varphi(u)\cdot\varphi(v)$.
		\end{Def}
		
Гомоморфизм, который вы изучали в рамках высшей алгебры, является частным случаем морфизма и в современной терминологии его также называют морфизмом.
		
		\upr Показать, что морфизм $\varphi$ однозначно определён, если для каждой буквы $\sigma$ алфавита $\Sigma$ определено значение $\varphi(\sigma)$.
		\medskip
		
		\prdag Доказать, что регулярные языки замкнуты относительно взятия морфизма.
		\begin{Def}
			 Обратным морфизмом $\varphi^{-1} $ к морфизму $\varphi : \Sigma^* \to \Delta^*$, называется отображение $\varphi^{-1}(w) = \{ v\,|\, \varphi(v) = w \}$  
		\end{Def}

		Морфизмы применяются не только к словам, но и к языкам. Запись $\varphi(L)$ означает, что $\varphi(L) = \{ \varphi(w)\,|\, w \in L \}$, то же самое относится и к обратному морфизму: $\varphi^{-1}(L) = \{w\,|\, \ph(w) \in L\}$.


		\prdag Верно ли, что для любого языка $L$ и любого морфизма $\varphi : \Sigma^* \to \Sigma^*$

		\prsub язык $\varphi(\varphi^{-1}(L))$ совпадает с $L$?

		\prsub язык $\varphi^{-1}(\varphi(L))$ совпадает с $L$?

		\prsub $\varphi(\varphi^{-1}(L)) \stackrel{?}{=} \varphi^{-1}(\varphi(L))$

		\medskip
		
		\prdag Доказать, что регулярные языки замкнуты относительно операции взятия обратного морфизма.
		
	\section{Теорема Майхилла-Нероуда }


	Поскольку мы работаем со словами, то нас будут интересовать бинарные отношения на множестве $\Sigma^*$. А именно, нас будет интересовать следующее отношение эквивалентности, задаваемые языком $L$. Слово $x$ $L$-эквивалентно слову $y$, если для любого суффикса $z$, слова $xz$ и $yz$ либо одновременно лежат в $L$, либо одновременно не принадлежат $L$. Формально, $x\sim_L y \iff \forall z  \in \Sigma^* :  xz \in L \Leftrightarrow yz \in L$. Это отношение эквивалентности называется отношением Майхилла-Нероуда.


	Легко видеть, что это отношение является правоинвариантным, то есть если $x \sim_L y$, то $xz \sim_L yz $ для любого $z$.

	\begin{Theorem}[Майхилл-Нероуд, 1958]
		Язык $L$ является регулярным тогда и только тогда, когда $\Sigma^*$ разбивается на конечное число классов эквивалентности по отношению $\sim_L$. Другими словами, когда $\sim_L$ -- отношение конечного индекса. 
	\end{Theorem}
	\begin{proof}
		Если язык $L$ регулярен, то отношение $\sim_L$  очевидно имеет конечный индекс. Действительно, возьмём произвольный полный\footnote{ДКА является полным, если в нём определены все переходы, т.е. $\forall q \in Q, \forall \sigma \in \Sigma : \delta(q,\sigma) \neq \es$.} ДКА $\A$, распознающий $L$, в котором все состояния достижимы\footnote{формально в $Q$ могут быть состояния, в которые невозможно попасть из $q_0$. Обратите внимание, что они могут возникать при применении конструкции произведения.}. Пусть $\A$ имеет $n$ состояний. Рассмотрим  слова $x_1,x2, \ldots,x_n$, такие что $\delta(q_0,x_i) = q_i$. По любому слову $w$, автомат попадает в некоторое состояние $q_i$, а значит $w \in C(x_i)$, потому что для любого слова $z$,  состояние $q = \delta(q_i, z) $ либо принимающие, либо нет, а $\delta(q_0,x_iz) = \delta(q_0,wz) = \delta(q_i,z) = q$, поэтому $x \sim_L z$. Таким образом, мощность фактормножества $\Sigma^*\quotient_L$ не превосходит $n$, а значит самих классов эквивалентности конечное число.

		В обратную сторону. Пусть таких классов конечное число. Тогда, $\Sigma^*\quotient_L = \{C_1, C_2, \ldots, C_n\}$. Построим, имея такое разбиение, ДКА $\A$, распознающий $L$. \\
		\textbf{Построение:} Можеством состояний является фактормножество, то есть $Q = \Sigma^*\quotient_L$, в качестве начального состояния $q_0$ возьмём $C(\eps)$. Функцию переходов $\delta$ определим следующим образом. Пусть $x_i$ -- представитель класса $C_i$, тогда $\delta(C_i, \sigma) = C_j$, если $x_i\sigma \in C_j$. Осталось описать множество принимающих состояний: $F = \{ C_i\, |\, x_i \in L \}$.\\
		\textbf{Корректность:} По построению, автомат $\A$ при обработке слова $w$ на $i$-ом шаге оказывается в состоянии\footnote{Напомним, что $w[i,j]$ есть подслово слова $w$, начинающееся с $i$-го символа $w$ и заканчивающееся $j$-ым.} $C(w[1,i])$. Таким образом, обработав слово, автомат перейдёт в состояние $C(w)$, которое будет принимающим тогда и только тогда, когда $w \in L$, поскольку если $x_i \sim_L w$, и $x_i \in L$, а $w \not\in L$, то отношение $\sim_L$ не является правоинвариантным: $\eps \sim_L \eps$, но $\eps\cdot x_i \not\sim_L \eps\cdot w$, приходим к противоречию.
	\end{proof}

	 Эта теорема очень часто вызывает непонимание: почему мы можем построить автомат, если существует конечное разбиение. Да, допустим, что разбиение есть, но кто же нам его дал?  При доказательстве теорем, мы можем использовать факты из логики вида «утверждение всегда либо истинно, либо ложно» и используем оракул, который отвечает на наши вопросы -- если Оракул ответил «истинно», то мы начинаем одну ветвь рассуждений, если «ложно», то другую. Если во всех ветках ответа оракула, мы доказали правильность нашего утверждения, то утверждение считается доказанным. Так, мы пользовались тем, что оракул сообщал нам конечное ли у нас число классов эквивалентности или нет, лежат ли два слова в одном классе эквивалентности или нет и мы успешно \emph{построили} автомат в доказательстве -- это означает, что мы доказали, что если классов эквивалентности конечное число, то такой автомат есть. На практике же, зная только то, что классов эквивалентности конечное число, автомат мы можем и не построить -- для того, чтобы построить автомат, оракул должен быть вычислимой функцией, то есть мы должны уметь строить такую машину Тьюринга\footnote{Или, например, мы можем написать программу на языке C.}, которая отвечала бы на наши вопросы. Доказательства, в которых оракул вычислим, называются \emph{конструктивными}.

	\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$ -- нерегуляный язык.

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

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