Зміст:
Магазинні автомати
Магазинний автомат \(M\) — це сімка \(M = \left\langle Q, \Sigma, \Gamma, q_0, j_0, \sigma, F \right\rangle\), де:
-
\(Q = \{q_0, q_1, \ldots, q_{m - 1}\}\) — множина станів магазинного автомату;
-
\(\Sigma = \{a_1, a_2, \ldots, a_n\}\) — основний алфавіт;
-
\(\Gamma = \{\gamma_1, \gamma_2, \ldots, \gamma_k\}\) — допоміжний алфавіт (алфавіт магазина);
-
\(q_0 \in Q\) — початковий стан магазинного автомату;
-
\(j_0 \in \Gamma^\star\) — початковий вміст магазину;
-
\(\sigma: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to 2^{Q \times \Gamma^\star}\).
-
\(F \subseteq Q\) — множина заключних станів автомата \(M\).
Поточний стан магазинного автомата \(M\) описується конфігурацією. Конфігурація магазинного автомата \(M\) — це трійка \((q, \omega, j)\), де \(q \in Q\), \(\omega \in \Sigma^\star\), \(j \in \Gamma^\star\). Серед конфігурацій магазинного автомата \(M\) виділимо дві:
-
початкова конфігурація \((q_0, \omega, j_0)\), де \(q_0 \in Q\), \(\omega\) — вхідне слово \((\omega \in \Sigma^\star)\), \(j_0 \in \Gamma^\star\);
-
заключна конфігурація \((q_f, \varepsilon, \varepsilon)\), \(q_f \in F\). В загальній теорії магазинних автоматів іноді як заключну конфігурацію розглядають \((q_f, \varepsilon, j_f)\), де \((q_f, j_f)\) — фіксована пара. Можна довести, що визначення заключної конфігурації виду \((q_f, \varepsilon, \varepsilon)\) не зменшує потужності класу магазинних автоматів.
Такт роботи (позначається \(\models\)) магазинного автомата \(M\) — це перехід від однієї конфігурації до іншої, а точніше:
\[(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)\]Робота магазинного автомата \(M\) (позначається \(\models^\star\)) — це послідовність тактів роботи, а точніше: \((q_1, \omega_1, j_1) \models^\star (q_2, \omega_2, j_2)\) тоді і тільки тоді, коли
\[(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).\]Операції \(\models\) та \(\models^\star\) можна трактувати як бінарні відношення на відповідних кортежах. Тоді робота магазинного автомата \(M\) — це рефлексивно-транзитивне замикання бінарного відношення \(\models\).
Мова магазинного автомату
Мова, яку розпізнає магазинний автомат \(M\) — позначається \(L(M)\) — це множина слів \(\omega \in \Sigma^\star,\) які задовольняють умові:
\[L(M) = \left\{ \omega \middle| \exists q_f \in F: (q_0, \omega, j_0) \models^\star (q_f, \varepsilon, \varepsilon) \right\}.\]Зафіксуємо наступні результати теорії магазинних автоматів:
-
Не існує алгоритму перетворення недетермінованого магазинного автомата у еквівалентний йому детермінований магазинний автомат.
-
Існує алгоритм, який вирішує проблему порожньої множини \(L(M)\) для конкретного магазинного автомата.
-
Існує алгоритм, який за час, пропорційний \(O(n^3)\) перевіряє, чи належить \(\omega \in \Sigma^\star\) мові, яку розпізнає магазинний автомат \(M\).
-
Клас мов, які розпізнаються магазинними автоматами, співпадає з класом мов, що породжуються КС-граматиками.
На основі сформульованих вище результатів для лівосторонньої стратегії виводу \(\omega \in \Sigma^\star\) в \(G\) запропонуємо наступне твердження: для довільної КС-граматики \(G\) можна побудувати магазинний автомат \(M\) такий, що \(L(G) = L(M)\). При цьому автомат буде моделювати лівосторонню стратегію виводу \(\omega\) в \(G\).
Магазинний автомат за КС-граматикою
Нехай \(G = \left\langle N, \Sigma, P, S \right\rangle\) — КС-граматика. Побудуємо відповідний магазинний автомат \(M = \left\langle Q, \Sigma, \Gamma, q_0, j_0, \sigma, F \right\rangle\):
-
\(Q = \{q_0\}\) — множину станів автомата складає один стан \(q_0\);
-
\(\Gamma = N \cup \Sigma\) — допоміжний алфавіт;
-
\(j_0 = S\) — початковий вміст магазина;
-
функцію \(\sigma\) визначимо так:
- якщо \(A \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p\) належить \(P\), то
- також поповнимо множину значень функції \(\sigma\) наступними значеннями:
Для слова \(\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)\). Далі розглянемо наступні ситуації:
-
коли \(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)\);
-
коли \(x_1\) — нетермінал, тоді в схемі \(P\) граматики \(G\) виберемо правило виду \(x_1 \mapsto y_1 y_2 \ldots y_l\), зробимо наступний крок безпосереднього виведення: \(S \Rightarrow y_1 \ldots y_l x_2 \ldots x_k\). При таких умовах автомат перейде в наступну конфігурацію:
\[(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).\]
Очевидно, якщо слово \(\omega\) виводиться за \(m\) кроків, то МП-автомат зробить \(m + \vert\omega\vert\) кроків та розпізнає \(\omega\). Таким чином, \(L(G) = L(M)\).
Контрольні запитання
-
Що таке магазинний автомат?
-
Що таке конфігурація магазинного автомату?
-
Які конфігурації магазинного автомату називаються початковою і заключною?
-
Що таке такт роботи і робота магазинного автомату?
-
Яку мову розпізнає магазинний автомат?
-
Що таке проблема порожньої множини \(L(M)\)?
-
Як за КС-граматикою \(G\) побудувати магазинний автомат \(M\) такий, що \(L(G) = L(M)\)?
-
Яку стратегію виведення \(\omega\) в \(G\) реалізує побудований у попередньому питанні автомат, і яка обчислювальна складність алгоритму розпізнавання слова \(\omega\)?
(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)