08.md

{% include mathjax %}

Зміст:

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

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

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

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

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

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

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

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

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