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

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{indentfirst}
\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\varnothing
\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\prsubr{\medskip\noindent\stepcounter{subproblem}{\sf \thesubproblem)} }

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

\medskip

\begin{center}
	{\Large Замкнутость регулярных языков, теорема Майхилла-Нероуда и минимальные автоматы}
\end{center}

\bigskip



\noindent{\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}
		
		
		Операция взятия морфизма переносится на множества естественным образом: $\varphi(X) = \{ \varphi(x)\,|\, x \in X  \}$.
		
Морфизм является частным случаем понятия гомоморфизма, которое вы изучали в рамках курса высшей алгебры. В современной терминологии гомоморфизмы также называют просто морфизмами.
		
		\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$.  Обратите внимание, что отношение эквивалентности задано на множестве всех слов $\Sigma^*$, а не только на словах языка $L$: таким образом, $x$ и $y$ в определении -- произвольные слова. Формально, $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,x_2, \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$, поэтому $w \sim_L x_i$. Таким образом, мощность фактормножества $\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$ лежит в языке $ L$, то и слово $w $ тогда лежит в языке $ L$, иначе различающим для них будет пустое слово.
		
%A.R.: выше написана глупость какая-то.

	\end{proof}

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


\section{Построение минимального автомата}

ДКА $\A$ называется \emph{минимальным} автоматом, распознающим язык $L$, если $L(\A) = L$ и не существует ДКА $\B$, такого что $L(\B) = L$ и число состояний автомата $\B$ меньше числа состояний автомата $\A$.

Для доказательства существования и корректности построения минимального автомата мы будем использовать теорему Майхилла-Нероуда. Нам потребуется аналогичное отношению М.Н. отношение эквивалентности, определённое на состояниях. Будем использовать обозначение $q \xrightarrow{w} p$, если из состояния $q$ обрабатывая слово $w$, автомат переходит в состояние $p$ или что то же самое $(q, w) \vdash^* (p,\eps)$.

\begin{Def}
Зафиксируем автомат $\A$, распознающий язык $L$. Пусть $q_0 \xrightarrow{ x_i} q_i$, а $q_0 \xrightarrow{ x_j} q_j$. Тогда $q_i \sim_L q_j$ тогда и только тогда, когда $x_i \sim_L x_j$.  Данное отношение мы назовём соответствующим отношению Майхилла-Нероуда.
\end{Def}

Неэквивалентные состояния называются \emph{различимыми}. Обратите внимание, что это \emph{два разных} отношения эквивалентности, потому что одно из них определено на множестве всех слов, а другое на множестве состояний. Мы обозначаем одинаково два разных отношения, потому что они схожи, но определены на разных объектах, поэтому это не приведёт к путанице.
%A.R.: На самом деле нет, но ввод ещё одной буквы приведёт к ещё б'ольшей беде.

\begin{Theorem}\label{min-auto}
	Для каждого регулярного языка, существует минимальный полный автомат, распознающий его. Состояния минимального автомата соответствуют классам эквивалентности по отношению Майхилла-Нероуда $\sim_L$ 
\end{Theorem}
\begin{proof}
	В силу теоремы Майхилла-Нероуда, язык $L$ регулярен тогда и только тогда, когда отношение $\sim_L$ имеет конечный индекс. Рассмотрим автомат $\A$, построенный в доказательстве теоремы Майхилла-Нероуда и покажем, что он является минимальным. Допустим противное -- пусть автомат $\B$ имеет меньшее число состояний, чем $\A$. Тогда, по принципу Дирихле, существует два слова $x_i$ и $x_j$, такие что $x_i \not\sim_L x_j $ и в автомате $\B$ при этом $q_0 \xrightarrow{x_i} q$ и $ q_0 \xrightarrow{x_j} q$. Так как $x_i \not\sim_L x_j $, то найдётся такое слово $z$, что $x_iz \in L$, а $x_jz \not\in L$. Но тогда с одной стороны $q \xrightarrow{z} q_f \in F$, т.к. $x_iz \in L$, а с другой стороны $q \xrightarrow{z} q_{\bar f} \not\in F$, поскольку $x_jz \not\in L$ -- приходим к противоречию.
\end{proof}


Просто из факта того, что язык $L$ имеет конечное число классов эквивалентности М.-Н., не совсем ясно как построить автомат $\A$, распознающий $L$. Однако, имея любой ДКА, распознающий $L$ можно конструктивно построить по нему минимальный автомат. 
Рассмотрим регулярный язык $L$ и распознающий его полный ДКА $\A$. Идея построения по автомату $\A$ минимального состоит в склейке эквивалентных состояний. Под склейкой состояний $q_i \sim_L q_j$ мы понимаем удаление состояния $q_j$  из автомата $\A$ и направление всех переходов ведущих в него в состояние $q_i$.

\begin{Claim}
	Склеив все эквивалентные состояния автомата $\A$, мы получим минимальный автомат.
\end{Claim}
\begin{proof}
	Склейка состояний $q_i \sim_L q_j$ не изменит язык $L(\A)$, потому что из состояния $q_j$ по слову $z$, автомат $\A$ попадает в принимающее состояние тогда и только тогда, когда он попадает в принимающее состояние по слову $z$ из состояния $q_i$. Таким образом, склеив все эквивалентные состояния автомата $\A$, мы получим минимальный автомат, потому что в силу определения эквивалентности на состояниях каждое состояние соответствует классу эквивалентности М.-Н. и по теореме \ref{min-auto}, он является минимальным. 
\end{proof}

Осталось привести алгоритм склейки состояний.\\
\smallskip

\noindent\textbf{Алгоритм.} На вход алгоритма подаётся ДКА $\A$.\\
\textbf{1.} В случае, если автомат $\A$ не является полным, пополним автомат $\A$, добавив состояние $q_D$, такое что $q_D \xrightarrow{\Sigma} q_D$, и если $\delta(q,\sigma)=\es$, то теперь $\delta(q,\sigma)=q_D$. Если в $\A$ есть состояния, не достижимые из начального состояния, удалим их.\\

\noindent\textbf{2.} Разделим множество состояний на два подмножества: множество принимающих состояний $F = Q_1$ и его дополнение $Q\setminus F = Q_2$.\\

\noindent$\mathbf{i+1}$. Пусть после $i$-ого шага алгоритма множество состояний $Q$ разбито на $j$ подмножеств $Q_1,\ldots,Q_j$. Зафиксируем символ $\sigma \in \Sigma$ сделаем следующее. Если для $q_k \in Q_k$ $q_k \xrightarrow{\sigma} q_l \in Q_l$, поместим состояние $q_k$ в множество $Q_{k,l}$. Получили новое разбиение $Q$ на подмножества $Q_{k,l}$ и повторяем для него эту процедуру для оставшихся символов $\sigma \in \Sigma$. Если после $|\Sigma|$ разбиений мы получили разбиение, в котором $j$ подмножеств, то алгоритм останавливается, в противном случае он продолжает работу. 
\medskip

Склеив все состояния, попавшие в одно подмножество, получим минимальный автомат. 

\prpstar В описании алгоритма минимизации оставлен пробел (как и в некоторых учебниках, например, в учебнике Хопкрофта Мотвани и Ульмана). Приведите пример ДКА, для которого применение указанного алгоритма не приводит к минимальному автомату. Исправьте этот пробел.



\section{Задачи}

\prp Доказать, что для языка $L$ выполняется лемма о накачке, но он не является регулярным. Обозначим за ${\rm PRIMES}$ множество простых чисел. Напомним, что $A^+ = AA^*$.
$$ L = b^* \cup \{ab^{\,p}\,|\, p \in {\rm PRIMES} \} \cup aa^+b^*.  $$

\medskip

\prp К языку $L_1$ добавили конечный язык $R$ и получили язык $L$ ($L = L_1\cup R$). Язык $L$ оказался регулярным. Верно ли, что язык $L_1$ мог быть нерегулярным?

\bigskip

\prp Язык $L$ задан автоматом $\A$. Построить минимальный автомат для языка $L$.

\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]          (q_2) [ right = of q_1] {$q_2$};
  \node[state, accepting]           (q_3) [ right = of q_2] {$q_3$};

  \path[->] 
		(q_0)	edge		node	{$a$}	(q_1)
				edge [bend left] node {$b$}	(q_3)
		(q_1)
				edge		node	{$b$}	(q_2)
		(q_2)
				edge		node	{$b$}	(q_3)
				edge [bend left] node {$a$}	(q_1);
 \end{tikzpicture}
\medskip

\prp Постройте минимальный автомат для языка $\bar L$ из предыдущей задачи.

\bigskip

\prp Найдите все классы эквивалентности Майхилла-Нероуда для языка $\Sigma^*ab\Sigma^*$ и постройте по ним ДКА.

\bigskip

\prp Является ли регулярным язык~$L$ всех слов в алфавите  $\{ 0, 1 \}$, которые представляют числа в двоичной записи, дающие остаток два при делении на три (слово читается со старших разрядов). Например, $001010\, (1010_2=10_{10} = 3 \times 3+1)  \not\in  L$,
а $10001\, (10001_{2}=17_{10} = 5 \times  3+2)  \in  L$.
 
\prp Опишите классы эквивалентности Майхилла-Нероуда для языка $L$. В случае конечности множества классов, постройте минимальный полный ДКА, распознающий $L$. $L = $


\prsubr $\{ w \mid |w|_a = |w|_b \}$;\quad \prsubr  $\{ w \mid |w|_{ab} = |w|_{ba} \}$.


\end{document}