Automat ze stosem

Automat ze stosem (ang. pushdown automaton, PDA) – automat skończony, który może dodatkowo korzystać ze stosu do przechowywania danych. Domyślnie przyjmuje się, że ten automat jest automatem niedeterministycznym. Takie automaty są równoważne pod względem siły wyrazu gramatykom bezkontekstowym, rozpoznając języki bezkontekstowe. Jeśli nie dopuszcza się możliwości niedeterminizmu, otrzymuje się słabszy model automatu nazywany deterministycznym automatem ze stosem.

Przykładowy diagram automatu ze stosem

Wyposażenie automatu skończonego w dwa stosy zamiast jednego, daje model obliczeń równoważny maszynie Turinga.

Definicja

Automat ze stosem definiuje się jako siódemkę ${\displaystyle (Q,{\mathcal {A}},\Sigma ,\delta ,q_{0},\sigma _{0},F),}$ gdzie:

• ${\displaystyle Q}$ jest skończonym zbiorem stanów,
• ${\displaystyle {\mathcal {A}}}$ jest skończonym alfabetem symboli wejściowych,
• ${\displaystyle \Sigma }$ jest skończonym alfabetem symboli stosowych,
• ${\displaystyle q_{0}\in Q}$ jest stanem początkowym,
• ${\displaystyle \sigma _{0}}$ jest (opcjonalnym) początkowym elementem na stosie,
• ${\displaystyle F\subseteq Q}$ jest zbiorem stanów końcowych,
• ${\displaystyle \delta \subseteq (Q\times ({\mathcal {A}}\cup \left\{\epsilon \right\})\times \Sigma )\times (Q\times \Sigma ^{*})}$ jest skończonym zbiorem dopuszczalnych przejść.

W literaturze spotyka się dwa kryteria akceptacji wejściowego ciągu: akceptacja przez pusty stos i akceptacja przez stan końcowy. Łatwo pokazać, że te dwa kryteria są równoważne: stan końcowy może w pętli zawsze czyścić stos do końca, natomiast automat może łatwo wykryć pusty stos i wejść w stan końcowy, gdy odczyta unikatowy symbol umieszczany tam wyłącznie w stanie początkowym.

Interpretacja

Automat ze stosem możemy interpretować jako graf skierowany o wierzchołkach ze zbioru ${\displaystyle Q,}$ a krawędziach zdefiniowanych przez relację przejścia ${\displaystyle \delta .}$ Krawędzie są etykietowane przez litery z alfabetu ${\displaystyle {\mathcal {A}}.}$ Aby sprawdzić, czy pewne słowo ${\displaystyle s}$ należy do języka akceptowanego przez ten automat, należy przeprowadzić obliczenie na tym automacie. W tym celu szukamy ścieżki, która zaczyna się w stanie początkowym ${\displaystyle q_{0}}$ z symbolem ${\displaystyle \sigma _{0}}$ na stosie, kończy w którymś ze stanów końcowych ${\displaystyle F}$ z pustym stosem oraz litery, którymi etykietowane są krawędzie, po których przechodzimy, tworzą słowo ${\displaystyle s.}$ Po automacie przechodzimy zgodnie z relacją przejścia.

Interpretacja relacji przejścia jest następująca: ${\displaystyle \langle p,a,\sigma ,q,U\rangle \in \delta ,}$ gdzie ${\displaystyle U}$ jest ciągiem elementów z alfabetu ${\displaystyle \Sigma }$ oznacza, że ze stanu ${\displaystyle p}$ można przejść po krawędzi etykietowanej literą ${\displaystyle a}$ do stanu ${\displaystyle q,}$ przy okazji na stosie wykonując operacje: najpierw zdjęcia ze stosu litery ${\displaystyle \sigma }$ (ruch jest dozwolony, jeśli na górze stosu jest właśnie taka litera), a potem wrzucenia na stos po kolei liter słowa ${\displaystyle U.}$

Uogólniony automat ze stosem (ang. Generalized Pushdown Automaton, GPDA)

Uogólniony automat ze stosem jest rozszerzeniem automatu ze stosem o możliwość zapisu i usuwania ciągów ze stosu w jednym kroku.

Formalnie, uogólniony automat ze stosem jest definiowany jako szóstka ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},F)}$

gdzie ${\displaystyle Q,\Sigma ,\Gamma ,q_{0}}$ i ${\displaystyle F}$ są zdefiniowane tak samo jak dla automatów ze stosem.

${\displaystyle \delta \colon Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})}$ jest funkcją przejścia.

Reguły obliczeń dla GPDA są takie same jak dla PDA, z wyjątkiem tego że ${\displaystyle a_{i+1}'s}$ i ${\displaystyle b_{i+1}'s}$ są ciągami, a nie symbolami.

GPDA i PDA są równoważne: dla każdego języka rozpoznawanego przez GPDA istnieje PDA rozpoznający ten język, i odwrotnie.

Dowód równoważności powyższych klas automatów można przeprowadzić, używając następującej symulacji:

Niech ${\displaystyle \delta (q_{1},w,x_{1}x_{2}\dots x_{m})\longrightarrow (q_{2},y_{1}y_{2}\dots y_{n})}$ będzie przejściem GPDA

gdzie ${\displaystyle q_{1},1_{2}\in Q,}$ ${\displaystyle 2\in \Sigma _{\epsilon },}$ ${\displaystyle x_{1},x_{2},\dots ,x_{m}\in \Gamma ^{*},}$ ${\displaystyle m\geqslant 0,}$ ${\displaystyle y_{1},y_{2},\dots ,y_{n}\in \Gamma ^{*},}$ ${\displaystyle n\geqslant 0.}$

Skonstruujmy następujące przejścia dla PDA:

${\displaystyle \delta ^{'}(q_{1},w,x_{1})\longrightarrow (p_{1},\epsilon )}$

${\displaystyle \delta ^{'}(p_{1},\epsilon ,x_{2})\longrightarrow (p_{2},\epsilon )}$

${\displaystyle \vdots }$

${\displaystyle \delta ^{'}(p_{m-1},\epsilon ,x_{m})\longrightarrow (p_{m},\epsilon )}$

${\displaystyle \delta ^{'}(p_{m},\epsilon ,\epsilon )\longrightarrow (p_{m+1},y_{n})}$

${\displaystyle \delta ^{'}(p_{m+1},\epsilon ,\epsilon )\longrightarrow (p_{m+2},y_{n-1})}$

${\displaystyle \vdots }$

${\displaystyle \delta ^{'}(p_{m+n-1},\epsilon ,\epsilon )\longrightarrow (q_{2},y_{1})}$