Зміст:

• Магазинні автомати

  • Мова магазинного автомату

  • Магазинний автомат за КС-граматикою

• Контрольні запитання

Магазинні автомати

Магазинний автомат $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\}.$$

Зафіксуємо наступні результати теорії магазинних автоматів:

1. Не існує алгоритму перетворення недетермінованого магазинного автомата у еквівалентний йому детермінований магазинний автомат.

2. Існує алгоритм, який вирішує проблему порожньої множини $L(M)$ для конкретного магазинного автомата.

3. Існує алгоритм, який за час, пропорційний $O(n^3)$ перевіряє, чи належить $\omega \in \Sigma^\star$ мові, яку розпізнає магазинний автомат $M$.

4. Клас мов, які розпізнаються магазинними автоматами, співпадає з класом мов, що породжуються КС-граматиками.

На основі сформульованих вище результатів для лівосторонньої стратегії виводу $\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(q_0, \varepsilon, A)=\{(q_0, \omega_1), (q_0, \omega_2), \ldots, (q_0, \omega_p)\}.$$
  • також поповнимо множину значень функції $\sigma$ наступними значеннями:
  $$\sigma(q_0, a_i, a_i) = \{(q_0, \varepsilon)\}, \quad a_i \in \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)$.

Контрольні запитання

1. Що таке магазинний автомат?

2. Що таке конфігурація магазинного автомату?

3. Які конфігурації магазинного автомату називаються початковою і заключною?

4. Що таке такт роботи і робота магазинного автомату?

5. Яку мову розпізнає магазинний автомат?

6. Що таке проблема порожньої множини $L(M)$?

7. Як за КС-граматикою $G$ побудувати магазинний автомат $M$ такий, що $L(G) = L(M)$?

8. Яку стратегію виведення $\omega$ в $G$ реалізує побудований у попередньому питанні автомат, і яка обчислювальна складність алгоритму розпізнавання слова $\omega$?

(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)

Назад до лекцій

Назад на головну