Автомат pushdown — это способ реализовать контекстно-свободную грамматику аналогично тому, как мы проектируем DFA для обычной грамматики. DFA может запоминать ограниченное количество информации, но PDA может запоминать бесконечное количество информации.
По сути, автомат с нажатием кнопки —
«Конечный автомат» + «стек»
Автомат с нажатием кнопки состоит из трех компонентов:
- входная лента,
- блок управления и
- стек с бесконечным размером.
Голова стека сканирует верхний символ стека.
Стек выполняет две операции —
-
Нажмите — новый символ добавлен вверху.
-
Pop — верхний символ читается и удаляется.
Нажмите — новый символ добавлен вверху.
Pop — верхний символ читается и удаляется.
КПК может или не может прочитать входной символ, но он должен читать вершину стека при каждом переходе.
КПК может быть формально описан как 7-кортеж (Q, ∑, S, δ, q 0 , I, F) —
-
Q — конечное число состояний
-
Input является входным алфавитом
-
S — символы стека
-
δ — функция перехода: Q × (∪ ∪ {ε}) × S × Q × S *
-
q 0 — начальное состояние (q 0 ∈ Q)
-
I — начальный символ вершины стека (I ∈ S)
-
F — множество принимающих состояний (F ∈ Q)
Q — конечное число состояний
Input является входным алфавитом
S — символы стека
δ — функция перехода: Q × (∪ ∪ {ε}) × S × Q × S *
q 0 — начальное состояние (q 0 ∈ Q)
I — начальный символ вершины стека (I ∈ S)
F — множество принимающих состояний (F ∈ Q)
Следующая диаграмма показывает переход в КПК из состояния q 1 в состояние q 2 , помеченный как a, b → c —
Это означает, что в состоянии q 1 , если мы сталкиваемся с входной строкой ‘a’ и верхним символом стека является ‘b’ , то мы выталкиваем ‘ b’ , помещаем ‘c’ в верхнюю часть стека и переходим в состояние q 2 .
Терминологии, связанные с КПК
Мгновенное описание
Мгновенное описание (ID) КПК представлено триплетом (q, w, s), где
-
q это состояние
-
w — неиспользованный ввод
-
s — содержимое стека
q это состояние
w — неиспользованный ввод
s — содержимое стека
Турникет Нотация
Обозначение «турникет» используется для соединения пар идентификаторов, которые представляют один или несколько ходов КПК. Процесс перехода обозначается символом турникета «⊢».
Рассмотрим КПК (Q, ∑, S, δ, q 0 , I, F). Переход может быть математически представлен следующими обозначениями турникета —
(p, aw, Tβ) ⊢ (q, w, αb)
Это подразумевает, что при переходе из состояния p в состояние q используется входной символ «a» , а вершина стека «T» заменяется новой строкой «α» .
Примечание. Если нам требуется ноль или более ходов КПК, мы должны использовать для него символ (⊢ *).