 \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{indentfirst}
\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\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^*$ .  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^\dagger$ .  }\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\quotient{\backslash\negthickspace\sim}
\begin{document}
	\centerline{\LARGE Задание 1}

	\medskip

	\centerline{\Large Регулярные языки и автоматы}

	\bigskip

	{\bf Литература: }
	\begin{enumerate}
		\item {\em Хопкрофт Д., Мотвани Р., Ульман Д.}\\ Введение в теорию автоматов, языков и вычислений.\\ М.: Вильямс, 2002.

	\item {\it Ахо А., Ульман Д.}\\ Теория синтаксического анализа, перевода и компиляции\\  М.: Мир, 1978. Гл. 0, 2.

	\item {\em Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.}\\ Теория и реализация языков программирования.\\ М.: МЗ-пресс, 2006.

	\end{enumerate}

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

	%языки скобочных выражений (языки Дика). 
	}

	\section{$\TeX$}

	В этом году все задания принимаются \underline{только} в формате $\TeX$. Во-первых, через пару лет вам уже предстоит написание диплома и большинство дипломов так или иначе связаны с математикой, и уж точно в подавляющем большинстве из них присутствуют формулы. $\TeX$ -- довольно гибкий инструмент для работы с математическими текстами, он является стандартом для публикаций в крупных журналах, не зависит от платформы и с ним довольно удобно работать. Даже в переписках в сети, уже принято записывать математические формулы в стиле теха и большинство профильных сайтов поддерживают конвертацию на лету из теха в формулы. Я буду предоставлять теховские исходники ко всем заданиям. Во-вторых, в этом году я планирую частично автоматизировать процесс приёма задания, поэтому, если планы сбудутся, то с определённого момента сдавать задания в техе придётся по техническим причинам.

	В качестве литературы по теху, я рекомендую \href{ftp://ftp.mccme.ru/pub/tex/lvovsky-newbook/pdf.zip}{книгу} Львовского  и \href{http://www.ccas.ru/voron/download/voron05latex.pdf}{статью с набором примеров} Воронцова и \href{http://en.wikibooks.org/wiki/LaTeX/}{wiki-учебник}. Так же я нашёл \href{http://www.youtube.com/ShareLaTeX}{видеоуроки}, возможно они окажутся полезны.

	Техом пользуется столько людей, что практически все потребности, которые возникают в процессе написания научных текстов, уже удовлетворены. Например, для построения графов автоматов есть множество пакетов. Я предпочитаю пакет \emph{tikz}. Документация к этому пакету находится \href{http://ctan.usu.ru/graphics/pgf/base/doc/generic/pgf/pgfmanual.pdf}{здесь}.

	В качестве редактора, я рекомендую использовать \href{http://www.xm1math.net/texmaker/}{Texmaker}. Это довольно удобный кроссплатформенный редактор.

	\section{О заданиях}

	Задания сдаются еженедельно, сдать задание надо до 22:59 среды. Исходники теха и pdf с заданием нужно присылать по адресу \href{mailto:homework@rubtsov.su}{homework@rubtsov.su}, если на сайте не появятся иные указания, для писем по другому поводу стоит использовать адрес \href{mailto:alex@rubtsov.su}{alex@rubtsov.su}. В самом задании обязательно \textbf{укажите фамилию, имя и номер группы}.

	Задачи делятся на следующие категории: предбазовые, базовые, усиленные и дополнительные. Если вы не можете решить задачи предбазового уровня, то скорее всего вам стоит ещё раз разобраться с материалом. Сдавать эти задачи крайне желательно, благо они не большие по объёму, чтобы в случае критической ошибки я мог дать обратную связь. Задачи базового уровня -- это обязательные задачи. Они не представляют особой трудности, но их уже необходимо сдавать в обязательном порядке. Усиленные задачи -- это задачи в рамках курса и близкие к курсу, которые крайне желательно решать, если вы хотите автомат: успешное решение этих задач облегчит получение автомата и тем более сдачу задания.


	Каждую неделю будут проводиться контрольные на 10-15 минут. Формат -- openbook: вы можете пользоваться любой литературой, но \emph{исключительно в бумажном виде}! Оценки за контрольные $0$ и от $3$ до $7$. Без дополнительного общения, я готов в качестве автомата выставить среднюю оценку за контрольные, если у вас нет штрафных очков. Но обычно, те кто не имеют штрафных очков желают повысить оценку, поэтому среднюю оценку по контрольным следует рассматривать как оценку с которой начинается разговор. Автомат можно получить только если промежуточные общие контрольные для всего курса написаны не на два.

	За несданные задания и плохо написанные контрольные начисляются штрафные очки, которые на очных сдачах преобразуются в дополнительные задачи.
	
	Не сданное в срок задание или не написанную в срок семинарскую контрольную нельзя пересдать потом, вне зависимости от причины. Все набранные долги можно будет закрыть на очной сдаче, поэтому дополнительные меры для увеличения мировой справедливости применяться не будут.

	\section{Теоретико-множественное отступление}

	Для полноценного прохождения данного курса, вы должны помнить азы теории множеств. Вы должны знать что такое множество, пустое множество, элемент множества, основные операции над множествами: объединение, пересечение, дополнение, исключение. Однако, как показывает практика, обязательно найдутся люди, которые не помнят что такое декартово (прямое) произведение.

	\begin{Def}
		Декартовым произведением двух множеств $X$ и $Y$ называют множество $X \times Y = \{ (x,y)\ |\ x \in X,\ y \in Y \}$.

	\end{Def}

	Также нередко забывают, что множество всех подмножеств множества $X$, обозначают $2^X$.


	Восполнить пробелы в теории множеств и дискретном анализе, а также узнать много нового и интересного можно из книги Н.К. Верещагина и А. Шеня \emph{\href{http://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf}{Лекции по математической логике и теории алгоритмов.} }Эта книга, а также много других интересных и полезных книг, находятся в свободном доступе по адресу \url{http://www.mccme.ru/free-books/}.

	\section{ Регулярные языки и конечные автоматы }

	 Под \emph{алфавитом} понимается конечное множество. Мы будем обозначать алфавиты заглавными греческими буквами, такими как $\Sigma, \Gamma$. Обычно мы будем использовать двухбуквенные алфавиты $\Sigma = \{a, b\}$ или  $\Sigma = \{0, 1\}$. Множества мы будем обозначать заглавными буквами, а их элементы строчными. 

	Для \emph{букв} -- элементов алфавита -- определена операция \emph{конкатенации}: $a\cdot b = ab$.
	\emph{Слово} $w = w_1w_2\ldots w_n$ -- конкатенация букв. Длину слова $w$, мы будем обозначать $|w|$.
	Для слова $w = w_1w_2\ldots w_n$, длина $|w|$ равна $n$, $i$-ый символ слова мы будем обозначать $w[i] = w_i$,
	подслово $w_iw_{i+1}\ldots w_j$ будем обозначать $w[i,j]$. Мы не будем различать слова длины $1$ и буквы, а также
	одноэлементные множества слов и слова. Пустое слово мы будем обозначать $\eps$. Пустое слово обладает следующими свойствами:
	Для любого слова $w$, $\eps\cdot w = w \cdot \eps = w$, $|\eps| = 0$.   
	Для множеств слов определены следующие операции:

	\begin{itemize}
		\item Конкатенация: $X\cdot Y = \{ x\cdot y\ |\ x \in X,\ y \in Y  \}$.
		\item Возведение в степень: $X^n = \underbrace{X\cdot X\cdot\ldots X}_{n}$
		\item Объединение: $X | Y = X + Y = X \cup Y = \{ w\ |\ w \in X $ или $ w \in Y\} $.
		\item Итерация\footnote{Эта операция также носит название звёздочка Клини, в честь выдающегося математика Стивена Клини.} $X^* = \eps + X + X^2 + X^3 + \ldots X^n + \ldots$
	\end{itemize}

	В первой части курса мы будем изучать класс регулярных языков $\REG$. Регулярные языки определяются следующим образом:

	\begin{itemize}
		\item $\emptyset \in \REG$.
		\item $\forall \sigma \in \Sigma:\ \{ \sigma \} \in \REG $.
		\item $\forall X, Y \in \REG\ :\ X\cdot Y,\ X|Y,\ X^* \in \REG   $.
		\item Больше нет регулярных языков.
	\end{itemize}

	Так, множество всех слов над алфавитом $\Sigma$ обозначают $\Sigma^*$.


	Запись регулярных языков с использованием скобок и определённых выше операций, называют \emph{регулярным выражением}.
	Сами по себе скобки являются разделителем и не несут смысловой нагрузки: 
	Регулярное выражение $(a) $  задаёт язык $\{a\}$, $(a|b) = \{a,b\}$, $(a|b)^* = \{a,b\}^* = \Sigma^*$.
	
	\upr Показать, что $\eps \in \REG$.
	\medskip
	
В теории формальных языков, каждому классу языков соответствует модель вычислений, которая распознаёт данный класс языков. Для класса регулярных языков такой моделью является \emph{Конечный Автомат} (КА).


	\begin{Def}
		Конечный автомат $\A$ -- это устройство, описываемое набором $(Q, \Sigma, q_0, \delta, F)$, где
		\begin{itemize}
			\item $Q$ -- конечное множество состояний автомата;
			\item $\Sigma$ -- алфавит, слова над которым обрабатывает автомат;
			\item $q_0$ -- начальное состояние автомата;
			\item $\delta\ : Q \times \Sigma \to 2^Q $ -- функция переходов;
			\item $F \subset Q$ -- множество принимающих состояний.
		\end{itemize}
	\end{Def}

	Автомат является \emph{детерминированным} (ДКА), если функция переходов определена однозначно, то есть для каждого состояния $q$ и для каждого символа $\sigma$, существует не больше одного состояния $q' \in \delta(q, \sigma)$.  В противном случае, автомат является \emph{недетерминированным} (НКА).

	На вход автомата подаётся слово $w = w_1\ldots w_n$. Автомат обрабатывает слово слева направо по тактам. 


	В детерминированном случае, за такт работы автомат находится в состоянии $q$, считывает символ $\sigma$ и вычисляет функцию перехода $\delta(q, \sigma) $. Если  $\delta(q, \sigma)  = q'$, то автомат переходит в состояние $q'$, если же  $\delta(q, \sigma) = \es $, то автомат прекращает работу.


	В недетерминированном случае, за такт работы, автомат \emph{недетерминированно выбирает состояние} $q'$ из множества  $\delta(q, \sigma) $ и переходит в состоянии $q'$. В случае, если  $\delta(q, \sigma) = \es$, автомат прекращает работу. Под недетерминированном выбором, мы понимаем, следующую ситуацию. %Если слово $w$ принимается недетерминированным автоматом $\A$, то это означает, что по этому слову есть последовательность переходов из начального состояния в принимающее. Будем считать, что в этом случае, недетерминированный автомат получает такую последовательность переходов свыше и переходы выполняет именно по ней.


	Слово \emph{принимается автоматом}, если после обработки слова, автомат оказался в принимающем состоянии. Недетерминированный автомат \emph{всегда} оказывается в принимающем, состоянии, если он может в него попасть. 
	Таким образом, детерминированный автомат принимает слово, если после обработки слова он оказался в принимающем состоянии, а недетерминированный автомат принимает слово, если существует такая последовательность выборов состояний, что после обработки слова он оказывается в принимающем состоянии. 

	Назовём {\em конфигурацией} пару $(q,w) \in Q \times \Sigma^*$. На множестве конфигураций введём соответствующее тактам работы автомата бинарное отношение $\vdash$:  для всех $q' \in \delta(q,a)$ и для всех $w \in \Sigma^* \, (q,aw) \vdash (q',w)$. Рефлексивное и транзитивное замыкание отношения $\vdash$ обозначим $\vdash^*$. Таким образом, автомат принимает слово, если существует такая цепочка конфигураций \[(q_0, w_1w[2,n]) \vdash (q'_1, w[2,n]), (q'_1, w_2w[3,n]) \vdash (q'_2, w[3,n]),\ldots, (q'_{n-1},w_n) \vdash (q'_n,\eps), \]
	что $q'_n \in F$. Или в терминах транзитивного замыкания $\exists q'_n: (q_0, w) \vdash^* (q'_n, \eps)$.

	Множество всех слов, принимаемых автоматом $\A$ будем обозначать $L(\A)$. Автомат $\A$  \emph{принимает} язык $L$, если $\forall w \in L : w \in L(\A)  $, другими словами $L \subseteq L(\A)$. Если при этом, $L(\A) \subseteq L$, то будем говорить, что автомат $\A$ \emph{распознаёт} язык $L$. Здесь есть тонкая лингвистическая разница,  слова ``принимает''\  и ``распознаёт'', конечно схожи, но за ними стоят разные определения. 

\section{О решении задач}

	Я хочу отметить, что под \emph{решением задачи} понимается не получение конечного ответа без пояснений, а последовательность \emph{обоснованных} действий, приводящих к правильному ответу. Все действия и построения должны быть обоснованны \emph{всегда}. Часто я буду акцентировать в условии внимание на том, что именно нужно доказать, но это не означает, что если в задаче нет фразы в духе «доказать, что A = B», то можно писать не подкреплённый доводами поток сознания.
	
	
	Не обязательно решить все задачи, поэтому если не получается что-то решить самостоятельно, не надо это судорожно списывать. Лучше решить то, что получается. Не страшно не решить -- страшно попасться на списывании. Я буду кластеризовать работы по глупостям. Это не означает, что задачи нельзя обсуждать друг с другом. Если кто-то рассказал вам идею решения и вы думаете, что её поняли и решили записать, то укажите ссылку на автора идеи.

	\section{Задачи предбазового уровня}

	\prp 

	\prsub $\{a, aa\}\cdot\{b,bb\} = ?$

	\prsub $\{a, aa\}+\{b,bb\} = ?$

	\prsub $\{a, aa\}\times\{b,bb\} = ?$

	\prsub $ ((aa|b)^*(a|bb)^*)^* = ? $

	\prsub 
	$\{ a^{3n} | \, n>0\} \cap \{ a^{5n+1} | n \geq 0\}^* =?$

	\prsub  $\emptyset \cap \{\eps\} =?$


	\section{Задачи базового уровня}

Если в задаче явно не указан алфавит, но в тексте упомянуты символы $a, b$ ($0,1$), то алфавит в этой задаче состоит из символов $a,b$ ($0,1$).

	\prp Записать регулярное выражение для языка $L =\Sigma^*\setminus{\{ (a|b)^*ab(a|b)^* \}}$. Доказать, что язык порождённый регулярным выражением совпадает с $L$.
	
	\medskip
	

	\prp\\
	\begin{multicols}{2}

	\centerline{Автомат $\A:$}
	\vspace{10pt}

		\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) [above right = of q_0] {$q_1$};
		  \node[state]          (q_2) [below right =of q_1] {$q_2$};
		 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
		  \path[->] 
			(q_0)	edge	[loop below]	node	{0}	()
					edge	[bend left] 	node	{1}	(q_1)
		 	(q_1)	edge	[bend left]		node	{1} (q_0)
					edge	[bend left]		node	{0}	(q_2)
			(q_2)	edge	[bend left]		node	{0}	(q_1)
					edge	[loop below]	node	{1}	();
		\end{tikzpicture}

	\centerline{Автомат $\B:$}
	\vspace{10pt}

		\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) [above right = of q_0] {$q_1$};
		  \node[state]          (q_2) [below right =of q_1] {$q_2$};
		 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
		  \path[->] 
			(q_0)	edge	[loop below]	node	{0}	()
					edge	[bend left] 	node	{1}	(q_1)
		 	(q_1)	edge	[bend left]		node	{0} (q_0)
					edge	[bend left]		node	{0}	(q_2)
			(q_2)	edge	[bend left]		node	{0}	(q_1)
					edge	[loop below]	node	{1}	();
		\end{tikzpicture}

	\end{multicols}

	Для каждого автомата ответьте на следующие вопросы (1-2):

	\prsub Автомат задан через граф переходов. Запишите определение автомата в виде $(Q, \Sigma, \delta, q_0, F)$. Опишите элементы каждого множества 

	\prsub Явлется ли автомат детерминированным?

	\prsub Опишите последовательность конфигураций автомата $\A$ при обработке слова $w = 1101010$. Верно ли, что $w \in L(\A)$?

	\prsub Принимает ли автомат $\B$ слово $v = 10001$?

	\prsub Укажите по одному слову, принадлежащему $L(\A)$, $L(\B)$ и по одному слову, не принадлежащее $L(\A)$, $L(\B)$. Все $4$ слова должны быть различными. 



	\prp
	
	Определим язык $L\subseteq \{a,b\}^*$ индуктивными правилами:\\
	({\em 1}) $\eps \in L$;\\ ({\em 2}) вместе с любым словом $x \in L$ в $L$ также 
	входят слова $xa, xaa, xabba$;\\ ({\em 3}) никаких других слов в $L$ нет.

	В язык $T\subseteq \{a,b\}^*$ входит пустое слово $\eps$ и ВСЕ 
	начинающиеся и заканчивающиеся буквой $a$ слова, в которых нет подслов
	``$aba$'' или ``$bbb$''. 
	Докажите или опровергните, что $L=T$. 
	

	\prsub Докажите или опровергните, что $L=T$. 
	{ Если равенство неверно, то нужно явно указать слово, принадлежащее
	одному языку и не принадлежащее другому. Если равенство верно, то нужно провести
	доказательство ПО ИНДУКЦИИ:\\ 1) $L\subseteq T$;\\
	2) $T\subseteq L$. }

	\prsub Постройте конечный автомат, распознающий $T$. Докажите (по индукции), что построенный автомат распознаёт язык $T$.

\section{Благодарности}

	Я хотел бы поблагодарить Сергея Тарасова за предоставление своих материалов и задач, часть из которых я использовал при подготовке этих заданий. Также я хочу поблагодарить Дмитрия Гончара за исправление опечаток и рекомендации по правке предыдущей версии этого задания.

\end{document}
