chapter-8.tex

\chapter{Автоматы с магазинной памятью}
\label{Chapter8FSMSM}
\section{Определения и примеры}
\label{Chapter8Defines}
Перед тем, как изучать этот параграф, было бы хорошо еще раз просмотреть содержание пункта 3.1.

Автомат с магазинной памятью --- это односторонний недетерминированный распознаватель (см. 1.5), в потенциально бесконечной памяти которого элементы информации хранятся и используются так же, как патроны в магазине автоматического оружия, т. е. в каждый момент доступен только верхний элемент магазина. Можно представлять себе магазин в виде слова, причем верхним символом магазина будем считать самую левую букву.

Автомат с магазинной памятью
(сокращенно МП"/автомат)~--- это семерка
\[P=
    (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F),\]
где
\begin{enumerate}
\item $Q$~--- конечное множество состояний;

\item $\Sigma$~--- конечный входной алфавит;

\item $\Gamma$~--- конечный алфавит магазинных символов;

\item функция переходов $\delta$ ---
отображение множества $Q\times(\Sigma\cup\{\eps\}) \times \Gamma$ во множество $P \left (Q \times \Gamma^* \right)$
конечных подмножеств множества $Q \times\Gamma^*$;

\item
$q_0$ $(\in Q)$ --- начальное состояние;

\item
$Z_0$ $(\in\Gamma)$ --- начальный символ
магазина;

\item
$F$ $(\subseteq Q)$ --- множество
заключительных (финальных) состояний.
\end{enumerate}


Конфигурацией МП"/автомата $P$ называется тройка $(q,\omega,\alpha)$ из $Q\times\Sigma^*\times\Gamma^*$, где $q$ --- текущее состояние управляющего устройства; $\omega$ --- непрочтенная часть входного слова (первая буква слова $\omega$ находится под входной головкой; при этом, если $\omega=\eps$, то считается, что все входное слово прочитано); $\alpha$ --- содержимое магазина (самый левый символ слова $\alpha$ отождествляется с верхним символом магазина; при этом, если $a=\eps$, то магазин считается пустым).

Такт работы МП"/автомата $P$ будем представлять бинарным отношением $\vdash_p$ (или, короче, $\vdash$), определенным на конфигурациях. Именно, если $(q,\gamma)\in\delta(q,a,\Sigma)$, то будем писать $(q,a\omega,Z\alpha)\}\vdash(q',\omega,\gamma\alpha)$, где $q,q'\in Q$, $a\in\Sigma\cup\{\eps\}$, $\omega\in\Sigma^*$, $Z\in\Gamma$ и $\alpha,\gamma\in\Gamma^*$. Если $a\neq\eps$, то формула ($q,a\omega,Z\alpha)\vdash(q',\omega,\gamma\alpha)$ говорит о том, что МП"/автомат $P$ сначала находился в состоянии $q$, имел $a$ в качестве текущей входной буквы и $Z$ в качестве верхнего символа магазина; после чего он перешел в новое состояние $q$, сдвинул входную головку на одну ячейку вправо и заменил верхний символ магазина словом $\gamma$, составленным из магазинных букв. Если же $a=\eps$ (такой такт называется $\eps$"/тактом), то текущая входная буква не принимается во внимание и входная головка не двигается, однако состояние управляющего устройства и содержимое памяти могут измениться.

Подчеркнем, что $\eps$"/такт может происходить и тогда, когда все входное слово прочитано; при пустом же магазине следующий такт невозможен.

Обычным образом вводятся обозначения $\vdash_P^i$ для $i\ge 0$, $\vdash_P^*$ и $\vdash_P^+$ (далее значок $P$ мы часто будем в этих обозначениях пропускать).

Начальной конфигурацией МП"/автомата $P$ называется конфигурация вида $\{q_0,\omega,\Sigma_0\}$; в этом случае управляющее устройство находится в начальном состоянии, входная лента содержит некоторое слово из $\Sigma^*$, а в магазине есть только начальный символ $Z_0$.

Заключительная конфигурация --- это конфигурация вида $(q,\eps,\alpha)$, где
\[
    q\in F \quad \text{и} \quad \alpha\in\Gamma^*.
\]
Говорят, что слово $\omega$ допускается
МП"/автоматом $P$, если $(q_0,\omega,Z_0)\vdash^*
(q,\eps,\alpha)$ для некоторых $q\in F$ и
$\alpha\in\Gamma^*$. Языком, определяемым (или
допускаемым) автоматом $P$, называют множество всех
слов, допускаемых автоматом $P$; этот язык
обозначается $L(P)$.

Как и в случае обычных автоматов, недетерминированность удобно интепретировать как наличие нескольких параллельно работающих экземпляров исходного МП"/автомата.

\begin{myexample}
Для того, чтобы задать язык
\[L=\{0^n1^n\mid n\ge 0\},\]
рассмотрим МП"/автомат
\[P=(\{q_0;q_1;q_2\},\{0;1\},\{Z;0\},\delta,q_0,Z,\{q_0\}),\]
где
\[
\delta(q_0,0,Z)=\{(q_1,0Z)\}, \quad
    \delta(q_1,0,0)=\{(q_1,00)\}, \quad
    \delta(q_1,1,0)=\{(q_2,\eps)\},
\]
а для остальных элементов из $Q\times(\Sigma\cup\{\eps\})\times\Gamma$ функция переходов не определена.

Работа автомата $P$ состоит в том, что он копирует в магазин состоящий из нулей префикс входного слова, а затем устраняет из магазина по одному нулю на каждую единицу, которую он обнаруживает на входе.

Например, для входного слова $0011$ автомат $P$ проделает такую последовательность тактов:
\[
    (q_0,0011,Z) \vdash (g_1,011,0Z) \vdash
        (q_1,11,00Z) \vdash (q_2,1,0Z) \vdash
        (q_2,\eps,Z)\vdash(q_0,\eps,\eps).
\]

Докажем, что $L\subseteq L(P)$. Прежде всего заметим, что осуществимы следующие пять последовательностей тактов:
%\begin{equation*}
%\begin{array}{l}
\begin{align*}
(q_0,0,Z)           &\vdash      (q_1,\eps,0Z), \\
(q_1,0^i,0Z)        &\vdash^i    (q_1,\eps,0^{i+1}Z), \\
(q_1,1,0^{i+1}Z)    &\vdash      (q_2,\eps,0^iZ), \\
(q_2,1^i,0^iZ)      &\vdash^i    (q_2,\eps,Z), \\
(q_2,\eps,Z)       &\vdash      (q_0,\eps,\eps).
\end{align*}
%\end{array}
%\end{equation*}
Отсюда вытекает, что
\[
(q_0,\eps,Z) \vdash^0 (q_0,\eps,Z)
\]
и для $n \ge 1$ возможна последовательность
\[
(q_0,0^n1^n,Z) \vdash^{2n+1} (q_0, \eps, \eps).
\]
Таким образом, $L\subseteq L(P)$.

Докажем, что $L\supseteq L(P)$. Анализ функции переходов показывает, что если $P$ допускает непустое слово, то он обязан последовательно пройти через состояния $q_0, q_1, q_2, q_0$. Если для $i\ge 1$
\[
(q_0,\omega,Z)\vdash^i(q_1,\eps,\alpha),
\]
то $\omega=0^i$, $\alpha=0^iZ$. Аналогично, если для $i\ge 1$
\[
(q_2,\omega,\alpha)\vdash^i(q_2,\eps,\beta),
\]
то $\omega=1^i$, $\alpha=0^i\beta$. Такт
\[
(q_1,\omega,\alpha)\vdash(q_2,\eps,\beta)
\]
возможен тогда и только тогда, когда $\omega=1$, $\alpha=0\beta$, а последовательность тактов
\[
(q_2,\omega,Z)\vdash^*(q_0,\eps,\eps)
\]
возможна только и только тогда, когда $\omega=\eps$. Таким образом, если
\[
(q_0,\omega,Z) \vdash^i (q_0,\eps,\alpha)
\]
для некоторого $i\ge 0$, то либо $\omega=\omega$ и $i=0$, либо $\omega=0^n1^n$, $i=2n+1$ и $\alpha=\eps$. Следовательно, $L\supseteq L(P)$.
\end{myexample}

\begin{myexample}
Построим МП"/автомат, допускающий язык
\[
L = \{\omega\omega^R\mid\omega\in\{a,b\}^+\}.
\]
Пусть $P=(\{q_0;q_1;q_2\},\{a;b\},\{Z;a;b\},\delta,q_0,Z,\{q_2\}$, где
\begin{enumerate}
\item $\delta(q_0,a,Z) = \{(q_0,aZ)\}$,
\item $\delta(q_0,b,Z) = \{(q_0,bZ)\}$,
\item $\delta(g_0,a,a) = \{(g_,aa),(q_1,\eps)\}$,
\item $\delta(q_0,a,b) = \{(q_0,a,b)\}$,
\item $\delta(q_0,b,a) = \{(q_0,ba)\}$,
\item $\delta(q_0,b,b) = \{(g_0,bb),(q_1,\eps)\}$,
\item $\delta(q_1,a,a) = \{(q_1^\eps)\}$,
\item $\delta(q_1,b,b) = \{(q_1,\eps)\}$,
\item $\delta(q_1,\eps,Z) = \{(q_2,\eps)\}$,
\end{enumerate}
а для остальных элементов из $Q\times(\Sigma\cup\{\eps\})\times\Gamma$ функция пареходов не определена.

Опишем работу МП"/автомата $P$. Сначала $P$ копирует в магазине какую"/то часть входного слова по правилам (1), (2), (4), (5) и первым альтернативам правил (3) и (6). Однако в том случае, когда текущая входная буква совпадет с верхним символом магазина, автомат может перейти (если пожелает!) в состояние $q_1$ и начать сравнивать слово в магазине с оставшейся частью входного слова. Эта возможность гарантируется вторыми альтернативами правил (3) и (6), а по правилам (7) и (8) происходит сравнение символов. Если в хода сравнения обнаруживается несовпадение очередных букв, то соответствующий экземпляр МП"/автомата <<умирает>>. Однако в силу недетерминированности разные экземпляры $P$ могут проделывать все возможные для него такты, и если реализация какой"/нибудь последовательности тактов приводит к тому, что $Z$ снова оказывается верхним (и единственным!) символом магазина, то по правилу (8) $P$ стирает $Z$ и попадает в состояние $q_2$. МП"/автомат $P$ должен допустить слово тогда и только тогда, когда все сравнения обнаружили совпадение букв.

Рассмотрим работу МП"/автомата $P$ в случав, когда $aabbaa$ --- входное слово. Ясно, что среда прочих возможны <<смертельные>> последовательности тактов, например:
\[
(q_0,aabbaa,Z) \vdash (q_0,abbaa,aZ) \vdash (q_1,bbaa,Z)
\]
или
\begin{multline*}
(q_0,aabbaa,Z) \vdash (q_0,abbaa,aZ) \vdash (q_0,bbaa,aaZ) \vdash (q_0,baa,baaZ) \vdash \\ (q_0,aa,bbaaZ) \vdash (q_0,a,abbaaZ) \vdash (q_0,\eps,aabbaaZ).
\end{multline*}
С другой стороны, возможна последовательность, оканчивающаяся заключительной конфигурацией:
\[
(q_0,abba,Z) \vdash (q_0,bba,aZ) \vdash (q_0,ba,baZ) \vdash (q_1,a,aZ) \vdash (q_1,\eps,Z) \vdash (q_2,\eps,\eps).
\]
Это означает, что МП"/автомат $P$ допускает входное слово $aabbaa$.

Докажем, что $L\subseteq L(P)$. Пусть $\omega=c_1c_2\ldots c_{n-1}c_nc_{n-1}\ldots c_1$, где $C_i\in\{a,b\}$ для $1\le i\le n$. Возможна следующая последовательность тактов:
\begin{multline*}
(q_0,\omega,Z) \vdash^n (q_0,c_n,c_{n-1}\ldots c_1,c_nc_{n-1}\ldots c_1Z) \vdash \\ (q_1,c_{n-1}\ldots c_1,c_{n-1}\ldots c_1,c_{n-1}\ldots c_1Z) \vdash^{n-1} (q_1,\eps,Z) \vdash {q_2,\eps,\eps}.
\end{multline*}
Таким образом, $L\subseteq L(P)$.

Доказательство вложения $L\supseteq L(P)$ не приводим.
\end{myexample}

\begin{myproblem}
Завершить доказательство равенства $L=L(P)$ в примере 7.1.2, то есть доказать, что если $(q_0,\omega,Z)\vdash^*(q_2,\eps,\alpha)$, где $\alpha\in\Gamma^*$, то $\omega=xx^R$ для некоторого $x\in(a+b)^+$ и $\alpha=\eps$.
\end{myproblem}

\begin{myproblem}
Для произвольного МП"/автомата
\[
P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)
\]
доказать, что если $(q,\omega,A)\vdash^n(q',\eps,\eps)$, то $(q,\omega,A\alpha)\vdash^n(q',\eps,\alpha)$ для всех $A\in\Gamma$ и $\alpha\in\Gamma^*$. Этот факт можно было бы сформулировать так: <<То, что происходит с верхним символом магазина, не зависит от того, что находится в магазине под ним>>.
\end{myproblem}

\section{Расширенный МП"/автомат}
\label{Chapter8FSMSMVariants}

Напомним, что МП"/автомат мог на каждом такте заменять лишь один верхний символ магазина. Теперь определение МП"/автомата будет слегка изменено, именно, автомату будет позволено заменять за один такт какой-нибудь магазинный префикс.

\mydef{Расширенным МП"/автоматом} (РМП"/автоматом) назовем семерку
\[
P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F),
\]
где $\delta$ --- отображение конечного подмножества множества
$Q\times(\Sigma\cup\{\eps\})\times\Gamma^*$ во множество конечных подмножеств множества $Q\times\Gamma^*$, а все другие символы имеют такой же смысл, как и в~\ref{Chapter8Defines}.

Ясно, что каждый обычный МП"/автомат является РМП"/автоматом. Конфигурация определяется как и прежде. Мы будем писать
\[
(q,a\omega,\alpha\gamma)\vdash(q',\omega,\beta\gamma),
\]
если $(q',\beta)\in\delta(q,a,\alpha)$, где $q\in Q$, $a\in\Sigma\cup\{\eps\}$, $\alpha,  \beta, \gamma\in\Gamma^*$. Языком $L(P)$, определяемым РМП"/автоматом $P$, называется множество всех таких слов $\omega$, что $(q_0,\omega,Z_0)\vdash^*(q,\eps,\alpha)$ для некоторых $q\in Q$ и $\alpha \in\Gamma^*$.

Отметим, что в отличие от МП"/автомата РМП"/автомат обладает способностью продолжать работу и тогда, когда магазин пуст.

\begin{myexample}
\label{example-langwwr-rmp}
Построим РМП"/автомат $P$, распознающий язык $L=\{\omega\omega^R\mid \omega\in\{a,b\}^*\}$. Пусть $P=(\{q;p\},\{a;b\},\{a;b;S;Z\},\delta,q,Z,\{p\})$, где
\begin{multicols}{2}
\begin{enumerate}
\item $\delta(q,a,\eps) = \{(q,a)\}$,
\item $\delta(q,b,\eps) = \{(q,b)\}$,
\item $\delta(q,\eps,\eps) = \{(q,S)\}$,
\item $(q,\eps,aSa) = \{(q,S)\}$,
\item $(q,\eps,bSb) = \{(q,S)\}$,
\item $(q,\eps,SZ) = \{(p,\eps)\}$.
\end{enumerate}
\end{multicols}
\noindent Для остальных элементов из $Q\times(\Sigma\cup\{\eps\})\times\Gamma^*$ функция переходов не определена.

Сначала автомат $P$ записывает в магазине некоторый префикс входного слова (правила (1),(2)). Далее автомат может предположить, что середина слова достигнута, и записать верхним символом магазина маркер $S$ (правило (3)). Можно проверить, что если автомат неправильно угадает середину слова, то рано или поздно он обязательно <<умрет>>, но если же автомат в нужном слове угадает середину правильно, то он имеет возможность выжить и достигнуть заключительного состояния. После угадывания середины слова автомат $P$ помещает в магазин очередную входную букву и заменяет в магазине $aSa$ или $bSb$ на $S$ (правила (1),(4) или (2),(5)). Автомат $P$ работает до тех пор, пока не исчерпается все входное слово. Если после этого в магазине останется слово $SZ$, то $P$ сотрет его и тем самым будет получена заключительная конфигурация.

Рассмотрим работу РМП"/автомата $P$ в случае, когда $aabbaa$ --- входное слово. Разумеется, как это обычно бывает, среди прочих возможны <<смертельные>> последовательности тактов, например:
\begin{multline*}
(q,aabbaa,Z) \vdash (q,abbaa,aZ) \vdash (q,abbaa,SaZ) \vdash (q,bbaa,aSaZ) \vdash \\ (q,bbaa,SZ) \vdash (q,baa,bSZ) \vdash (q,baa,SbSZ) \vdash (q,aa,bSbSZ) \vdash \\ (q,aa,SSZ) \vdash (q,a,aSSZ) \vdash (q,a,SaSSZ) \vdash (q,a,SSZ) \vdash (q,\eps,aSSZ)
\end{multline*}
или
\begin{multline*}
(q,aabbaa,Z) \vdash (q,abbaa,aZ) \vdash (q,bbaa,aaZ) \vdash (q,bbaa,SaaZ) \vdash \\ (q,aa,bbSaaZ) \vdash (q,a,abbSaaZ) \vdash (q,\eps,aabbSaaZ).
\end{multline*}
С другой стороны, возможна последовательность, оканчивающаяся заключительной конфигурацией:
\begin{multline*}
    (q,aabbaa,Z) \vdash
    (q,abbaa,aZ) \vdash
    (q,bbaa,aaZ) \vdash
    (q,baa,baaZ) \\
    %
    \vdash
    (q,baa,SbaaZ) \vdash
    (q,aa,bSbaaZ) \vdash
    (q,aa,SaaZ) \vdash
    (q,a,aSaaZ) \\
    %
    \vdash
    (q,a,SaZ) \vdash
    (q,\eps,aSaZ) \vdash
    (q,\eps,SZ) \vdash
    (q,\eps,\eps).
\end{multline*}
Это означает, что РМП"/автомат $P$ допускает входное слово $aabbaa$.
\end{myexample}

\begin{myproblem}
Доказать, что построенный в примере~\ref{example-langwwr-rmp} РМП"/автомат $P$, действительно распознает язык $L=\{\omega\omega^R\mid\omega\in\{a,b\}^*\}$.
\end{myproblem}

\begin{mytheorem}
\label{theorem-eqMPandRMP}
Класс языков, определяемых МП"/автоматами, совпадает с классом языков, определяемых РМП"/автоматами.
\end{mytheorem}

\begin{myproof}
Пусть $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ --- произвольный РМП"/автомат. Для доказательства теоремы достаточно построить такой МП"/автомат $P_1$, что $L(P_1)=L(P)$. Ниже будет предъявлена конструкция автомата и приведена схема доказательства равенства.

Введем обозначение:
\[
    m = \max\left\{|\alpha|: \delta(q,a,\alpha)\neq\es, \alpha\in\Gamma^*,
                q\in Q, a\in\Sigma\cup\{\eps\}\right\}.
\]
Построим МП"/автомат $P_1$, который будет моделировать автомат $P$, храня верхние $m$ символов его магазина в <<буфере>> длины $m$, занимающим часть памяти управляющего устройства автомата $P_1$. При этом автомат $P_1$ сможет сообщить в начале каждого такта, каковы $m$ верхних символов магазина автомата $P$. Если в некотором такте $P$ заменяет слово из $k$ верхних символов магазина словом из $l$ символов, то $P_1$ заменит $k$ первых символов в буфере этим словом длины $l$. Если $l<k$, то $P_1$ сделает $k-i$ вспомогательных $\eps$"/тактов, в течение которых $k-i$ символов перейдут из верхней части магазина в буфер управляющего устройства; после этого буфер окажется заполненным, и $P_1$ будет готов моделировать очередной такт автомата $P$. Если $i>k$, то символы передаются из буфера в магазин. В качестве состояний МП"/автомата $P_1$ будут рассматриваться упорядоченные пары $[q,\alpha]$, где $q$ --- состояние из множества $Q, \alpha (\in\Gamma_1^*)$ --- буфер, $0\le|\alpha|\le m$.

Итак, рассмотрим МП"/автомат $P_1=(Q_1,\Sigma,\Gamma_1,\delta_1,q_1,Z_1,F_1)$, где
\begin{itemize}
\item[] $\Gamma_1 = \Gamma\cup\{Z_1\}$,
\item[] $Q_1 = \{[q,\alpha]\mid q\in Q, \alpha\in\Gamma^*_1, 0\le\alpha\le m\}$,
\item[] $q_1 = [q_0,Z_0Z_1^{m-1}]$,
\item[] $F_1 = \{[q,\alpha]\mid q\in F, \alpha\in\Gamma_1^*\}$,
\end{itemize}
а функция переходов $\delta_1$ определяется по правилам:
\begin{enumerate}
    \item если $(r,Y_1 \ldots Y_l)\in\delta(q,a,X_1\ldots X_k)$, то
    для всех $Z\in\Gamma_1$ и всех таких $\alpha\in\Gamma_1^*$,
    у которых $|\alpha|=m-k$ положим

    \begin{enumerate}
        \renewcommand{\labelenumii}{\arabic{enumi}.\arabic{enumii})}
        \item при $l\ge k$ для всех $\beta\in \Gamma_{1}^*$, у которых
        $\beta\gamma=Y_1\ldots Y_l\alpha$ и $|\beta|=m$:
        %
        \[
        ([r,\beta],\gamma Z)\in\delta_1([q,X_1\ldots X_k\alpha],a,Z),
        \]

        \item при $l<k$:
        %
        \[
        ([r,Y_1\ldots Y_l\alpha Z],\eps) \in
            \delta_1([q,X_1\ldots X_k\alpha],a,Z);
        \]
    \end{enumerate}

    \item $\delta_1([q,\alpha],\eps,Z)=\{([q,\alpha Z],\eps)\}$ для
    всех $q\in Q$, $\Sigma\in\Gamma_1$ и всех таких
    $\alpha\in\Gamma_1^*$, у которых $|\alpha|<m$.

\end{enumerate}
По этим правилам осуществляется заполнение буфера управляющего устройства, который содержит $m$ символов. Отметим, что в начальный момент буфер содержит символ $Z_0$ наверху и $(m-1)$ символов $Z_1$ ниже. Символ $Z_1$ используется как специальный маркер, отмечающий <<дно>> магазина.

Анализ конструкции автомата $P_1$ позволяет показать, что такт
\[
    (q,a\omega,X_1\ldots X_kX_{k+1}\ldots X_n) \vdash_P
        (r,\omega,Y_1 \ldots Y_lX_{k+1} \ldots X_n)
\]
происходит тогда и только тогда, когда
\[
    ( [q,\alpha],a\omega,\beta ) \vdash_{P_1}^+
        ([r,\alpha'],\omega,\beta' ),
\]
где
\[
    \alpha\beta = X_1\ldots X_nZ_1^m, \alpha'\beta' =
        Y_1 \ldots Y_lX_{k+1} \ldots X_nZ_1^m, |\alpha| = |\alpha'| = m,
\]
и между двумя
конфигурациями $([q,\alpha],a\omega,\beta)$ и
$([r,\alpha'],\omega,\beta')$ МП"/автомата $P_1$ нет ни
одной, в которой состояние имело бы вторую компоненту (буфер) длины
$m$.

Таким образом, для некоторых $q\in F$ и $\alpha\in\Gamma^*$ такт
\[
(q_0,\omega,\Sigma_0) \vdash_P^* (q,\eps,\alpha)
\]
происходит тогда и только тогда, когда
\[
([q_0,Z_0Z_1^{m-1}],\omega,Z_1) \vdash_{P_1}^*([q,\beta],\eps,\gamma),
\]
где $|\beta|=m$ и $\beta\gamma=\alpha\Sigma_1^m$. Отсюда вытекает, что $L(P_1)=L(P)$.
\end{myproof}

Теорема~\ref{theorem-eqMPandRMP} предоставляет и обосновывает все необходимые конструкции для перехода от РМП к МП"/автомату. На основе этой теоремы сформулируем алгоритм~\ref{algo-RMPtoMP} (с.~\pageref{algo-RMPtoMP}).

\Algo{Построение МП"/автомата по РМП"/автомату}
{\label{algo-RMPtoMP} РМП-автомат $P = (Q, \Sigma, \Gamma, q_0, Z_0, F)$. }
{МП"/автомат $P' = (Q_1, \Sigma, \Gamma_1, q_1, Z_1, F_1)$, такой что $L(P') = L(P).$}
{ конструирование элементов автомата $P'$ по правилам теоремы~\ref{theorem-eqMPandRMP}.}
{
\item Положить $m = max \{|\alpha| \mid \alpha \in \Gamma^*, \delta(q, a, \alpha) \neq \es, q \in Q, a \in \Sigma \cup \{\eps\}\}$.

\item Положить $\Gamma_1 = \Gamma \cup \{Z_1\}$.

\item Положить $Q_1 = \{ [q, \alpha] \mid q \in Q \cup \{ q_{new} \}, \alpha \in \Gamma_1^*, 0 \leq|\alpha| \leq m \}$.

\item Определить $\delta_1$ следующим образом:
	\begin{enumerate}[itemindent=\parindent,leftmargin=!]
		\item если $\delta(q, a, X_1 \ldots X_k) \ni (r, Y_1 \ldots Y_l)$ и $l \geq k$, то для всех $Z \in \Gamma_1$ и $\alpha \in \Gamma_1^*, |\alpha| = m - k$,
		\[
			\delta_1([q, X_1 \ldots X_k\alpha], a, Z) \ni ([r, \beta], \gamma Z),
		\]
		где $\beta\gamma = Y_1\ldots Y_l\alpha$ и $|\beta| = m $;
		\item если $\delta(q, a, X_1 \ldots X_k) \ni (r, Y_1 \ldots Y_l)$ и $l \le k$, то для всех $Z \in \Gamma_1$ и $\alpha \in \Gamma_1^*, |\alpha| = m - k$,
		\[
			\delta_1([q, X_1 \ldots X_k\alpha], a, Z) \ni ([r, Y_1 \ldots \alpha Z], \eps);
		\]
		\item для всех $q \in Q, Z \in \Gamma_1$ и $\alpha \in \Gamma_1^*, |\alpha| \le m$,
		\[
			\delta_1(q_1, \eps, Z_1) = \{ ([q, \alpha Z], \eps) \};
		\]
		\item $\delta_1(q_1, \eps, Z_1) = \{ ([q_0, Z_0Z_1^{m-1}], Z_1Z_1) \}$.
  \end{enumerate}  
\item Положить $q_1 = [q_{new}, Z_1^m]$.

\item Положить $F_1 = \{ [q, \alpha] \mid q \in F, \alpha \in \Gamma_1^* \}$.

\item Вернуть МП"/автомат $P' = (Q_1, \Sigma, \Gamma_1, \delta_1, q_1, Z_1, F_1)$ в качестве результата.
} 

\section{Автомат, допускающий слово опустошением магазина }
\label{MPeps-fsm}
Напомним, что согласно данным ранее определениям, слово $\omega$ из
$\Sigma^*$ допускается РМП"/автоматом $P=
(G,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ тогда и только тогда, когда
\[
(q_0,\omega,Z_0)\vdash^*(q,\eps,\alpha)
\]
для некоторых $q\in F$ и
$\alpha\in\Gamma^*$, а языком $L(P)$, определяемым автоматом $P$,
называют множество всех слов, допускаемых автоматом $P$. Теперь изменим условие допускаемости слова.

Пусть $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,P)$ --- РМП"/автомат. Будем говорить, что автомат $P$ допускает слово $\omega\in\Sigma^*$ \mydef{опустошением магазина}, если $(q_0,\omega,Z_0)\vdash^+(q,\eps,\eps)$ для некоторого $q\in Q$. Пусть $L_\eps(P)$ --- множество всех слов, допускаемых автоматом $P$ опустошением магазина. Далее, если нас в автомате (МП или РМП) будет интересовать только язык $L_\eps(P)$, то такие автоматы будем называть МП$\eps$"/автомат и РМП$\eps$"/автомат соответственно.

Если два РМП"/автомата. $P$ и $R$, отличаются друг от друга только множествами заключительных состояний, то $L_\eps(P)=L'_\eps(R)$, хотя, разумеется, языки $L(P)$ и $L(R)$ не обязаны совпадать. Поэтому при изучении языков, допускаемых РМП-автоматами опустошением магазина, обычно рассматривают только такие автоматы, у которых $P=\es$.

Выясним, как связано новое условие допускаемости слов с прежним.

\begin{mytheorem}
\label{theorem-eqMPandMPeps}
Пусть $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ --- РМП"/автомат. Тогда можно построить такой МП$\eps$"/автомат $P'$, что $L_\eps(P')=L(P)$.
\end{mytheorem}

\begin{myproof}
Ввиду теоремы~\ref{theorem-eqMPandRMP} будем, не теряя общности, полагать, что $P$ --- МП"/автомат.

Предположим, что автомат $P'$ моделирует действия автомата $P$, и прикинем, каким требованиям он обязан в этом случае удовлетворять. Введем специальное состояние $q_\eps$, которое позволяет опустошать магазин; всякий раз, когда $P$ переходит в заключительное состояние, $P'$ должен решать, продолжать ли моделирование $P$ или перейти в состояние $q_\eps$. Второй важный момент, который надо учесть, состоит в том, что для некоторого входного слова $\omega$ автомат $P$ может сделать последовательность тактов, приводящую к опустошению магазина, но управляющее устройство окажется при этом не в заключительном состоянии; тогда для того, чтобы помешать $P'$ допустить в этом случае слово $\omega$, надо добавить к $P'$ специальный маркер $Z'$, отмечающий <<дно>> магазина, который автомат $P'$ может устранить только в состоянии $q_\eps$. Этот же символ, $Z'$, будет начальным символом магазина.

Итак, пусть
\[
P' = (Q\cup\{q_\eps;q'\},\Sigma,\Gamma\cup\{Z'\},\delta',q',Z',\es),
\]
где $\delta'$ определяется так:
\begin{enumerate}
    \item $\delta'(q',\eps,Z')=\{(q_0,Z_0,Z')\}$;

    \item $\forall q\in Q$, $\forall a\in\Sigma\cup\{\eps\}$,
    $\forall Z\in\Gamma$:
        \[(r,\gamma)\in\delta(q,a,Z) \To (r,\gamma)\in\delta'(q,a,Z);\]

    \item $\forall q\in F$, $\forall Z\in\Gamma\cup\{Z'\}$:
        $(q_\eps,\eps)\in\delta'(q,\eps,Z)$;

    \item $\forall Z\in\Gamma\cup\{Z'\}$:
        $\delta'(q_\eps,\eps,Z)=\{(q_\eps,\eps)\}$.
\end{enumerate}

Отметим, что на первом такте автомат $P'$ записывает в магазин $Z_0Z'$ и переходит в начальное состояние $q_0$ автомата $P$, a $Z'$ начинает играть роль маркера, отмечающего <<дно>> магазина.

Анализ функций переходов $\delta$ и $\delta'$ показывает, что для некоторых натуральных $r$ и $n$, произвольного $q$ из $F$ и произвольных слов $Y_1, \ldots , Y_{r-1}, Y_r=Z'$ из $\Gamma^*$ последовательность тактов автомата $P'$
\begin{multline*}
    (q',\omega,Z')
        \vdash_{P'} (q_0,\omega,Z_0,Z')
        \vdash_{P'}^n \\ (q,\eps,Y_1 \ldots Y_r)
        \vdash_{P'} (q_\eps,\eps,Y_2 \ldots Y_r)
        \vdash_{P'}^{r-1} (q_\eps,\eps,\eps)
\end{multline*}
осуществима тогда и только тогда, когда
\[
    (q_0,\omega,Z_0) \vdash_P^n (q, \eps, Y_1 \ldots Y_{r-1}).
\]
Следовательно, $L_\eps(P')=L(P)$.
\end{myproof}

Сформулируем основной результат теоремы~\ref{theorem-eqMPandMPeps} в виде алгоритма~\ref{algo-MPtoMPeps}.

\Algo[b]{Построение МП$\eps$"/автомата по МП"/автомату}
{\label{algo-MPtoMPeps} МП-автомат $P = (Q, \Sigma, \Gamma, q_0, Z_0, F)$. }
{МП"/автомат $P' = (Q_1, \Sigma, \Gamma_1, q_1, Z_1, \es)$, такой что $L_\eps(P') = L(P).$}
{ конструирование элементов автомата $P'$ по правилам теоремы~\ref{theorem-eqMPandMPeps}.}
{
\item Положить $Q_1 = Q \cup \{ q_\eps, q_1 \}$.

\item Положить $\Gamma_1 = \Gamma \cup \{Z_1\}$.

\item Определить $\delta_1$ следующим образом:
	\begin{enumerate}[itemindent=\parindent,leftmargin=!]
		\item $\delta_1(q_1, \eps, Z_1) = \{ (q_0, Z_0Z_1) \}$;
		\item если $\delta(q, a, Z) \ni (r, \gamma)$, то $\delta_1(q, a, Z) \ni (r, \gamma)$ для всех $q \in Q, a \in \Sigma \cup \{ \eps \}$ и $Z \in \Gamma$;
		\item $\delta_1(q, \eps, Z) \ni (q_\eps, \eps)$ для всех $a \in F$ и $Z \in \Gamma_1$;
		\item $\delta_1(q_\eps, \eps, Z) = \{ (q_\eps, \eps) \}$ для всех $Z \in \Gamma_1$.
  \end{enumerate}  

\item Вернуть МП"/автомат $P' = (Q_1, \Sigma, \Gamma_1, \delta_1, q_1, Z_1, \es)$ в качестве результата.
} 

Заметим, что алгоритм~\ref{algo-MPtoMPeps} <<заворачивает>> исходный МП"/автомат в автоматную обёртку, цель которой --- очистить магазин после перехода исходного автомата в завершающую конфигурацию. 

Справедливо обращение теоремы~\ref{theorem-eqMPandMPeps}.

\begin{mytheorem}
\label{theorem-eqRMPandMPeps}
Пусть $P=(Q,\Sigma,\Gamma,\delta,q_0,\Sigma_0,\es)$ --- РМП$\eps$"/автомат. Тогда можно построить такой МП"/автомат $P'$, что $L(P')=L_\eps(P)$.
\end{mytheorem}

\begin{myproof}
Ввиду теоремы~\ref{theorem-eqMPandRMP} будем, не теряя общности, полагать, что
$P$~--- МП"/автомат.

Как и при доказательстве теоремы~\ref{theorem-eqMPandMPeps} предположим, что автомат $P'$ моделирует действия автомата $P$, и выясним, каким требованиям он обязан в этом случае удовлетворять. Введем заключительное состояние $g_f$ и маркер $Z'$ , отмечающий <<дно>> магазина нового автомата ($Z'$ будет, кроме того, начальным магазинным символом). В тот момент, когда автомат $P'$ может прочесть $Z'$ , он будет переходить в новое заключительное состояние $q_f$.

Итак, пусть
\[
P' = (Q\cup\{q_f;q'\},\Sigma,\Gamma\cup\{Z'\},\delta' ,q' ,Z' ,\{q_f\}),
\]
где $\delta'$ определяется так:
\begin{enumerate}
    \item $\delta' (q',\eps,Z')=\{(q_0,Z_0,Z')\}$;

    \item $\forall q\in Q$, $\forall a\in\Sigma\cup\{\eps\}$,
    $\forall\ Z\in\Gamma$:
        $(r,\gamma)\in\delta(q,a,Z)\To(r,\gamma)\in\delta'(q,a,Z)$;

    \item $\forall q\in Q$: $\delta'(q,\eps,Z')=\{(q_f,\eps)\}$.
\end{enumerate}

Доказательство равенства $L(P')=L_\eps(P)$ не приводим.
\end{myproof}

\begin{myproblem}
Доказать равенство $L(P')=L_\eps(P)$ из теоремы~\ref{theorem-eqMPandMPeps}.
\end{myproblem}

Сформулируем основной результат теоремы~\ref{theorem-eqRMPandMPeps} в виде алгоритма~\ref{algo-RMPtoMPeps}.

\Algo{Построение МП"/автомата по МП$\eps$"/автомату}
{\label{algo-RMPtoMPeps} МП$\eps$-автомат $P = (Q, \Sigma, \Gamma, q_0, Z_0, \es)$. }
{МП"/автомат $P' = (Q_1, \Sigma, \Gamma_1, q_1, Z_1, F_1)$, такой что $L_(P') = L\eps(P).$}
{ конструирование элементов автомата $P'$ по правилам теоремы~\ref{theorem-eqRMPandMPeps}.}
{
\item Положить $Q_1 = Q \cup \{ q_f, q_1 \}$.

\item Положить $\Gamma_1 = \Gamma \cup \{Z_1\}$.

\item Положить $F_1 = \{q_f\}$.

\item Определить $\delta_1$ следующим образом:
	\begin{enumerate}[itemindent=\parindent,leftmargin=!]
		\item $\delta_1(q_1, \eps, Z_1) = \{ (q_0, Z_0Z_1) \}$;
		\item если $\delta(q, a, Z) \ni (r, \gamma)$, то $\delta_1(q, a, Z) \ni (r, \gamma)$ для всех $q \in Q, a \in \Sigma \cup \{ \eps \}$ и $Z \in \Gamma$;
		\item $\delta_1(q, \eps, Z_1) = \{ (q_f, \eps) \}$ для всех $q \in Q$.
  \end{enumerate}  

\item Вернуть МП"/автомат $P' = (Q_1, \Sigma, \Gamma_1, \delta_1, q_1, Z_1, F_1)$ в качестве результата.
} 

Как и в случае алгоритма~\ref{algo-MPtoMPeps}, алгоритм~\ref{algo-RMPtoMPeps}  создаёт над исходным МП"/автоматом обёртку, цель которой --- перевести результирующий автомат в финальное состояние, когда исходный автомат допустил цепочку опустошением магазина. 

\section {Эквивалентность МП"/автоматов и КС"/грамматик}
\label{Chapter8GrammarEqFSM}

Сформулируем теперь один из фундаментальных результатов теории КС"/языков, показывающий, что языки, определяемые МП"/автоматами, --- это в точности КС"/языки.

\begin{mytheorem}
\label{theorem-eqKSandMP}
Пусть $\Sigma$ --- конечный алфавит, $L$ --- язык над этим алфавитом. Тогда следующие условия эквивалентны:
\begin{enumerate}
\item $L=L(G)$ для некоторой КС"/грамматики $G$;
\item $L=L(P_1)$ для некоторого МП"/автомата $P_1$;
\item $L=L(P_2)$ для некоторого РМП"/автомата $P_2$;
\item $L=L_\eps(P_3)$ для некоторого МП"/автомата $P_3$.
\end{enumerate}
\end{mytheorem}

\begin{myproof}
Эквивалентность утверждений 2) и 3) доказана в теореме~\ref{theorem-eqMPandRMP}. Эквивалентность утверждении 3) и 4) вытекает из теорем~\ref{theorem-eqMPandMPeps} и~\ref{theorem-eqRMPandMPeps}. Ниже будут доказаны еще две теоремы --- ~\ref{cfg2pda} и~\ref{pda2cfg}. В силу теоремы~\ref{cfg2pda} утверждение 4) --- следствие утверждения 1), а в силу теоремы~\ref{pda2cfg} утверждение 1) --- следствие утверждения 4). Это завершает доказательство теоремы~\ref{theorem-eqKSandMP}.
\end{myproof}

\begin{mytheorem}\label{cfg2pda}
Пусть $G=(N,\Sigma,P,S)$ --- КС"/грамматика. Тогда можно построить такой МП"/автомат $R$, что $L_\eps(R)=L(G)$.
\end{mytheorem}

\begin{myproof}
Построим МП"/автомат $R$ так, чтобы он моделировал все левые выводы в $G$ (см. пункт~\ref{Chapter6-trees}). Именно, пусть $R=(\{q\},\Sigma,N\cup\Sigma,\delta,q,S,\es)$, и функция переходов $\delta$ полностью определяется правилами:
\begin{enumerate}[label=(\emph{\roman*})]
    \item если $A\to\alpha\in P$, то $(q,\alpha)\in\delta(q,\eps,A)$, где, напомним, $\alpha\in(N\cup\Sigma)^*$;
    \item $\delta(q,a,a)=\{(q,\eps)\}$ для всех $a\in\Sigma$.
\end{enumerate}
Первое правило моделирует продукции грамматики $G$, а второе --- позволяет эти продукции применять.

Перед тем, как проверить равенство $L_\eps(R)=L(G)$, докажем методом математической индукции два вспомогательных утверждения.

$A)$ Для произвольного натурального числа $m$ из возможности вывода $A\To^m\omega(\in\Sigma^*)$ вытекает, что $(q,\omega,A)\vdash^+(q,\eps,\eps)$.

Пусть $A\To^*\omega$. Если $m=1$, $\omega=a_1 \ldots a_k$, где $k\ge 1$, то из $i)$ и $ii)$ получаем:
\[
(q,a_1 \ldots a_k,A) \vdash (q,a_1 \ldots a_k,a_1 \ldots a_k)\vdash^k (q,\eps,\eps).
\]
Если же $m=1$ и $\omega=\eps$, то, как легко видеть, $(q,\eps,A)\vdash (q,\eps,\eps)$.

Теперь предположим, что утверждение верно для $m\le j$ и докажем его для $m=j+1$. Итак, пусть $A\To^{j+1}\omega$. Первый шаг этого вывода должен иметь вид $A\To X_1X_2 \ldots X_k$, где $X_i\To^*x_i$, $x_i\in\Sigma$ и $x_1x_2\ldots x_k=\omega_i$. Тогда в силу правила $i)$ $(q,\omega,A) \vdash (q,\omega,X_1X_2\ldots X_k)$. Если $X_i\in N$, то по предположению индукции $(q,x_i,X_i)\vdash^*(q,\eps,\eps)$. Если же $X_i=x_i\in\Sigma$, то $(q,x_i,X_i) \vdash  (q,\eps,\eps)$. Объединяя эти последовательности тактов, получаем: $(q,\omega,A) \vdash^+ (q,\eps,\eps)$.

Таким образом, утверждение $A)$ верно.

$B)$ Для произвольного натурального числа $n$ из существования последовательности тактов $(q,\omega,A)\vdash^n(q,\eps,\eps)$ вытекает, что $A\To^+\omega$.

Пусть $n=1$. Тогда, как нетрудно убедиться, $\omega=\eps$ и $(A\to \eps)\in P$. Таким образом, $A\To^+\omega$.

Теперь предположим, что утверждение верно для $n\le j$ и докажем его для $n=j+1$. Первый такт, сделанный МП"/автоматом $R$, должен иметь вид $(q,\omega,A)\vdash(q,\omega,X_1,X_2\ldots X_k)$, где $(q,x_i,X_i)\vdash^+(q,\eps,\eps)$, $x_i\in\Sigma$ и $x_1x_2\ldots x_k=\omega_i$ (см. упражнение~\ref{myproblem-612}). Тогда $(A\to X_1\ldots X_k)\in P$, а по предположению индукции $X_i\To^+x_i$ для $X_i\in N$ и $X_i\To^0x_1$ при $X_i\in\Sigma$. Таким образом, искомый вывод $A\To^+\omega$ строится так:
\[
    A   \To X_i \ldots X_k \To^* x_1X_2\ldots X_k
        \To^* x_1x_2\ldots x_{k-1}X_k
        \To^* x_1x_2\ldots x_{k-1}x_k=\omega.
\]

Итак, утверждение $B)$ верно.

Из утверждений $A)$ и $B)$ вытекает, что $S\To^+\omega$ тогда и только тогда, когда $(q,\omega,S)\vdash^+(q,\eps,\eps)$. Следовательно, $L_\eps(R)=L(G)$.
\end{myproof}

Сформулируем результаты теоремы~\ref{cfg2pda} в виде алгоритма~\ref{algo-KStoMPeps} 
(с.~\pageref{algo-KStoMPeps}).

\Algo{Построение МП$\eps$"/автомата по КС"/грамматике.}
{\label{algo-KStoMPeps} КС"/грамматика $G = (N, \Sigma, P, S)$. }
{МП$\eps$"/автомат $P = (Q, \Sigma, \Gamma, q, Z, \es)$, такой что $L\eps(P) = L(G).$}
{ конструирование элементов автомата $P$ по правилам теоремы~\ref{cfg2pda}.}
{
\item Положить $Q = \{ q \}$.

\item Положить $\Gamma = N \cup \Sigma$.

\item Определить $\delta$ следующим образом:
	\begin{enumerate}[itemindent=\parindent,leftmargin=!]
		\item если $A \to \alpha \in P$, то $\delta(q, \eps, A) \ni \{ (q, \alpha) \}$, для всех $A \in N$ и $\alpha \in (N + \Sigma)^*$;
		\item $\delta(q, a, a) = \{ (q, \eps) \}$ для всех $a \in \Sigma$.
  \end{enumerate}  

\item Вернуть МП"/автомат $P = (Q, \Sigma, \Gamma, \delta, q, S, \es)$ в качестве результата.
}

\begin{myexample}
Рассмотрим КС"/грамматику $G = (\{S\}, \{a, b\}, P, S)$, заданную множеством $P$ = \{
$S \to aSbb \mid \eps \}$.
После применения алгоритма~\ref{algo-KStoMPeps} получим автомат $P = (\{q\},  \{a, b\}, \{a, b, S\}, \delta, q, S, \es)$, где функция переходов $\delta$ определяется следующим образом:
\begin{align*}
    \delta(q, \eps, S) 	&= \{ (q, aSbb), (q, \eps) \}; \\
    \delta(q, a, a) 		&= \{ (q, \eps) \}; \\
    \delta(q, b, b) 		&= \{ (q, \eps) \}. \\
\end{align*}
\end{myexample}

Из теоремы~\ref{theorem-eqRMPandMPeps} следует, что если у нас есть МП$\eps$"/автомат, то по нему всегда можно получить МП"/автомат, распознающий тот же язык. Без обосновывающей теоремы приведём алгоритм~\ref{algo-KStoRMP}, который строит РМП"/автомат, моделирующий все правые выводы в заданной КС"/грамматике.

\Algo{Построение РМП"/автомата по КС"/грамматике.}
{\label{algo-KStoRMP} КС"/грамматика $G = (N, \Sigma, P, S)$. }
{РМП"/автомат $P = (Q, \Sigma, \Gamma, q, \mathdollar, F)$, такой что $L(P) = L(G).$}
{преобразование правил грамматики в такты автомата.}
{
\item Положить $Q = \{ q, q_f \}$.

\item Положить $\Gamma = N \cup \Sigma \cup \{ \mathdollar \}$.
\item Положить $F = \{ q_f \}$. 

\item Определить $\delta$ следующим образом:
	\begin{enumerate}[itemindent=\parindent,leftmargin=!]
		\item $\delta(q, a, \eps) = \{ (q, a) \}$ для всех $a \in \Sigma$;
		\item если $A \to \alpha \in P$, то $\delta(q, \eps, \alpha^R) \ni \{ (q, A) \}$, для всех $A \in N$ и $\alpha \in (N + \Sigma)^*$;
		\item $\delta(q, \eps, S\mathdollar) = \{ (q_f, \eps) \}$.
  \end{enumerate}  

\item Вернуть МП"/автомат $P = (Q, \Sigma, \Gamma, \delta, q, \mathdollar, F)$ в качестве результата.
}

\begin{myexample}
Рассмотрим КС"/грамматику $G = (\{S\}, \{a, b\}, P, S)$, заданную множеством $P$ = \{ $S \to aSbb \mid \eps \}$.
После применения алгоритма~\ref{algo-KStoRMP} получим автомат $P = (\{q, q_f\},  \{a, b\}, \{a, b, S, \mathdollar\}, \delta, q, \mathdollar, \{q_f\})$, где функция переходов $\delta$ определяется следующим образом:
\[\begin{array}{ll}
    \delta(q, a, \eps) 	= \{ (q, a) \}; &
    \delta(q, b, \eps) 	= \{ (q, b) \}; \\
    \delta(q, \eps, \eps) = \{ (q, S) \}; &
    \delta(q, \eps, aSbb) = \{ (q, S) \}; \\
    \delta(q, \eps, S\mathdollar) = \{ (q_f, \eps) \}. &
\end{array}\]
\end{myexample}

Покажем теперь, что язык, определяемый МП"/автоматом, контекстно"/свободен.

\begin{mytheorem}
\label{pda2cfg}
Пусть $R=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ --- МП"/автомат. Можно построить такую КС"/грамматику $G$, что $L(G)=L_\eps(R)$.
\end{mytheorem}

\begin{myproof}
Начнем строить грамматику $G=(N,\Sigma,P,S)$. Нетерминальные символы будем записывать в виде $[qZr]$, где $q,r\in Q$ и $Z\in\Gamma$, т. е. определим множество нетерминалов равенством
\[
N =\{[qZr]\mid q,r\in Q, Z\in\Gamma\} \cup \{S\}.
\]
Множество продукций зададим следующими условиями:
\begin{enumerate}
\item если $(r,X_1\ldots X_k)\in\delta(q,a,Z)$, где $k\ge 1$, то для каждой последовательности $s_1, s_2, \ldots , s_k$ состояний из $Q$ отнесем к $P$ все продукции вида
\[
[qZs_k] \to a[rX_1s_1][s_1X_2s_2]\ldots [s_{k-1}X_ks_k];
\]
\item если $(r,\eps)\in\delta(q,a,Z)$, то отнесем к $P$ продукцию $[qZr]\to a$; \\
\item для каждого $q\in Q$ отнесем к $P$ продукцию $S\to[q_0\Sigma_0q]$.
\end{enumerate}

Индукцией по числу продукций и числу тактов доказывается следующее вспомогательное утверждению: для любых $q,r\in Q$ и $Z\in\Gamma$ $[qZr]\To^+\omega$ тогда и только тогда, когда $(q,\omega,Z)\vdash^+(r,\eps,\eps)$. Из этого утверждения следует, что $S\To[q_0Z_0q]\To^+\omega$ тогда и только тогда, когда $(q_0,\omega,Z_0)\vdash^+(q,\eps,\eps)$ для $q\in Q$. Таким образом, $L_\eps(R)=L(G)$.
\end{myproof}

На базе теоремы~\ref{pda2cfg} сформулируем алгоритм~\ref{algo-MPetoKS}.

\Algo[t]{Построение КС"/грамматики по МП"/автомату.}
{\label{algo-MPetoKS} МП"/автомат $R = (Q, \Sigma, \Gamma, q, S, F)$. }
{КС"/грамматика $G = (N, \Sigma, P, S)$, такая что $L(G) = L_\eps(R)$.}
{ конструирование элементов грамматики $G$ по правилам теоремы~\ref{cfg2pda}. }
{
\item Положить $N = \{ [qZr] \mid q, r \in Q, Z \in \Gamma \} \cup \{ S \}$.

\item Положить $P = \es$.

\item Если $\delta(q, a, Z) \ni (r, X_1 \ldots X_k)$, где $k \geq 1, \quad q, r \in Q, \quad a \in \Sigma, \quad Z, X_1 \ldots X_k \in \Gamma$, то включить в $P$ все правила вида 
\[
	[qZs_k] \to a[rX_1s_1][s_1X_2s_2] \ldots [s_{k-1}X_ks_k]
\]  
для каждой последовательности $s_1, s_2, \ldots , s_k$ состояний из $Q$.

\item Если $\delta(q, a, Z) \ni (r, \eps)$, где $q, r \in Q, \quad a \in \Sigma, \quad Z \in \Gamma$, то включить в $P$ правило $[qZr] \to a$.

\item Включить в $P$ правила $S \to [q_0Z_0q]$ для каждого $q \in Q$.

\item Вернуть КС"/грамматику $G = (N, \Sigma, P, S)$ в качестве результата.
}

\begin{myexample}
Рассмотрим МП"/автомат
\[
    R = (\{ q_0, q_1, q_2 \}, \{a, b\}, \{a, b, Z_0\}, q_0, Z_0, \{ q_0 \}), 
\]
функция переходов $\delta$ которого определяется следующим образом:
\begin{align*}
    &\delta(q_0, a, Z_0) 	= \{ (q_1, aaZ_0) \}; & 
    &\delta(q_2, b, a) 		= \{ (q_2, \eps) \};  \\
    &\delta(q_1, a, a) 	  = \{ (q_1, aaa) \}; &
    &\delta(q_1, b, a) 		= \{ (q_2, \eps) \}; \\
    &\delta(q_2, \eps, Z_0) 		= \{ (q_0, \eps) \}. \\
\end{align*}

После применения алгоритма~\ref{algo-MPetoKS} получим следующие элементы результирующей грамматики $G = (N, \{a, b\}, P, S)$.

Множество нетерминалов:
\[N = \{ [qZr] \mid q, r \in \{ q_0, q_1, q_2 \}, Z \in \{a, Z_0\} \cup \{S\} \}.\]

Множество продукций $P$ без бесполезных символов:
\begin{align*}
    S	&\to [q_0Z_0q_0]; & [q_2Z_0q_0]     &\to  \eps. \\
    [q_0Z_0q_0] 	  &\to a[q_1aq_2][q_2aq_2][q_2Z_0q_0]; & [q_1aq_2] &\to b;\\
    [q_1aq_2] 		&\to a[q_1aq_2][q_2aq_2][q_2aq_2];     & [q_2aq_2] &\to b; \\
\end{align*}

После переименования множество продукций $P$ имеет следующий вид:
\[
    S	\to aABC; \quad
    A 	\to aABB \mid b; \quad
    B 	\to b; \quad
    C 	\to  \eps.
\]

Упростим правила грамматики и получим $P = \{ S \to aAb; A \to aAbb \mid b \}$.

В результате искомая грамматика имеет вид $G = (\{S, A\}, \{a, b\}, P, S)$, у которой $L(G) = \{ a^nb^{2n} \mid n \ge 1 \}$.
\end{myexample}

\section{Детерминированный МП"/автомат}
Выше отмечалось, что для каждой КС"/грамматики $G$ можно построить МП"/автомат, распознающий $L(G)$ (теорема~\ref{cfg2pda}). Однако построенный автомат был недетерминированный, а в приложениях более удобны детерминированные МП"/автоматы, которые в каждой конфигурации могут сделать не более одного очередного такта.

Дадим точное определение: МП"/автомат $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ называется \mydef{детерминированным} (сокращенно ДМП"/автоматом), если для каждых $q\in Q$ и $\Sigma\in\Gamma$ либо $\delta(q,a,Z)$ содержит не более одного элемента для каждого $a\in\Sigma$ и $(q,\eps,Z)=\es$, либо $\delta(q,a,Z)=\es$ для всех $a\in\Sigma$ и $\delta(q,\eps,Z)$ содержит не более одного элемента. В силу этих двух ограничений ДМП"/автомат в любой конфигурации может выбрать не более одного такта.

В теореме~\ref{theorem-reduction-NKAtoDKA} было показано, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых полностью определенными детерминированными конечными автоматами. Но, к сожалению, ДМП"/автоматы не так мощны по своей распознавательной способности, как недетерминированные МП"/автоматы, и существуют КС"/языки, которые нельзя определить детерминированными МП"/автоматами. При этом для более сильного
вычислительного формализма (машин Тьюринга) снова справедлива эквивалентность
детерминированной и недетерминированной версии.

ДМП-автоматные языки интересно соотносятся с уже известными классами языков.
Укажем ещё два факта об этих отношениях, кроме упомянутого выше строгого включения
в класс МП-автоматных языков.
\begin{enumerate}
    \item Хотя исключить недетерминизм без уменьшения вычислительной мощности в случае МП"/автоматов не удаётся, можно избавиться от $\eps$"/переходов,
    не меняя класса распознаваемых языков. Этот факт получается,
   если адаптировать доказательство теоремы~\ref{cfg2pda} к КС"/грамматике,
   которая находится в нормальной форме Грейбах. Подумайте, как
   реализовать эту идею.

    \item ДМП-автоматные языки содержат в себе класс регулярных языков как собственное подмножество.

    \item Все ДМП-автоматные языки не являются существенно неоднозначными, то есть для
    них существуют КС"/грамматики без неоднозначности. В то же время,
    существуют языки без неоднозначности, которые не являются ДМП"/автоматными.
     К последним относится, например, язык палиндромов четной длины
     $L_{ww^r}$.
\end{enumerate}

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

Для каждого из следующих языков
\begin{enumerate}
    \item $\{ a^n b^n c^m d^m \mid n,m \in \N\}$,
    \item $\{ a^i b^j c^j d^i \mid i,j \in \N \}$,
    \item $\{ a^i b^j c^k \mid i,j,k \in \N \text{ и } i+j=k \}$,
    \item $\left\{  x \in \{ a,b,c \}^* \mid |x|_a + |x|_b = |x|_c \right\}$
\end{enumerate}
построить МП-автомат:
\begin{enumerate}[label=\asbuk*)]
   \item распознающий $L$,
   \item распознающий $L$ опустошением магазина.
\end{enumerate}
Напомним, что запись вида $|w|_z$  (см.~язык 4) означает количество вхождений символа $z$ в строку $w$.