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

Магазинні автомати (автомати з магазинною пам’яттю, МП- автомати, стекові автомати) широко використовуються в програмуванні, бо дозволяють моделювати різні важливі алгоритми, які повязані з компіляцією та інтерпретаціює мов програмування, обробки складних структур даних – дерев, списків і таке інше. Такі автомати можна розглядати як обмежені машини Тьюрінга, що мають вхідну стрічку, на якій голівка може тільки читати символи і рухатись тільки в один бік, та робочу стрічку, яку відповідна голівка

може обробляти лише з однієї сторони. Як і в попередніх випадках є різні варіанти визначень магазинних автоматів. Наведемо тут просте екстенсіональне визначення, яке разом з тим є еквівалентним іншим визначенням за класом мов, що розпізнаються.

Визначення 4.29 Магазинний автомат – це шістка M =(Q, A, Γ, δ,

q0, F), де

• Q – скінченна множина станів,

• A – скінченний вхідний алфавіт (Q ∩ A =∅),

• Γ – скінченний магазинний алфавіт,

• δ – скінченне відношення переходів (скінченне відображення

δ: Q Ч A Ѓ~Γ → Q Ѓ~Γ *),

• q 0 – початковий стан із Q,

• F – підмножина фінальних (заключних) станів із Q.

Виконання команди виду (q, a, Z)→ (p, γ) означає, що знаходячись у стані q, та оглядаючи символ a на вхідній стрічці, і символ Z у магазині, автомат переходить у стан p, стирає символ a та пересуває голівку до наступного символу на вхідній стрічці, а замість символу Z записує у магазин ланцюжок γ. Зауважимо, що в інших модифікаціях магазинних автоматів перехід в новий стан може відбуватися без стирання символа із вхідної стрічки (так званий ε -перехід).

Конфігурацію магазинного автомату можна задати як трійку (q, w,

ζ), де q ∈ Q, w ∈ A *, ζ ∈ Γ *). Відношення безпосереднього переходу |– задається так: (q, aw ′, Z ζ ′)|– (p, w ′, γ ζ ′), якщо команда (q, a, Z)→ (p, γ) належить δ.

Аналогічно тому, як це робилось раніше, визначаються і інші необхідні поняття, пов’язані з магазинним автоматом: протоколи та мова, що сприймається таким автоматом. Для нас важливим є наступне твердження.

Теорема 4.6 За кожним магазинним автоматом можна побудувати еквівалентну йому породжуючу граматику типу 2 (контекстно-вільну граматику), і навпаки, за кожною породжуючою граматикою типу 2 можна побудувати еквівалентний їй магазинний автомат. Зважаючи на те, що синтаксис мов програмування, як правило, задається граматиками типу 2, теорема стверджує, что алгоритми

обробки програм можуть базуватися на магазинних автоматах.

25. Скінченні автомати

Скінченні автомати можна розглядати як обмежені машини Тьюрінга, що мають одну вхідну стрічку – голівка може тільки читати символи і рухатись тільки в один бік. Тому такі автомати не мають необмеженої пам’яті. Екстенсіональне визначення наступне.

Визначення 4.30 Скінченний автомат – це п’ятірка M =(Q, A, δ, q0,

F), де

• Q – скінченна множина станів,

• A – скінченний вхідний алфавіт (Q ∩ A =∅),

• δ – скінченне відношення переходів (скінченне відображення

δ: Q Ч A → Q),

• q 0 – початковий стан із Q,

• F – підмножина фінальних (заключних) станів із Q.

Всі основні загальні (інтенсіональні) поняття визначаються подібно до того, як це було зроблено для машин Тьюрінга та магазинних автоматів, тому тут їх наводити не будемо. Основним є наступний результат.

Теорема 4.7 За кожним скінченним автоматом можна побудувати еквівалентну йому породжуючу граматику типу 3 (ліволінійну чи праволінійну граматику), і навпаки, за кожною породжуючою граматикою типу 3 можна побудувати еквівалентний їй скінченний автомат.

Відзначимо, що детермінованість чи не детермінованість скінченного автомату не впливає на клас мов, що сприймаються автоматами. Теорія скінченних автоматів розроблена досить детально, для них побудовані алгоритми еквівалентних перетворень, мінімізації та таке інше. Тут наведемо лише один результат, що стосується алгебраїчного подання скінченно-автоматних мов. Такі мови ще називаються регулярними мовами.

Регулярні мови задаються виразами (термами) регулярної алгебри мов, що має операції об’єднання, конкатенації та ітерації. Регулярні вирази можна визначити індуктивно. Базис складається з трьох визначень.

1. Константи ε та O є регулярними виразами.

2. Якщо a – довільний символ, то a – регулярний вираз.

Зауважимо, що часто в написанні розрізняють символ алфавіту та відповідний вираз. Тут це не робимо, щоб не ускладнювати текст.

3. Якщо X – змінна, то X – регулярний вираз.

Крок індуктивної побудови. Індуктивний крок складається з чотирьох визначень, по одному для трьох операторів та для введення дужок.

1. Якщо E та F – регулярні вирази, то E + F – регулярний вираз.

2. Якщо E та F – регулярні вирази, то EF – регулярний вираз. Зауважимо, що для позначення оператора конкатенації – як операції над мовами, так і оператора в регулярному виразі – можна використовувати крапку.

3. Якщо Е – регулярний вираз, то Е* - регулярний вираз.

4. Якщо Е – регулярний вираз, то (Е) – регулярний вираз.

Інтерпретація L виразів в класі мов над алфавітом A задається також індуктивно на підставі інтерпретації змінних LV: Var → 2A *, де Var – множина змінних. Інтерпретація базових виразів задається таким чином:

1. L (ε) = {ε } і L (O) = O.

2. L (a) = { a }.

3. L (X) = LV (X).

Інтерпретація складних виразів задається таким чином (E та F – регулярні вирази):

1. L (E + F) = L (E) ∪ L (F).

2. L (EF) = L (E) L (F).

3. L (E *) = (L (E))*.

4. L ((E)) = L (E).

Основний результат стосовно регулярних мов є наступний.

Теорема 4.8 За кожним скінченним автоматом можна побудувати еквівалентний йому регулярний вираз, і навпаки, за кожним регулярним виразом можна побудувати еквівалентний йому скінченний автомат.

Наведений результат дозволяє використовувати різні формалізми (граматики типу 3, скінченні автомати, регуляні вирази) для дослідження властивостей регулярних мов. Такі мови мають гарні властивості замкненості (відносно об’єднань, перетину, доповнень, конкатенації, ітерації та деяких інших операцій). Ще одну важливу групу властивостей регулярних мов становлять ≪ властивості розв’язності≫. За їх допомогою можна з’ясувати, чи визначають два різні автомати одну і ту саму мову. Розв’язність цієї задачі дозволяє мінімізувати автомати, тобто за даним автоматом знайти еквівалентний йому з найменшою можливою кількістю станів.

26. Методи подання синтаксису мов програмування. Нормальні форми Бекуса-Наура. Модифіковані нормальні форми Бекуса-Наура

Граматики типу 2 (контекстно-вільні граматики) відіграють велику роль у формалізації мов програмування. Справа в тому, що вони задають чітке подання деякого синтаксичного поняття як структури, що склається з певних частин. Ті частини, у свою чергу, мають частини і так далі. Тобто конктекстно-вільні граматики подають ієрархічну організацію синтаксичного поняття. Це відповідає і композиційній структурі програм. Саме тому вивченню цього класу

граматик буде приділено більшу увагу. Щоб продемонструвати зв’язок з мовами програмування більш чітко, розглянемо методи подання синтаксису мов програмування. Найбільш відомим методом є нормальні форми Бекуса–Наура (БНФ). Цей формалізм (метамова) широко використовується як при поданні синтаксису мов програмування, так і при вивченні природних мов.