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


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

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

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


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


\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\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\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;({\rm\Rnum{\theprvar}}).  }\setcounter{subproblem}{0} }
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}. \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}{\sf \thesubproblem .} }
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\sf \thesubproblem)} }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{$\mathsf{\thesubproblem^*}$\negthickspace.  } }
\def\prsubrstar{\medskip\noindent\stepcounter{subproblem}{\sf $\mathsf{\thesubproblem^*}$)  } }

\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} 
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{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}
	\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{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{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}
	\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
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Eof Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

	\medskip

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

\begin{center}
	{\Large Автоматы и распознавание текстов II	    	
			
			%\vspace{0.5ex}
			                         
		Лемма о накачке 
				
		}
\end{center}

	\bigskip

	


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

	\section{Алгоритм Ахо-Корасик}

	Алгоритм Ахо-Корасик позволяет проверять вхождение в текст~$t$ слов из заранее построенного словаря. Причём, алгоритм находит все вхождения за линейное время! 

	\begin{figure}[h]

	\begin{center}
		\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]%, every state/.style={inner sep=3pt,minimum size=0pt}
		  %\draw[help lines] (0,0) grid (3,2);
		  \node[state,initial]  (eps)                      {$\eps$};
		  \node[state, accepting]          (a) [below right = of eps] {$a$};
		  \node[state]          (b) [above right =of eps] {$b$};
		  \node[state, accepting]          (ba) [right =of b] {$ba$};
		  \node[state, accepting]          (ab) [above right = 2cm of a] {$ab$};
		  \node[state, accepting]          (abb) [right = 3cm of ab] {$abb$};
	      \node[state, accepting, black!60]          (aba) [below = of abb] {$aba$};
		  \node[state, accepting]          (abab) [right = 3cm of aba] {$abab$};
		 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
		  \path[->]                                         
			%%% dashed
			(b)		edge [bend right=60, dashed] node {} (eps)	
			(ba)	edge [bend right, dashed] node {} (a)	    
			(a)		edge [bend left=60, dashed] node {} (eps)  
			(ab)	edge [dashed] node {} (b)    
			(abb)	edge [bend right=60, dashed] node {} (b)
			(aba)	edge [bend right=100, dashed] node {} (ba)
			(abab)	edge [bend left=60, dashed] node {} (ab)
			%%%%% normal
			(eps)	edge      node	{$a$}	(a)
				 	edge	  node	{$b$}	(b)
			(a)		edge      node	{$b$}	(ab)		
			(b)		edge      node	{$a$}	(ba)
			(ab) 	edge      node	{$a$}	(aba)     
			     	edge	  node	{$b$}	(abb)
			(aba) 	edge      node	{$b$}	(abab);     				  		
		\end{tikzpicture}
		\begin{comment}
			\node[state with output]          (a) [below right = of eps] {$a$ \nodepart{lower} $A_1$};
		  	\node[state with output]          (b) [above right =of eps] {$b$ \nodepart{lower} $A_4$};
		  	\node[state with output]          (ba) [right =of b] {$ba$  \nodepart{lower} $A_5$};
		  	\node[state with output]          (ab) [above right = 2cm of a] {$ab$  \nodepart{lower} $A_2$};
		  	\node[state with output]          (abb) [right = 3cm of ab] {$abb$  \nodepart{lower} $A_3$};
	      	\node[state with output]          (aba) [below = of abb] {$aba$  \nodepart{lower} $A_6$};
		   	\node[state with output]          (abab) [right = 3cm of aba] {$abab$  \nodepart{lower} $A_7$};
		\end{comment}
	\end{center}
		\caption{Автомат Ахо-Корасик}\label{ACautomata}
	\end{figure}      

	Автомат для алгоритма Ахо-Корасик (рис.~\ref{ACautomata}) построен следующим образом. Он содержит все состояния и переходы, что и соответсвующий автомат для словаря (рис.~1 в задании 3), но помимо этого к принимающим состояниям относятся те состояния, некоторый суффикс которых является принимающим: состояние $aba$ выделено серым, поскольку слово $aba$ не лежит в словаре, однако в словаре лежит слово $ba$. Пунктирные переходы используются в случае сбоя: переход из состояния $u$ (состояние = некоторое слово) по пунктирной линии осуществляется в случае сбоя: если из $u$ нет перехода по $a$, то автомат переходит в состояние $s$, в которое ведёт пунктирная стрелка, и пытается перейти по $a$ из $s$ и т.д. Переход из $u$ в $s$ добавляется согласно следующему правилу. Слово $s$ должно быть самым длинным суффиксом слова $u$ ($u = ps$), который является состоянием автомата Ахо-Корасик. Такие переходы называют \emph{суффиксными ссылками}.
	% Пусть $u = ps$, где $s$ -- самый длинный суффикс, который является состоянием автомата Ахо-Корасик. Тогда переход по пунктирной линии из состояния $u$ ведёт в состояние $s$. Такие переходы называют \emph{суффиксными ссылками}.

	\begin{figure}[h]

	\begin{center}
		\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,initial text=]%, every state/.style={inner sep=3pt,minimum size=0pt}
		  %\draw[help lines] (0,0) grid (3,2);
		  \node[state,initial]  (eps)                      {$\eps$};
		  \node[state, accepting]          (a) [below right = of eps] {$a$};
		  \node[state]          (b) [above right =of eps] {$b$};
		  \node[state, accepting]          (ba) [right =of b] {$ba$};
		  \node[state, accepting]          (ab) [above right = 2cm of a] {$ab$};
		  \node[state, accepting]          (abb) [right = 3cm of ab] {$abb$};
	      \node[state, accepting, black!60]          (aba) [below = of abb] {$aba$};
		  \node[state, accepting]          (abab) [right = 3cm of aba] {$abab$};
		 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
		  \path[->]                                         
			%%% added
			(b)		edge [loop above, gray] node {$b$} (b)	
			(ba)	edge [gray, bend right, anchor=-1] node {$a$} (a)	    
			(ba)	edge [gray, pos=0.05] node {$b$} (ab)	    
	 		(a)		edge [loop below, gray] node {$a$} (a)  
			(abb)	edge [gray, bend right=60,anchor=-100] node {$b$} (b) 
			(abb)	edge [gray,anchor=-100] node {$a$} (ba)    
	%		(abb)	edge [bend right=60, dashed] node {} (b)
			(aba)	edge [gray] node {$a$} (a)
			(abab)	edge [gray, bend left] node {$a$} (aba)
			(abab)	edge [gray,anchor=-100] node {$b$} (abb)
			%%%%% normal
			(eps)	edge      node	{$a$}	(a)
				 	edge	  node	{$b$}	(b)
			(a)		edge      node	{$b$}	(ab)		
			(b)		edge      node	{$a$}	(ba)
			(ab) 	edge      node	{$a$}	(aba)     
			     	edge	  node	{$b$}	(abb)
			(aba) 	edge      node	{$b$}	(abab);     				  		
		\end{tikzpicture}	
	\end{center}
		\caption{ДКА Ахо-Корасик}\label{DFACautomata}
	\end{figure}



	Так, автомат Ахо-Корасик (рис.~\ref{ACautomata}) по сути является ДКА (рис.~\ref{DFACautomata}), граф которого получается из автомата Ахо-Корасик добавлением явных переходов, которые были заданы суффиксными ссылками.  ДКА (и соответсвенно автомат Ахо-Корасик) оказывается в принимающем состоянии тогда и только тогда, когда в тексте на входе автомата встретилось слово из словаря (возможно несколько одновременно). Заметим, что количество одновременно встретившихся подслов текста из словаря зависит только от состояния автомата.

	Непосредственное построение ДКА~Ахо-Корасик как правило неэффективно для приложений  -- суффиксные ссылки позволяют существенно сократить таблицу переходов и уменьшить тем самым длину описания автомата.

	\prp Постройте для словаря $S = \{ac, acb, b, ba, c, cbb\}$ (который вы строили в предыдущем задании) автомат Ахо-Корасик. Посчитайте с его помощью количество различных вхождений слов из словаря~$S$ в подслово $acbacbb$.	


\section{Лемма о накачке\footnote{Также известна как лемма о разрастании. Неудачные переводы неудачного термина «Pumping Lemma».}}

	В данном разделе мы поговорим о лемме о накачке -- одном из способов доказательства нерегулярности языка.

	\begin{Lemma}
		Для любого регулярного языка $L$ существует такая константа $p \geq 1$, что  для любого слова $w$ из $L$ длиннее $p$, существует разбиение $w = xyz$, такое что
		\begin{itemize}
			\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$ идёт квантор существования: часто студенты это равенство ошибочно воспринимают как <<для любого разбиения>>.


	\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}
	
	\begin{Remark}
		Для доказательства того, что некоторый язык является нерегулярным, при использовании леммы о накачке необходимо предъявить не одно конкретное слово, а последовательность слов, зависящих от $p$ (константы леммы). Если вы предъявите всего одно слово, то кто-то очень умный сможет просто взять б\'{о}льшую константу.
	\end{Remark}
	
\upr В предыдущем примере показано громоздкое доказательство: его можно сделать проще, убрав перебор случаев, воспользовавшись структурой слова. Постарайтесь получить доказательство в одну строчку или восстановить доказательство с семинара.

\bigskip

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

\prp Будут ли регулярными следующие языки?

\medskip

 \prsub  $L = \{ a^{2017n+5}\mid n=0,1, \} \cap \{ a^{503k+29}\mid k=401,402,\ldots \}  \subseteq  \{ a^* \}$.

\medskip

 \prsub  $L_2 = \{ a^{200n^2+1}\mid n=1000,1001,\ldots \}  \subseteq  \{ a^* \}$.

\medskip

\prsub Язык $L_3 = \{ w \mid |w|_a = |w|_b \}$; через $|w|_a$ обозначают количество букв $a$ в слове $w$.

%\prsub  Язык $L_3$ всех слов в алфавите  $\{ 0, 1 \}$, которые представляют числа в двоичной записи, дающие остаток два при делении на три (слово читается со старших разрядов). Например, $001010\, (1010_2=10_{10} = 3 \times 3+1)  \not\in  L_3$,
%а $10001\, (10001_{2}=17_{10} = 5 \times  3+2)  \in  L_3 $.

\medskip

\prsub Язык $L_3 = \{ w \mid |w|_{ab} = |w|_{ba} \}$, через $|w|_{ab}$ обозначают количество подслов $ab$ в слове $w$.

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


		


\end{document}
