chapter-2.tex

\chapter{Регулярные языки}
\label{Chapter2}
\section{Регулярные множества и регулярные выражения}
\label{Chapter2RegExprs}

Пусть $\Sigma$ --- конечный алфавит. \mydef{Регулярное множество} над алфавитом
$\Sigma$ определяется рекурсивно следующим образом: множества $\es$,
$\{\eps\}$ и $\{a\}$ для каждого $a$ из $\Sigma$ --- регулярные; если $P$
и $Q$ --- регулярные множества, то таковы же и множества $P\cup Q$,
$PQ$, $P^*$; ничто другое не является регулярным множеством. Другими
словами, множество регулярно над алфавитом $\Sigma$ тогда и только
тогда, когда оно либо $\es$, либо $\{\eps\}$, либо $\{a\}$ для
некоторого $a\in\Sigma$. либо его можно получить из этих множеств
применением конечного числа операций объединения, конкатенации и
итерации.

Регулярное множество над алфавитом $\Sigma$ иначе называется регулярным языком над этим алфавитом

Для обозначения регулярных множеств используют регулярные выражения.
Регулярные выражения над алфавитом $\Sigma$ и регулярные множества,
которые они обозначают, определяются рекурсивно следующим образом:
$\es$ --- регулярное выражение, обозначающее регулярное множество
$\es$; $\eps$ --- регулярное выражение, обозначающее регулярное
множество $\{\eps\}$ если $a\in\Sigma$, то $a$ --- регулярное
выражение, обозначающее регулярное множество $\{a\}$; если $p$ и $q$ ---
регулярные выражения, обозначающие регулярные множества $P$ и $Q$
соответственно, то $(p+q)$, $(pq)$ и $(p)^*$ --- регулярные выражения,
обозначающие $P\cup Q$, $PQ$ и $p^*$ соответственно; ничто другое не
является регулярным выражением.

Для сокращения будем далее вместо $pp^*$ писать $p^+$ и устранять из регулярных выражений лишние скобки там, где это не приводит к недоразумениям. При этом будем предполагать, что наивысшим приоритетом обладает итерация, затем конкатенация и, наконец, операция $+$. Например, вместо $(01(1^*))+(1(0^*)))$ будем писать $01^++10^*$.

\begin{myexample}
Приведем несколько регулярных выражений и соответствующих им множеств:
\begin{enumerate}
	\item $(0+1)^*$ обозначает $\{0;1\}^*$;
	\item $(0+1)^*0101$ обозначает множество всех слов над алфавитом $\{0;1\}$ с суффиксом $0101$;
	\item $(a+b+c+d)(a+b+c+d+0+1)^*$ обозначает множество всех слов над алфавитом $\{0;1;a;b;c;d\}$ с префиксами $a, b, c$ или $d$;
	\item $(00+11)^*((01+10)(00+11)^*(01+10)(01+11)^*)^* $обозначает множество всех слов над алфавитом $\{0;1\},$ содержащих четное число нулей и четное число единиц.
\end{enumerate}

Последний пример представляется весьма поучительным, и хотелось бы порекомендовать читателю поразмышлять над ним до тех пор, пока он не станет «очевидным».
\end{myexample}

Для каждого регулярного множества можно найти по крайней мере одно регулярное выражение, которое его обозначает. Обратно, для каждого регулярного выражения можно построить регулярное множество, обозначаемое этим выражением. Но для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений. Будем говорить, что два регулярных выражения равны $(=)$, если они обозначают одно и то же множество.

\begin{mylemma}
\label{LemmaRegExprFeat}
Пусть $\alpha$, $\beta$, $\gamma$ --- регулярные выражения. Тогда
\begin{multicols}{2}
\begin{enumerate}
	\item $\alpha+\es=\alpha$,
	\item $\alpha+\alpha=\alpha$,
	\item $\alpha+\beta=\beta+\alpha$,
	\item $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$,
	\item $\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma$,
	\item $(\alpha+\beta)\gamma=\alpha\gamma+\beta\gamma$,
	\item $\alpha\eps=\eps\alpha=\alpha$,
	\item $\es\alpha=\alpha\es=\es$,
	\item $\alpha(\beta\gamma)=(\alpha\beta)\gamma$,
	\item $\es^*=\eps$,
	\item $(\alpha^*)^*=\alpha^*$,
	\item $\alpha^*=\alpha+\alpha^*$,
	\item $(\alpha+\beta)^*=(\alpha^*\beta^*)^*$,
	\item $\alpha\alpha^*+\eps=\alpha^*$.
\end{enumerate}
\end{multicols}
\end{mylemma}

\begin{myproof}
Каждое из равенств легко проверить, используя свойства множеств и приведенные выше определения. Рассмотрим, для примера, лишь некоторые из приведенных равенств.

Равенство 4). Пусть $\alpha$, $\beta$ и $\gamma$ --- регулярные выражения, обозначающие регулярные множества $A$, $B$ и $\Gamma$ соответственно. Тогда $\beta+\gamma$ обозначает $B \cup \Gamma$, а $\alpha+(\beta+\gamma)$ обозначает $A \cup (B \cup \Gamma)$; аналогично, $(\alpha+\beta)+\gamma$ обозначает $(A \cup B)\cup\Gamma$. Но $A \cup (B \cup \Gamma) = (A \cup B) \cup \Gamma$, поэтому $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$.

Равенство 12). Пусть $\alpha$ --- регулярное выражение, обозначающее регулярное множество $A$. Ясно, что множество $A^*= \bigcup_{n\ge 0}A^n$ содержит $A$, поэтому $A^*\cup A=A^*$ и, следовательно, $\alpha^*+\alpha=\alpha^*$.
\end{myproof}

\begin{myproblem}
Приведите доказательства всех равенств из леммы~\ref{LemmaRegExprFeat} Постарайтесь обнаружить новые равенства и доказать их (см. \cite{Sal}).
\end{myproblem}

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

\section{Уравнения и системы уравнений с регулярными коэффициентами}
\label{Chapter2Systems}

Рассмотрим уравнение
\begin{equation}\label{lin-reg-eq}
    X=\alpha X+\beta,
\end{equation}
где $\alpha$ и $\beta$ --- регулярные выражения над некоторым
алфавитом $\Sigma$. Прямой подстановкой проверим, что
$X=\alpha^*\beta$~--- решение уравнения~\eqref{lin-reg-eq}:
%TODO вот такой вот "список" здесь, лучшее что я придумал это так:

(?)	$\quad \alpha^*\beta=\alpha(\alpha^*\beta)+\beta,$

(?) $\quad \alpha^*\beta=(\alpha\alpha^*)\beta+\eps\beta,$

(?)	$\quad \alpha^*\beta=(\alpha\alpha^*+\eps)\beta,$

(!)	$\quad \alpha^*\beta=\alpha^*\beta.$

Решение уравнения с регулярными коэффициентами может быть не единственным. Например, если в уравнении~\eqref{lin-reg-eq} потребовать, чтобы $\eps\in\alpha$, то
\[
    X=\alpha^*(\beta\cup L)
\]
будет решением этого уравнения для любого (не обязательно регулярного) языка $L$. Действительно,

(?) $\quad \alpha^*(\beta\cup L)=\alpha(\alpha^*(\beta\cup L))\cup\beta,$

(?)	$\quad \alpha^*(\beta\cup L)=(\alpha\alpha^*)(\beta\cup L))\cup\beta,$

(?)	$\quad \alpha^*(\beta\cup L)=\alpha^*(\beta\cup L)\cup\beta,$

(!)	$\quad \alpha^*(\beta\cup L)=\alpha^*(\beta\cup L).$

Таким образом, уравнение~\eqref{lin-reg-eq} при $\eps \in \alpha$
% TODO: подумать. Написано, вроде, \eps \in \alpha, но
% кажется, что это неверно.
имеет бесконечно много решений.

В теории формальных языков представляет интерес, главным образом, наименьшее решение, которое называют наименьшей неподвижной точкой. (В математике решение уравнения вида $x=f(x)$ принято называть неподвижной точкой отображения $f$, поэтому термин <<неподвижная точка>> используется и здесь~\cite{Bau}.)

\begin{mytheorem}
\label{Theorem-NNT-EQ}
Пусть $\alpha$ и $\beta$ --- регулярные выражения над алфавитом $\Sigma$ и $X\notin\Sigma$. Рассмотрим уравнение~\eqref{lin-reg-eq}. Тогда
\begin{enumerate}
    \item $X=\alpha^*\beta$ --- наименьшая неподвижная точка уравнения;

    \item если $\eps\notin\alpha$, то $X=\alpha^*\beta$ --- единственное
    решение уравнения;

    \item если $\eps\in\alpha$, то для произвольного (не обязательно
    регулярного) языка $L$ язык $\alpha^*(\beta\cup L)$ является
    решением уравнения, и наоборот, всякое решение уравнения
    может быть записано в таком виде.
\end{enumerate}
\end{mytheorem}

\begin{myproof}
\hfill \break
1) Ранее мы проверили, что $X=\alpha^*\beta$ --- решение уравнения~\eqref{lin-reg-eq}. Пусть $\Omega$ --- произвольное решение этого уравнения; покажем, что $\alpha^*\beta\subset\Omega$. Предположим, что $\omega\in\alpha^*\beta$. Тогда $\omega=\omega_k\omega_{k-1}\ldots\omega_1b$, где $\omega_i\in\alpha$, $b\in\beta$. Из того, что $\Omega$ --- решение уравнения~\eqref{lin-reg-eq}, вытекает, что
\[
	\Omega = \alpha\Omega + \beta
\]
и, следовательно, $\beta\subset\Omega$, $\alpha\Omega\subset\Omega.$ Тогда
\[
b\in\Omega, \omega_1b\in\Omega, \omega_2\omega_1b\in\Omega, \ldots , \omega_k\omega_{k-1}\ldots\omega_1b\in\Omega.
\]
Таким образом, $\alpha^*\beta\subset\Omega$. Это означает, что $X=\alpha^*\beta$ - наименьшая неподвижная точка.

2)	Пусть $\eps\notin\alpha$. Предположим, что $\Omega$ --- произвольное решение уравнения~\eqref{lin-reg-eq}, и покажем, что $\Omega=\alpha^*\beta$. Пусть $\omega=a_1a_2\ldots a_m\in\Omega$ где $a_i\in\Sigma$. Из того, что $\Omega=\alpha\Omega+\beta$, вытекает: либо $\omega\in\beta\subset\alpha^*\beta$, либо $\omega\in\alpha\Omega$. Если $\omega\in\alpha\Omega=\alpha\alpha\Omega+\alpha\beta$, то либо $\omega\in\alpha\beta\subset\alpha^*\beta$, либо $\omega\in\alpha\alpha\Omega$. Продолжим этот процесс до тех пор, пока альтернатива $\omega\in\alpha\alpha\ldots\alpha\Omega$ окажется невозможной (в силу того, что $\omega$ имеет $m$ букв, а $\eps\notin\alpha$, это обязательно произойдет по крайней мере при $k>m$). В итоге получим, что $\omega\in\alpha^*\beta$.

3) Пусть $\eps\in\alpha$. Ранее мы проверили, что множество $\alpha^*(\beta\cup L)$, где $L$ --- произвольный язык, является решением уравнения~\eqref{lin-reg-eq}. Пусть теперь $\Omega$ --- какое-нибудь решение этого уравнения; покажем, что $\Omega$ можно записать в виде $\alpha^*(\beta\cup L)$, где $L$ --- некоторый язык. По условию
\[
\Omega = \alpha\Omega + \beta.
\]
Отсюда вытекает, что
\[
\alpha\Omega \subseteq \Omega, \beta \subseteq \Omega.
\]
С другой стороны, из условия $\eps\in\alpha$ следует, что
\[
\Omega \subseteq \alpha\Omega.
\]
Получаем равенство:
\[
\Omega = \alpha\Omega.
\]
Его непосредственным следствием является равенство:
\[
\Omega = \alpha^*\Omega.
\]
Тогда в силу соотношения $\beta\subseteq\Omega$ получаем:
\[
\Omega = \alpha^*(\Omega \cup \beta),
\]
так как $\Omega=\Omega\cup\beta$. Итак, действительно показано, что если множество $\Omega$ --- решение уравнения~\eqref{lin-reg-eq}, то оно имеет такой вид:
\[
\Omega = \alpha^*(L \cup \beta),
\]
где $L$ --- некоторый язык.
\end{myproof}

Систему уравнений с регулярными коэффициентами над некоторым алфавитом $\Sigma$ назовем стандартной системой со множеством неизвестных
\[
	\Delta = \{ X_1;X_2;\ldots ;X_n \},
\]
если она имеет вид
\begin{equation}
\label{GeneralSysWRegExprK}
\begin{cases}
X_{1} = \alpha_{10} + \alpha_{11}X_1 + \alpha_{12}X_2 + \ldots  + \alpha_{1n}X_n\\
X_{2} = \alpha_{20} + \alpha_{21}X_1 + \alpha_{22}X_2 + \ldots  + \alpha_{2n}X_n\\
\dotfill\\
X_n = \alpha_{n0} + \alpha_{n1}X_1 + \alpha_{n2}X_2 + \ldots  + \alpha_{nn}X_n
\end{cases}
\end{equation}
где $\alpha_{ij}$ --- регулярные выражения над $\Sigma$ и $\Sigma\cap\Delta=\es$.

Коэффициентами уравнений являются регулярные выражения $\alpha_{ij}$. Если $\alpha_{ij}=\es$, то в уравнении для $X_i$ нет компонента, содержащего $X_j$. Аналогично, если $\alpha_{ij}=\eps$, то в уравнении для $X_i$ компонент, содержащий $X_j$, совпадает с $X_j$. Иными словами, $\es$ играет роль коэффициента $0$, а $\eps$ - роль коэффициента $1$ в обычных линейных алгебраических уравнениях.

Пусть $Q$ --- стандартная система уравнения со множеством неизвестных $\Delta$ и с коэффициентами над алфавитом $\Sigma$. Отображение $f$ множества $\Delta$ во множество языков над $\Sigma$ называют решением системы $Q$, если после подстановки $f(X)$ вместо $X(\in\Delta)$ в каждое уравнение системы все уравнения становятся равенствами. Отображение $f\colon \Delta\to P(\Sigma^*)$ называют наименьшей неподвижной точкой системы $Q$, если, во-первых, $f$ --- решение и, во-вторых, $f(X)\subseteq g(X)$ для любого другого решения $g$ и всех $X\in\Delta$.

\begin{mytheorem}
\label{theorem-NNTSysReg}
Пусть $Q$ --- стандартная система уравнений, а $Y_i$ --- множество всех слов $\omega\ldots\omega_m$, где $m\ge 1$ и $\omega_m\in\alpha_{j_m0}$, $\omega_k\in\alpha_{j_kj_{k+1}}$ для некоторой последовательности $j_i=j_1, \ldots , j_m (\in\{1;2;\dots ;n\})$. Отображение $f$ множества $\Delta=\{X_1;X_2;\ldots ;X_n\}$ во множество языков над $\Sigma$ определим равенством: $f(X_i)=Y_i$, где $i\in\{1;2;\ldots ;n\}$. Тогда $f$ --- наименьшая неподвижная точка системы $Q$.
\end{mytheorem}

\begin{myproof}
Путем непосредственной подстановки проверяется, что для всех $i$
\[
f(X_{i}) = \alpha_{i0} \cup \alpha_{i1}f(X_1) \cup \dots \cup \alpha_{in}f(X_n).
\]
Таким образом, $f$ --- решение.

Покажем, что $f$ --- наименьшая неподвижная точка. Пусть $g$ --- какое-нибудь решение системы и $i\in\{1;2;\ldots ;n\}$. Рассмотрим произвольное слово $\omega$ из $f(X_i)$. Тогда $\omega=\omega_1\ldots\omega_m (m\ge 1)$, где для некоторой последовательности чисел $j_1, \ldots , j_m (\in\{1;2;\ldots ;n\}$) выполнены условия:
\[
	\omega_m\in\alpha_{j_m0}, \quad \omega_k\in\alpha_{j_kj_{k+1}}
\]
Так как $g$ - решение, то
\[
	g(X_i) = \alpha_{i0} \cup \alpha_{i1}g(X_{1}) \cup \dots  \cup \alpha_{in}g(X_n).
\]
В частности,
\[
	\alpha_{i0} \subseteq g(X_i), 	\alpha_{ik}g(X_k) \subseteq g(X_i)
\]
для всех $i$ и $k$. Тогда
\begin{align*}
    \omega_m & \in \alpha_{j_m0} \subseteq g(X_{j_m}),\\
    \omega_{m-1}\omega_m & \in \alpha_{j_{m-1}j_m}g(X_{j_m})
        \subseteq g(X_{j_{m-1}}),\\
    &\ldots \\
    \omega=\omega_1\omega_2\ldots\omega_m & \in
        \alpha_{j_1j_2}g(X_{j_2}) \subseteq g(X_{j_1})=g(X_i).
\end{align*}

Таким образом, $f(X_i)\subseteq g(X_i)$. Отсюда следует, что $f$ --- наименьшая неподвижная точка системы $Q$.
\end{myproof}

В этой теореме получено описание наименьшей неподвижной точки стандартной системы с регулярными коэффициентами, но, во-первых, нет гарантий, что наименьшая неподвижная точка является регулярным множеством, и, во"/вторых, неясно, как эту наименьшую неподвижную точку найти. Эти вопросы будут рассмотрены в следующем пункте.

\begin{myproblem}
Проверьте (любым способом), что наименьшая неподвижная точка системы
\begin{equation}
\begin{cases}
X_1 = a_{10} + a_{11}X_1 + a_{12}X_2\\
X_2 = a_{20} + a_{21}X_1 + a_{22}X_2
\end{cases}
\end{equation}
имеет вид
\begin{equation}
\begin{cases}
f(X_1) = (a_{11}+a_{12}a^*_{22}a_{21})^*(a_{10}+a_{12}a^*_{22}a_{20}), \\
f(X_2) = (a_{22}+a_{21}a^*_{11}a_{12})^*(a_{20}+a_{21}a^*_{11}a_{10})
\end{cases}
\end{equation}
\end{myproblem}

\begin{myproblem}
Сформулируйте и докажите аналог теоремы~\ref{Theorem-NNT-EQ} для систем.
\end{myproblem}

\section[Алгоритм решения систем с регулярными коэффициентами]{Алгоритм решения систем уравнений с регулярными коэффициентами}
\label{Chapter2SysSolverAlg}

Рассмотрим стандартную систему уравнений с регулярными коэффициентами вида~\eqref{GeneralSysWRegExprK}.

%Алгоритм 2.3.1.%TODO - определить алгоритм, и как делать вот эти штуки: Вход, Выход, Метод, Шаг 1, и т.д. Страница 20 в методичке

\Algo{Решение систем уравнений с регулярными коэффициентами}%
{\label{Algo-SysEq-Solver} Стандартная система уравнения с регулярными коэффициентами над алфавитом $\Sigma$ и множеством неизвестных $\Delta=\{X_1,\ldots ,X_n\}$.}%
{Решение системы в виде $X_1=\alpha_1,\ldots, X_n=\alpha_n$, где $\alpha_i$ --- регулярные выражения над алфавитом $\Sigma$.}%
{Напоминает обычный метод Гаусса решения систем линейных уравнения и основан на систематическом использовании формулы $X=\alpha^*\beta$ для наименьшей неподвижной точки уравнения~\eqref{lin-reg-eq}.}%
{
    \item Положим $i=1$.
		
    \item Если $i=n$, перейти к шагу 4. В противном случае с помощью тождеств из леммы~\ref{LemmaRegExprFeat} записать уравнение для $X_i$ в виде $X_i=\alpha X_i+\beta$, где $\alpha$ и $\beta$ --- регулярные выражения над $\Sigma$. Затем в правых частях уравнений для $X_{i+1}, \ldots , X_n$ заменить $X_i$ регулярным выражением $\alpha^*\beta$.

    \item Увеличить $i$ на 1 и вернуться к шагу 2.

    \item Записать уравнение для $X_n$ в виде $X_n=\alpha X_n+\beta$ где $\alpha$ и $\beta$ --- регулярные выражения над $\Sigma$. (После выполнения шага 2 для каждого $i$ при $l<n$ в правой части уравнения для $X_i$ не будет неизвестных $X_1, \ldots,X_{i-1}$. В частности, на шаге 4 этим свойством будет обладать и уравнение для $X_n$.) Перейти к шагу 5 (при этом $i=n$).

%    \item Уравнение для $X_i$ имеет вид $X_i=\alpha X_i+\beta$, где $\alpha$ и $\beta$ --- регулярные выражения над $\Sigma$. Записать $X_i=\alpha^*\beta$ и в уравнения для $X_{i-1}, \ldots , X_1$ подставить $\alpha^*\beta$ вместо $X_i$.

%    \item Если $i=1$, то остановиться. В противном случае уменьшить $i$ на 1 и вернуться к шагу 5.
}

\begin{mytheorem}
\label{Theorem-Algo-SysEq-Solver-RegLang}
Алгоритм~\ref{Algo-SysEq-Solver} строит наименьшую неподвижную точку системы уравнений как регулярный язык.
\end{mytheorem}

Доказательству теоремы~\ref{Theorem-Algo-SysEq-Solver-RegLang} предпошлём две леммы.

\begin{mylemma}
\label{RegSysSolver-lemma1}
Пусть $Q_1$ и $Q_2$ --- системы уравнений с регулярными коэффициентами до и после одного применения шага 2 алгоритма~\ref{Algo-SysEq-Solver}. Тогда эти системы имеют одну и ту же наименьшую неподвижную точку.
\end{mylemma}

\begin{myproof}
Отметим, что в ходе работы алгоритма для $1\le l<i$ коэффициент при $A_l$ в уравнении для $A_i$ оказывается равным $\es$. Предположим, что на шаге 2 рассматривается уравнение
\[
A_i = \alpha_{i0} + \alpha{il}A_i + \alpha_{i,i+1}A_{i+1} + \ldots + \alpha_{in}A_n
\]
системы $Q_1$.

В системах $Q_1$ и $Q_2$ уравнения для $A_j$ при $j\le i$ совпадают, а при $j>i$ эти уравнения совпадать не обязаны.

Пусть $j>i$ и
\begin{equation}
\label{eq231}
A_j = \alpha_{j0} + \underset{h=i}{\overset{n}{\sum}} \alpha_{jk}A_h	%(2.3.1)
\end{equation}
это уравнение для $A_j$ в системе $Q_1$. Тогда в силу того, что
\begin{equation*}
	A_i = \alpha^*_{ii}\alpha_{i0} + \underset{h=i+1}{\overset{n}{\sum}} \alpha^*_{ii}\alpha_{ih}A_h,
\end{equation*}
уравнение для $A_j$ в системе $Q_2$ имеет вид
\begin{equation}
\label{eq232}
A_j = (\alpha_{j0}+\alpha_{ji}\alpha^*_{ii}\alpha_{i0}) + \underset{h=i}{\overset{n}{\sum}} (\alpha_{jk}+\alpha_{ji}\alpha*_{ii}\alpha_{ih})A_h.
\end{equation}

Пусть
\begin{equation*}	\beta_{jk}=\alpha_{jh}+\alpha_{ji}\alpha*_{ii}\alpha_{jk} \quad	(k\in\{0;1+1;\ldots ;n\}.
\end{equation*}
Через $f_1$ и $f_2$ обозначим наименьшие неподвижные точки систем $Q_1$ и $Q_2$ соответственно. Далее будем пользоваться тем описанием наименьших неподвижных точек систем, которое дано в теореме~\ref{theorem-NNTSysReg}. В частности, $f_2(A_j)$ --- множество всех слов, представимых в виде $\omega_1\ldots\omega_m$, где $m\ge 1$ и $\omega_m\in\beta_{j_m0}$, $\omega_k\in\beta_{j_{k}j_{k+1}}$ для некоторой последовательности $j_1=j, \dots , j_{m} (\in\{1;2;\ldots ;n\})$.

Сравнение формул~\eqref{eq231} и~\eqref{eq232} показывает, что
\[
	f_2(A_j)\subseteq f_1(A_j).
\]
Действительно, любое слово $x$ из $\alpha_{ji}\alpha^*_{ii}\alpha_{jk}$ можно представить в виде $x_1x_2\ldots x_r$, где $\omega_1\in\alpha_{ji}, \omega_r\in\alpha_{jk}$ и $\omega_2,\ldots ,\omega_{r-1}\in\alpha_{ii}$. Таким образом, слово $\omega$ является конкатенацией слов, каждое из которых принадлежит множеству, обозначаемому некоторым коэффициентом системы $Q_1$, и индексы этих коэффициентов удовлетворяют необходимым условиям.

	Докажем обратное включение
\[
	f_2(A_j)\supseteq f_1(A_j).
\]
Предположим, что $\omega\in f_1(A_j)$. Тогда $\omega=\omega_1\ldots\omega_m$, где для некоторой последовательности ненулевых индексов $l_1=f,\ldots ,l_m$ выполнены условия $\omega_m\in\alpha_{l_m0}$ и $\omega_p\in\alpha_{l_{p}l_{p+1}}$ для $1\le p<m$. Сгруппируем слова $\omega_p$ так, чтобы имело место равенство $\omega=y_1\ldots y_r$, где $y_p=\omega_t\ldots\omega_s$, и
\begin{enumerate}
	\item если $l_t\le i$, то $s=t+1$,
	\item если $l_t>i$, то $s$ таково, что $l_{t+1}=\ldots =l_s=i$, $l_{s+1}\neq i$.
\end{enumerate}
Отсюда следует, что в любом случае $y_p$ --- коэффициент при $A_{j_{s+1}}$ в уравнении для $A_{l_t}$ системы $Q_2$, и, значит, $\omega\in f_2(A_j)$. В итоге получаем, что $f_1(A_j)=f_2(A_j)$ для всех $j$.
\end{myproof}

\begin{mylemma}\label{RegSysSolver-lemma2}
Пусть $Q_1$ и $Q_2$ --- системы уравнений с регулярными коэффициентами до и после одного применения шага 5 алгоритма~\ref{Algo-SysEq-Solver}. Тогда эти системы имеют одну и ту же наименьшую неподвижную точку.
\end{mylemma}

\begin{myproof}
аналогично доказательству леммы~\ref{RegSysSolver-lemma1} и здесь не приводится.
\end{myproof}

\begin{myproof}
теоремы~\ref{Theorem-Algo-SysEq-Solver-RegLang}. После того как шаг 5 алгоритма~\ref{Algo-SysEq-Solver} применен для всех $i$, мы получим новую систему, у которой все уравнения имеют вид $X_i=\alpha_i$, где $\alpha_i$ --- регулярное выражение над алфавитом $\Sigma$. Согласно теореме~\ref{theorem-NNTSysReg} отображение $f$, для которого $f(X_{i})=\alpha_{i}$, является наименьшей неподвижной точкой этой новой системы. В силу лемм~\ref{RegSysSolver-lemma1} и~\ref{RegSysSolver-lemma2} в ходе работы алгоритма наименьшая неподвижная точка не менялась. Таким образом, показано, что алгоритм~\ref{Algo-SysEq-Solver} строит наименьшую неподвижную точку системы уравнений как регулярный язык.
\end{myproof}

\begin{myproblem}
Найдите наименьшую неподвижную точку системы~\eqref{GeneralSysWRegExprK} при условии, что $\alpha_{i0}=\es$ для всех $i$.
\end{myproblem}

\section{Совпадение классов регулярных и ПЛ-языков}
\label{Chapter2MatchRegRL}

\begin{mylemma}
\label{lemma-PL-elem-lang}
Пусть $\Sigma$ --- конечный алфавит. Множества $\es$, $\{\eps\}$ и $\{a\}$ для всех $a\in\Sigma$ являются ПЛ"/языками.
\end{mylemma}

\begin{myproof}
Чтобы доказать лемму, достаточно для каждого из трех множеств построить такую ПЛ-грамматику $G$,  чтобы язык $L(G)$ совпадал с этим множеством:
\begin{enumerate}[itemsep=1ex]
\item $G_\es=(\{S\},\Sigma,\es,S)$ --- ПЛ-грамматика и $L(G_{\es})=\es;$
\item $G_\eps=(\{S\},\Sigma,\{S\to\eps\},S)$ --- ПЛ-грамматика и $L(G_\eps)=\{\eps\};$
\item $G_a=(\{S\}, \Sigma, \{S\to a\},S)$ --- ПЛ-грамматика и $L(G_a)=\{a\}$.
\end{enumerate}
\end{myproof}

\begin{mylemma}
\label{lemma-PL-op-lang}
Пусть $\Sigma$ --- конечный алфавит. Если $L_1$, $L_2$ --- ПЛ-языки над $\Sigma$, то и языки $L_3=L_1\cup L_2$, $L_4=L_1L_2$, $L_5=L^*_1$ тоже являются ПЛ-языками над $\Sigma$.
\end{mylemma}

\begin{myproof}
Пусть $G_1=(N_1,\Sigma,P_1,S_1)$, $G_2=(N_2,\Sigma,P_2,S_2)$ --- такие ПЛ"/грамматики, для которых $L(G_1)=L_1$, $L(G_2)=L_2$. Не теряя общности, будем предполагать, что алфавиты $N_1$ и $N_2$ не пересекаются. Теперь, как и в доказательстве леммы~\ref{lemma-PL-elem-lang}, для каждого из трех новых языков $L_i$ построим такую ПЛ-грамматику $G_i$, чтобы $L(G_i)=L_i$, $i\in\{3;4;5\}$.
\begin{enumerate}
\item Пусть $G_3 = (N_1\cup N_2\cup\{S_3\}$, $\Sigma, P_1\cup P_2\cup\{S_3\to S_1\mid S_2\}$, $S_3)$, где $S_3$ --- новый нетерминальный символ, не принадлежащий ни $N_1$, ни $N_2$. Ясно, что $G_3$ --- ПЛ-грамматика, причем $L(G_3)=L_1\cup L_2$, так как для каждого вывода $S_3\To_{G_3}^+\omega$ существует либо вывод $S_1\To_{G_1}^+\omega$, либо вывод $S_2\To_{G_2}^+\omega$, и обратно. Таким образом, $L_3=L_1\cup L_2$ --- ПЛ-язык.

\item Пусть $G_4=(N_1 \cup N_2 \}, \Sigma, P_4, S_1,)$, а множество продукций $P_4$ определяется так:

\begin{enumerate}[label=(\emph{\roman*})]
	\item если $A,B\in N$, $x\in\Sigma^*$ и $(A\to xB)\in P_1$, то $A\to xB)\in P_4$;
	\item если $A\in N$, $x\in\Sigma^*$ и $(A\to x)\in P_1$, то $(A\to xS_2)\in P_4$;
	\item $P_2\subset P_4$.
\end{enumerate}
Ясно, что $G_4$ --- ПЛ-грамматика. Если $S_1\To_{G_1}^+\omega$, то $S_1\To_{G_4}^+\omega S_2$, а если $S_2\To_{G_2}^+x$, то $S_2\To_{G_4}^+x$. Таким образом, $L(G_1)\cup L(G_2)\subseteq L(G_4)$.

Проверим теперь противоположное вложение. Пусть $S_1\To_{G_4}^+\omega$. Так как в $P_4$ нет продукций вида $A\to x$, которые попали бы туда из $P_1$, то этот вывод можно записать в виде $S_1\To_{G_4}^+xS_2\To_{G_4}^+xy$, где $\omega=xy$ и все продукции, используемые в выводе $S_1\To_{G_4}^+xS_2$, попали в $P_4$ с помощью $(i)$ и $(ii)$. Следовательно, должны быть выводы $S_1\To_{G_1}^+x$ и $S_2\To_{G_2}^+y$. Отсюда вытекает вложение $L(G_4)\subseteq L(G_1)L(G_2)$.

Итак, $L(G_4)=L(G_1)L(G_2)$.

\item Пусть грамматика $G_5=(N_1\cup \{S_5\},\Sigma,P_5,S_5)$ такова, что $S_5\nsubseteq N_1$, а $P_5$ строится следующим образом:
\begin{enumerate}[label=(\emph{\roman*})]
	\item если $A,B\in N$, $x\in\Sigma^*$ и $(A\to xB)\in P_1$, то $(A\to xB)\in P_5$;

	\item если $A\in N$, $x\in\Sigma^*$ и $(A\to x)\in P_1$, то $\{A\to xS_5;A\to x\}\in P_5$;

	\item $\{S_5\to S_1\mid\eps\}\subset P_5$.
\end{enumerate}
Равенство $L(G_5)=(L(G_1))^*$ является следствием того, что вывод
\[
S_5 \To_{G_5}^+ x_1S_5 \To_{G_5}^+ x_1x_2S_5 \To_{G_5}^+ x_1x_2\ldots x_{n-1}S_5 \To_{G_5}^+ x_1x_2\ldots x_{n-1}x_n
\]
реализуем тогда и только тогда, когда реализуема последовательность выводов
\[
S_1 \To_{G_1}^+ x_1,~ S_1 \To_{G_1}^+x_2,~\ldots ~, S_1 \To_{G_1}^+ x_n.
\]
\end{enumerate}
\end{myproof}

\begin{mylemma}
\label{lemma-PL-reg-lang}
Рассмотрим ПЛ-грамматику $G=(N,\Sigma,P,S)$, где
\[
    N=\{A_1=S,\ldots ,A_1\},
\]
и построим стандартную систему уравнений с регулярными коэффициентами, неизвестными которой служат нетерминалы из $N$, а уравнение для $A_i$ определяется равенством
\[
A_i=\alpha_{i0}+\alpha_{i1}A_1+ \ldots +\alpha_{in}A_n,
\]
где
\begin{enumerate}
    \item $\alpha_{i0} = x_1 + \ldots + x_k$, если $A_i \to x_1 \mid \ldots
    \mid x_k$~--- все продукции с левой частью $A_i$ и правой частью,
    состоящей только из терминалов (при $k=0$ полагаем
    $\alpha_{i0}=\es$);

    \item для $j>0$ $\alpha_{ij} = x_1 + \ldots + x_m$, если
    $A_i \to x_1A_j \mid \ldots  \mid x_mA_j$~--- все продукции с
    левой частью $A_i$ и правой частью, содержащей $A_j$
    (при $m=0$ полагаем $\alpha_{ij}=\es$).
\end{enumerate}

Пусть $f$ --- наименьшая неподвижная точка построенной системы уравнений. Тогда $L(G)=f(S)$ --- регулярный язык.
\end{mylemma}

\begin{myproof}
Пусть $\omega\in f(S)$. Ввиду теоремы~\ref{theorem-NNTSysReg} слово $\omega$ можно записать в виде: $\omega=\omega_1\ldots \omega_m$, где $m\ge l$ и $\omega_m\in\alpha_{j_m0}$, $\omega_k\in\alpha_{j_kj_{k+1}}$ для некоторой последовательности $j_1=1, \ldots , j_m (\in\{1;2;\ldots ;n\})$. Заметим, что коэффициенты $\alpha_{ij}$ определены таким образом, что в грамматике $G$ возможен вывод:
\begin{multline*}
    S \To_G 
    \omega_1A_{j_2} \To_G 
    \omega_1\omega_2A_{j_3} \To_G 
    \ldots \To_G \\
    \omega_1\omega_2\ldots \omega_{m-1}A_{j_m} \To_G 
    \omega_1\omega_2\ldots \omega_{m-1}\omega_m.
\end{multline*}
Это означает, что $f(S)\subseteq L(G)$. С помощью похожих рассуждений проверяется обратное вложение $L(G)\subseteq f(S)$. Напомним теперь, что алгоритм~\ref{Algo-SysEq-Solver} строит $f(S)$ как регулярный язык. Таким образом, язык $L(G)=f(S)$ --- регулярный.
\end{myproof}

\begin{mytheorem}
\label{threorem-RegExp-PL241}
Пусть $\Sigma$ --- конечный алфавит. Для того, чтобы язык $L$ над алфавитом $\Sigma$ был регулярным, необходимо и достаточно, чтобы он был праволинейным.
\end{mytheorem}

\begin{myproof}
Достаточность вытекает из леммы~\ref{lemma-PL-reg-lang}, проверим необходимость. Пусть $L$ --- регулярное множество над $\Sigma$. Напомним, что множество регулярно над алфавитом $\Sigma$ тогда и только тогда, когда оно либо $\es$, либо $\{\eps\}$, либо $\{a\}$ для некоторого $a\in\Sigma$, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации. По лемме~\ref{lemma-PL-elem-lang}1 $\es$, $\{\eps\}$ и $<a>$ --- ПЛ-языки. В силу леммы~\ref{lemma-PL-op-lang} для завершения доказательства теперь можно воспользоваться индукцией по числу шагов построения регулярного множества, где один шаг соответствует применению одного из правил, определяющих регулярное множество.
\end{myproof}

\begin{myexample}
\label{example-FindRegLang}
Пусть $G=(\{A;B;S\},\{0;1\},P,S)$, где $P$ состоит из продукций
\begin{align*}
	S &\to 0A \mid 1S \mid \eps\\
    A &\to 0B \mid 1A\\
    B &\to 0S \mid 1B.
\end{align*}
Построим язык $L(G)$. Применим конструкцию из леммы~\ref{lemma-PL-reg-lang} и составим систему уравнений
\begin{equation*}
\begin{cases}
	X_1 = 0X_2 + 1X_1 + \eps \\
    X_2 = 0X_3 + 1X_2 \\
    X_3 = 0X_1 + 1X_3
\end{cases}
\end{equation*}
где $X_1=S$, $X_2=A$, $X_3=B$. Для решения системы воспользуемся алгоритмом~\ref{Algo-SysEq-Solver} и на его выходе получим:
\begin{equation*}
\begin{cases}
	X_3~=~(01^*01^*0+1)^*01^* \\
    X_2~=~1^*0(01^*01^*0+1)^*01^* \\
    X_1~=~1^*(01^*0(01^*01^*0+1)^*01^*+\eps
\end{cases}
\end{equation*}
Из теоремы~\ref{theorem-NNTSysReg} вытекает, что $L(G)=f(X_1)$, где $f$ --- наименьшая неподвижная точка системы уравнений. Таким образом,
\[
	L(G)~=~1^*(01^*0(01^*01^*0+1)^*01^*+\eps).
\]
\end{myexample}

\begin{myproblem}
Проверьте, что язык $L(G)$ из примера~\ref{example-FindRegLang} состоит из множества всех таких слов над алфавитом $\{0;1\}$, в которых число нулей кратно трем.
\end{myproblem}

\section{Упражнения}
\label{Chapter2Exs}

\subsection*{Составление регулярных выражений}

Написать регулярное выражение для
\begin{enumerate}
    \item языка над $\{a, b, c\}$ из всех слов, содержащих хотя бы один символ
    $a$;
    \item языка над $\{a, b, c\}$ из всех слов, содержащих хотя бы один символ
    $a$ и хотя бы один символ $b$;
    \item языка над $\{0, 1\}$ из всех слов, в которых третий с правого края
    символ равен $1$;
    \item языка над $\{0, 1\}$ из всех слов, в которых нет двух подряд идущих единиц;
    \item языка над $\{0, 1\}$ из всех слов, в которых любая пара смежных нулей,
     расположена левее любой пары смежных единиц;
    \item языка над $\{0, 1\}$ из всех слов с чередующимися нулями и единицами.
\end{enumerate}

\subsection*{Системы линейных уравнений с регулярными коэффициентами}

Решить системы уравнений:
\begin{equation}
    \begin{cases}
    X_1 = aX_1 + aX_2;\\
    X_2 = bX_2 + b.
    \end{cases}
\end{equation}

\begin{equation}
    \begin{cases}
        X_1 = 1X_1 + 0X_2 + \es X_3; \\
        X_2 = 1X_1 + \es X_2 + 0X_3; \\
        X_3 = 0X_1 + \es X_2 + 1X_3.
    \end{cases}
\end{equation}

\begin{equation}
    \begin{cases}
        X_1 = a^{\ast}X_1 + (a+b)^{\ast}X_2;\\
        X_2 = (a+b^{\ast})X_1 + aX_2 + b^\ast.
    \end{cases}
\end{equation}

\begin{equation}
    \begin{cases}
        X_1 = (a+b)X_1 + \es X_2 + a^{\ast}X_3; \\
        X_2 = \es X_1 + aX_2 + a^{\ast}; \\
        X_3 = b^{\ast}X_1 + \es X_2 + a^{\ast}X_3.
    \end{cases}
\end{equation}

Написать регулярные выражения для языков, заданных грамматиками cо
следующими продукциями:
\begin{equation}
\begin{array}{l}
S \to 1A \mid 2S; \\
A \to 0B \mid 0S \mid 1A; \\
B \to 1C \mid 2C; \\
C \to \varepsilon \mid 1S \mid 2A.
\end{array}
\end{equation}

\begin{equation}
\begin{array}{l}
S \to 0A \mid 1S \mid \varepsilon ;\\
A \to 0B \mid 1A;\\
B \to 0S \mid 1B.
\end{array}
\end{equation}