• Автомати Pushdown — це спосіб реалізації CFG так само, як ми розробляємо DFA для звичайної граматики. DFA може запам'ятати обмежену кількість інформації, але КПК може запам'ятати нескінченну кількість інформації.
• Автомати Pushdown — це просто NFA, доповнений «зовнішньою стековою пам’яттю». Додавання стека використовується для забезпечення можливості керування пам’яттю «останній прийшов – першим вийшов» для автоматів Pushdown. Автомати Pushdown можуть зберігати необмежену кількість інформації в стеку. Він може отримати доступ до обмеженої кількості інформації в стеку. КПК може підштовхнути елемент на вершину стека та вискочити з вершини стека. Щоб прочитати елемент у стек, верхні елементи мають бути відскочені та втрачені.
• КПК потужніший, ніж FA. Будь-яка мова, яка може бути прийнятною для FA, також може бути прийнятною для PDA. PDA також приймає клас мови, який навіть не може бути прийнятий FA. Таким чином КПК набагато перевершує ФА.

Компоненти КПК:

Вхідна стрічка: Вхідна стрічка розділена на багато клітинок або символів. Головка введення призначена лише для читання і може рухатися лише зліва направо, по одному символу за раз.

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

Стек: Стек — це структура, у якій ми можемо штовхати та видаляти елементи лише з одного кінця. Він має нескінченний розмір. У КПК стек використовується для тимчасового зберігання елементів.

Формальне визначення КПК:

КПК можна визначити як набір із 7 компонентів:

Q: скінченна множина станів

∑: вхідний набір

C: символ стека, який можна штовхати та витягувати зі стеку

q0: початковий стан

сплячий діалект

З: початковий символ, який знаходиться в Γ.

F: набір кінцевих станів

d: функція відображення, яка використовується для переходу від поточного стану до наступного.

Миттєвий опис (ID)

Ідентифікатор — це неформальна нотація того, як КПК обчислює вхідний рядок і приймає рішення про те, прийняти чи відхилити рядок.

Миттєвий опис – це трійка (q, w, α), де:

q описує поточний стан.

в описує решту вхідних даних.

що таке номер алфавіту

a описує вміст стека, зверху ліворуч.

Позначення турнікета:

Знак ⊢ описує позначення турнікета та означає один хід.

⊢* знак описує послідовність ходів.

Наприклад,

(p, b, T) ⊢ (q, w, α)

У наведеному вище прикладі під час переходу від стану p до q вхідний символ «b» споживається, а верхня частина стеку «T» представлена ​​новим рядком α.

приклад 1:

Розробити КПК для сприйняття мови a^пb^2н.

рішення: У цій мові після n букв «а» слідувати 2n букв «b». Отже, ми застосуємо дуже просту логіку, а саме, якщо ми прочитаємо одне «а», ми заштовхнемо два «а» в стек. Як тільки ми читаємо «b», тоді для кожного окремого «b» зі стеку має бути вилучено лише одне «a».

міні панель інструментів excel

Ідентифікатор можна побудувати таким чином:

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) 

Тепер, коли ми читаємо b, ми змінюємо стан з q0 на q1 і починаємо вискакувати відповідне 'a'. Отже,

 δ(q0, b, a) = (q1, ε) 

Таким чином, процес видалення «b» повторюватиметься, якщо не буде прочитано всі символи. Зауважте, що вискакування відбувається лише в стані q1.

 δ(q1, b, a) = (q1, ε) 

Після прочитання всіх b, усі відповідні a мають вискочити. Отже, коли ми читаємо ε як вхідний символ, тоді в стеку нічого не повинно бути. Отже, хід буде таким:

 δ(q1, ε, Z) = (q2, ε) 

Де

стандартне відхилення панд

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

Ми можемо узагальнити ідентифікатор як:

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε) 

Тепер ми змоделюємо цей КПК для вхідного рядка 'aaabbbbbb'.

 δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ) ⊢ δ(q0, abbbbbb, aaaaZ) ⊢ δ(q0, bbbbbb, aaaaaaZ) ⊢ δ(q1, bbbbb, aaaaaZ) ⊢ δ(q1, bbbb, aaaaZ) ⊢ δ(q1, bbb, aaaZ) ⊢ δ(q1, bb, aaZ) ⊢ δ(q1, b, aZ) ⊢ δ(q1, ε, Z) ⊢ δ(q2, ε) ACCEPT 

приклад 2:

Розробити КПК для прийняття мови 0^п1^м0^п.

рішення: У цьому КПК за n нулями слідує будь-яка кількість 1, після яких n нулів. Отже, логіка проектування такого КПК буде наступною:

Помістіть усі 0 у стек, коли зустрінете перші 0. Тоді, якщо ми читаємо 1, просто нічого не робити. Потім читайте 0, і при кожному читанні 0 витягуйте один 0 зі стека.

Наприклад:

Цей сценарій можна записати у формі ID так:

 δ(q0, 0, Z) = δ(q0, 0Z) δ(q0, 0, 0) = δ(q0, 00) δ(q0, 1, 0) = δ(q1, 0) δ(q0, 1, 0) = δ(q1, 0) δ(q1, 0, 0) = δ(q1, ε) δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state) 

Тепер ми змоделюємо цей КПК для вхідного рядка '0011100'.

 δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z) ⊢ δ(q0, 11100, 00Z) ⊢ δ(q0, 1100, 00Z) ⊢ δ(q1, 100, 00Z) ⊢ δ(q1, 00, 00Z) ⊢ δ(q1, 0, 0Z) ⊢ δ(q1, ε, Z) ⊢ δ(q2, Z) ACCEPT