08.tex

\setcounter{section}{7}

\section{Магазинні автомати}

\subsection{Магазинні автомати}

\textit{Магазинний автомат} $M$ --- це сімка $M = \left\langle Q, \Sigma, \Gamma, q_0, j_0, \sigma, F \right\rangle$, де: 
\begin{itemize}
	\item $Q = \{q_0, q_1, \ldots, q_{m - 1}\}$ --- множина станів магазинного автомату;
	\item $\Sigma = \{a_1, a_2, \ldots, a_n\}$ --- основний алфавіт;
	\item $\Gamma = \{\gamma_1, \gamma_2, \ldots, \gamma_k\}$ --- допоміжний алфавіт (алфавіт
	магазина);
	\item $q_0 \in Q$ --- початковий стан магазинного автомату;
	\item $j_0 \in \Gamma^\star$ --- початковий вміст магазину;
	\item $\sigma: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to 2^{Q \times 
	\Gamma^\star}$.
	\item $F \subseteq Q$ --- множина заключних станів автомата $M$.
\end{itemize}

Поточний стан магазинного автомата $M$ описується конфігурацією. \textit{Конфігурація} магазинного автомата $M$ --- це трійка $(q, \omega, j)$, де $q \in Q$, $\omega \in \Sigma^\star$, $j \in \Gamma^\star$. Серед конфігурацій магазинного автомата $M$ виділимо дві:
\begin{itemize}
	\item \textit{початкова конфігурація} $(q_0, \omega, j_0)$, де $q_0 \in Q$, $\omega$ --- вхідне слово $(\omega \in \Sigma^\star)$, $j_0 \in \Gamma^\star$;
	\item \textit{заключна конфігурація} $(q_f, \varepsilon, \varepsilon)$, $q_f \in F$. В загальній теорії магазинних автоматів іноді як заключну конфігурацію розглядають $(q_f, \varepsilon, j_f)$, де $(q_f, j_f)$ --- фіксована пара. Можна довести, що визначення заключної конфігурації виду $(q_f, \varepsilon, \varepsilon)$ не зменшує потужності класу магазинних автоматів.
\end{itemize}

\textit{Такт роботи} (позначається $\models$) магазинного автомата $M$ --- це перехід від однієї конфігурації до іншої, а точніше:
\begin{equation}
	(q_1, a \omega, \gamma_1 j) \models (q_2, \omega, \gamma_2 j) \quad\text{if}\quad (q_2, \gamma_2) \in \sigma(q_1, a, \gamma_1)
\end{equation}

\textit{Робота} магазинного автомата $M$ (позначається $\models^\star$) --- це послідовність тактів роботи, а точніше: $(q_1, \omega_1, j_1) \models^\star (q_2, \omega_2, j_2)$ тоді і тільки тоді, коли
\begin{equation}
	(q_1, \omega_1, j_1) \models (q_1^1, \omega_1^1, j_1^1) \models (q_1^2, \omega_1^2, j_1^2) \models \ldots \models (q_1^n, \omega_1^n, j_1^n) \models (q_2, \omega_2, j_2).
\end{equation}

Операції $\models$ та $\models^\star$ можна трактувати як бінарні відношення на відповідних кортежах. Тоді робота магазинного автомата $M$ --- це реф\-лек\-сив\-но-транзитивне замикання бінарного відношення $\models$.

\subsubsection{Мова магазинного автомату}

Мова, яку розпізнає магазинний автомат $M$ --- позначається $L(M)$ --- це множина слів $\omega \in \Sigma^\star$, які задовольняють умові:
\begin{equation}
	L(M) = \left\{ \omega \middle| \exists q_f \in F: (q_0, \omega, j_0) \models^\star (q_f, \varepsilon, \varepsilon) \right\}.
\end{equation}

Зафіксуємо наступні результати теорії магазинних автоматів:
\begin{enumerate}
	\item Не існує алгоритму перетворення недетермінованого магазинного автомата у еквівалентний йому детермінований магазинний автомат.
	\item Існує алгоритм, який вирішує проблему порожньої множини $L(M)$ для конкретного магазинного автомата.
	\item Існує алгоритм, який за час, пропорційний $O(n^3)$ перевіряє, чи належить $\omega \in \Sigma^\star$ мові, яку розпізнає магазинний автомат $M$.
	\item Клас мов, які розпізнаються магазинними автоматами, співпадає з класом мов, що породжуються КС-граматиками.
\end{enumerate}

На основі сформульованих вище результатів для лівосторонньої стратегії виводу $\omega \in \Sigma^\star$ в $G$ запропонуємо наступне твердження: для довільної КС-граматики $G$ можна побудувати магазинний автомат $M$ такий, що $L(G) = L(M)$. При цьому автомат буде моделювати лівосторонню стратегію виводу $\omega$ в $G$.

\subsubsection{Магазинний автомат за КС-граматикою}

Нехай $G = \left\langle N, \Sigma, P, S \right\rangle$ --- КС-граматика. Побудуємо відповідний магазинний автомат $M = \left\langle Q, \Sigma, \Gamma, q_0, j_0, \sigma, F \right\rangle$:
\begin{itemize}
	\item $Q = \{q_0\}$ --- множину станів автомата складає один стан $q_0$;
	\item $\Gamma = N \cup \Sigma$ --- допоміжний алфавіт;
	\item $j_0 = S$ --- початковий вміст магазина;
	\item функцію $\sigma$ визначимо так:
	\begin{itemize}
		\item якщо $A \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p$ належить $P$, то
		\begin{equation}
			\sigma(q_0, \varepsilon, A)=\{(q_0, \omega_1), (q_0, \omega_2), \ldots, (q_0, \omega_p)\}.
		\end{equation}
		\item також поповнимо множину значень функції $\sigma$ наступними значеннями:
		\begin{equation}
			\sigma(q_0, a_i, a_i) = \{(q_0, \varepsilon)\}, \quad a_i \in \Sigma.
		\end{equation}
	\end{itemize}
\end{itemize}

Для слова $\omega \in \Sigma^\star$, $|\omega| = n$ покажемо, якщо ми за $m$ кроків 
безпосереднього виводу $S \Rightarrow^m \omega$, то відповідний автомат за $(m + n)$ кроків допустить $\omega$. Зробимо перший крок безпосереднього виведення $S \Rightarrow x_1 x_2 \ldots x_k$ тоді магазинний автомат з початкової конфігурації $(q_0, \omega, S)$ перейде в наступну конфігурацію $(q_0, \omega, x_1 x_2 \ldots x_k)$. Далі розглянемо наступні ситуації:
\begin{itemize}
	\item коли $x_1$ --- термінал $a_1$ (тобто $\omega = a_1 \omega_1$), тоді МП-автомат виконає наступний такт: $(q_0, a_1 \omega_1, a_1 x_2 \ldots x_k) \models (q_0, \omega_1, x_2 \ldots x_k)$;
	\item коли $x_1$ --- нетермінал, тоді в схемі $P$ граматики $G$ виберемо правило виду $x_1 \mapsto y_1 y_2 \ldots y_l$, зробимо наступний крок безпосереднього виведення:
    \begin{equation}
       S \Rightarrow y_1 \ldots y_l x_2 \ldots x_k
	\end{equation}
	При таких умовах автомат перейде в наступну конфігурацію:
	\begin{equation}
		(q_0, \omega, x_1 x_2 \ldots x_k) \models (q_0, \omega, y_1 y_2 \ldots y_l x_2 \ldots x_k).
	\end{equation}
\end{itemize}

Очевидно, якщо слово $\omega$ виводиться за $m$ кроків, то МП-автомат зробить $m + |\omega|$ кроків та розпізнає $\omega$. Таким чином, $L(G) = L(M)$.

\subsection{Контрольні запитання}

\begin{enumerate}
	\item Що таке магазинний автомат? % це сімка (множина станів, основний алфавіт, алфавіт магазина, початковий стан магазина, початковий вміст магазина, функція переходів, і множина заключних станів)
	\item Що таке конфігурація магазинного автомату? % трійка (стан автомату, слово, вміст магазину)
	\item Які конфігурації магазинного автомату називаються початковою і заключною? % (q_0, w,, j_0) і (q_f, eps, eps)
	\item Що таке такт роботи і робота магазинного автомату? % див визначення |= і |=* наведені вище
	\item Яку мову розпізнає магазинний автомат? % множина слів процес розпізнавання яких закінчується у заключній конфігурації
	\item Що таке проблема порожньої множини $L(M)$? % необхідно визначити чи правда що L(M) порожня множина
	\item Як за КС-граматикою $G$ побудувати магазинний автомат $M$ такий, що $L(G) = L(M)$?
	\item Яку стратегію виведення $\omega$ в $G$ реалізує побудований у попередньому питанні автомат, і яка обчислювальна складність алгоритму розпізнавання слова $\omega$? % лівосторонню, O(n+m), де n - довжина слова w, а m - кількість кроків необхідних для виведення w
\end{enumerate}