\documentclass[12pt]{extreport}
\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\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}}

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%% Enumerations %%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

%%%%%%%%%%%%%%%%%%%%% EOF Enumerations %%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}
\definecolor{Gray333}{HTML}{333333}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{kvproblem}
\newcounter{subproblem}
\newcounter{subrproblem}
\newcounter{prvar}


%\usepackage{xkeyval}

%\define@key{myupr}{label}{}
%\def\myupr[#1]#2{
%	\setkeys{myupr}{#1}
%	#
%}

\usepackage{pgfkeys}


\newcommand\tstkeys[3][]{%
  #2 \pgfkeys{/tstkeys,label,#1,print} #3 11%
}
\pgfkeys{
 /tstkeys/.is family, /tstkeys,
 label/.default = {},
 label/.store in = \tstlabel,
% mandatory/.default = {(invalid)},
% mandatory/.store in = \tstkeysmandatory,
 print/.code = {{\medskip\noindent\refstepcounter{uproblem}\label{\tstlabel}{\bf Упражнение \theuproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}{\smallskip} },
}



\newcommand\prtemplate[2][]{%
 \pgfkeys{/prtemplate,name,counter,label,type,#1,print}\ifthenelse{\equal{#2}{}}{}{#2 }% 
}
\pgfkeys{
 /prtemplate/.is family, /prtemplate,
 name/.default = {},
 name/.store in = \prname,
 label/.default = {},
 label/.store in = \prlabel,
 counter/.default = {problem},
 counter/.store in = \prcounter,
 type/.default={},
 type/.store in=\prtype,
 print/.code =  {\medskip\noindent\ifthenelse{\equal{\prlabel}{}}{\stepcounter{\prcounter}}{\refstepcounter{\prcounter}\label{\prlabel}}{\bf \ifthenelse{\equal{\prname}{}}{}{\prname~}\prwrite[\prtype]\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
}

\newcommand{\prwrite}[1][]{\ifthenelse{\equal{#1}{star}}{$\mathbf{\arabic{\prcounter}}^{*}$\!\!.}
	{\textbf{\arabic{\prcounter}.}}}

%\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;
\newcommand\prsubrtemplate[2][]{%
 \pgfkeys{/prsubrtemplate,label,display,type,#1,print}\ifthenelse{\equal{#2}{}}{}{#2 }% 
}
\pgfkeys{
 /prsubrtemplate/.is family, /prsubrtemplate,
 label/.default = {},
 label/.store in = \prlabel,
 display/.default={},
 display/.store in=\prdisplay,
 type/.default={},
 type/.store in=\prstype,
 print/.code =  {\ifthenelse{\equal{\prdisplay}{inline}}{}{\medskip\noindent}\ifthenelse{\equal{\prlabel}{}}{\stepcounter{subrproblem}}{\refstepcounter{subrproblem}\label{\prlabel}}{\bf \prsubrwrite[\prstype]\;}}
}
\newcommand{\prsubrwrite}[1][]{\ifthenelse{\equal{#1}{star}}{{\bf \asbuk{subrproblem}$^{*}$\!)}}
	{\ifthenelse{\equal{#1}{o}}{{\bf \asbuk{subrproblem}$^{\circ}$\!)}}
		{\textbf{\asbuk{subrproblem})}}}}

\newcommand\prsubr[1][]{\prsubrtemplate[#1]{}}
\newcommand\prsubru[1][]{\prsubrtemplate[#1,type=o]{}}
\newcommand\prsubrinline[1][]{\prsubrtemplate[#1,display=inline]{}}
\newcommand\prsubruinline[1][]{\prsubrtemplate[#1,type=o,display=inline]{}}



%\pgfkeys{/line cap/.is choice}
%\pgfkeys{/line cap/round/.style={\pgfsetbuttcap}}

\newenvironment{quiz}[1][]{\prtemplate[name={Контрольный вопрос}, counter={kvproblem}, #1]{}}{\medskip}
\newenvironment{upr}[1][]{\prtemplate[name={Упражнение}, counter={uproblem}, #1]{}}{\medskip}
%\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
%\newcommand\pr[1][]{\prtemplate[#1]}
\newcommand\pr[1][]{\prtemplate[#1]{}}

		%\medskip\noindent\stepcounter{kvproblem}{\bf Контрольный вопрос \thekvproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
%			








\def\prinline{\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}

\def\pru{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
\def\pruinline{\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}

\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
\def\prpfrom[#1]{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

\def\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;$\langle${\rm\Rnum{\theprvar}}$\rangle$.}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}.\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

%\newenvironment{upr}
%	{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}{\smallskip}

%\newenvironment{quiz}
%		{\medskip\noindent\stepcounter{kvproblem}{\bf Контрольный вопрос \thekvproblem.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}{\smallskip}

	
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{\sf \thesubproblem .}\;}
%\def\prsubr{\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;}
%\def\prsubru{\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem}$^\circ$\!)}\;}
%\def\prsubrinline{\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;}
%\def\prsubruinline{\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem}$^\circ$\!)}\;}
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{$\mathsf{\thesubproblem}^*$\negthickspace.}\;}

\def\prsubrstar{\medskip\noindent\stepcounter{subrproblem}{$\text{\bf \asbuk{subrproblem}}^*\text{\textbf{)}}\mathbf{}$}\;}
\def\prsubrstarinline{\noindent\stepcounter{subrproblem}{$\text{\bf \asbuk{subrproblem}}^*\text{\textbf{)}}\mathbf{}$}\;}


\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}\setcounter{subrproblem}{0}
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0}\setcounter{subrproblem}{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}\setcounter{subrproblem}{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{\Pr}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{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{\Prstar}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
		\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf$\mathbf{\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}\setcounter{subrproblem}{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}\setcounter{subrproblem}{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
}


\def\prskip{
	\medskip
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%\usepackage{erewhon}
%\usepackage{heuristica}
%\usepackage{gentium}

\usepackage[portrait, top=3cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\lhead{\fontfamily{fca}\selectfont {ТРЯП 2018} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
\rhead{\fontfamily{fca}\selectfont Домашнее задание 6}
%\rhead{\small 01.09.2016}
\cfoot{}

\usepackage{titlesec}
\titleformat{\section}[block]{\Large\bfseries\filcenter {\setcounter{problem}{0}}  }{}{1em}{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Обозначения и операции %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                                                                    
\newcommand{\divisible}{\mathop{\raisebox{-2pt}{\vdots}}}           
\let\Om\Omega


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Shen Macroses %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\w}[1]{{\hbox{\texttt{#1}}}}
 
\def\PAL{\mathsf{PAL}}

\begin{document}

Теория к домашним заданию по теме <<регулярные языки и конечные автоматы>>  приведена в книжке~\url{http://rubtsov.su/public/books/zz-a5-online.pdf}. Там же приведены используемые здесь обозначения.
Ответьте на контрольные вопросы из разделов 5.4-6 и проверьте себя, сверившись с ответами! Сдавать решение контрольных вопросов не нужно. В случае, если задача в ДЗ помечена символом $\circ$, её решение приведено в книжке. Попробуйте сначала решить эту задачу сами, потом сверьтесь с решеним; сдавать решение этой задачи на проверку не нужно.

	
Во всех задачах данного листка, кроме \textbf{№3}, языки определены над алфавитом $\Sigma = \{a,b\}$. %РВ~"--- сокращение для регулярного выражения.

%\textbf{Все ответы должны быть обоснованы, если не указано противное! (Ответы без обоснований не считаются решениями.)}
 

\pr Пусть~$\A$~"--- полный ДКА, распознающий язык $L$.	Докажите, что 
	
	\prsubr каждый левый язык $L_q$ является подмножеством некоторого класса $L$-эквивалентности: $x \in L_q \Rightarrow L_q \subseteq [x]$.
	
	\prsubr для каждого класса эквивалентности $[x]$ существует такое подмножество состояний $Q_x \subseteq Q_\A$, что $$ [x] = \bigcup\limits_{q\in Q_x} L_q. $$
	
	\prsubr если $x\in L_q$, то  $L_p \subseteq [x]$ тогда и только тогда, когда $R_q = R_p $ (когда правые языки для состояний $p$ и $q$ совпадают).

\prend

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

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

\Pr[null][к.д.з. №6 (1,2)] Является ли регулярным язык~$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$.

\prend

% Пусть $w = w_1w_2\ldots w_n, w_i \in \Sigma$, тогда $w^R = w_nw_{n-1}\ldots w_1$. Обозначим $L^R = \{ w^R \mid w \in L \}$ -- \emph{обращение} языка $L$.
 %\medskip


\pr Опишите классы эквивалентности Майхилла-Нероуда для языка $L$. В случае конечности множества классов, постройте минимальный полный ДКА, распознающий $L$.\\
$L = $\quad \prsubrinline $SQ=\{ww \mid w \in \Sigma^* \}$;\qquad \prsubrinline $\Sigma^*ab\Sigma^*$.

\prend

%\pr Являются ли регулярными следующие языки:

%\prsubr $\{ xy : |x| > |y|, \text{ $x$ содержит букву $a$ }  \}$;\quad \prsubrinline $\{ xy : |x| < |y|, \text{ $x$ содержит букву $b$ }  \}$?

%\prend

\pr Автомат $\A$ заданн диаграммой: 
\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, 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}
\end{center} 

\prsub Постройте праволинейную грамматику для языка $L(\A)$.

\prsub Постройте регулярное выражение для языка $L(\A)$.

\prend

\prstar Обозначим через $R(\A)$ автомат для языка $L^R(\A)$ (обращения $L(\A)$), построенный по алгоритму с семинара.  Через $D(\A)$ обозначим ДКА, полученный детерминизацией из НКА $\A$.  Пусть $\A$~"--- полный ДКА. Докажите. что тогда $D(R(D(R(\A))))$~"--- минимальный ДКА. То есть двукратное последовательное выполнение процедур обращения и детерминизации для полного ДКА приводит его к минимальному.

\end{document}
  