Pushdownautomaadid

Pushdownautomaadid (PDA) on teatud tüüpi lõpp-masinaid, mille mälu ei piirdu ainult staatiliste olekutega, vaid kasutavad lisamälu virna. Virn võimaldab tal meelde jätta ja töödelda keele süntakti struktuuri, andes masinale võimaluse kontrollida korduvaid või sõnastikku hierarhiaid suurema täpsusega kui tavalised lõppautomaatid.

PDA moodustavad järgmised komponendid: olekute hulk Q, sisend tähestik Σ, virna tähestik Γ, üleminekufunktsioon δ, algolek q0 ∈ Q, algvirna sümbol Z0 ∈ Γ ning lõppolekute hulk F ⊆ Q. Algvirna algab virnas Z0. Üleminek δ võtab kui sisendmärgi ja virna tipu ning annab uue oleku ning virna, mida saab muuta ühe või mitme sümboliga. Üleminekud võivad sisaldada ε-üleminekuid (mööndlust, kui sisendmärki ei loeta).

PDA-d jagunevad deteministlikeks (DPDA) ja mitmedeterministlikeks (NPDA). Aktsepteerimise viise on kaks levinud motifs: aktsepteerimine lõppolekuga või aktsepteerimine tühja virnaga. Need kaks lähenemist on teoreetiliselt ekvivalentsed keelte tasandil, nii et iga PDA jaoks on olemas ekvivalent PDA, mis aktsepteerib sama keelt teise meetodiga.

Seos keeltest: kõik kontekstivabad keeled on tunnistatud PDA-dega ning iga kontekstivaba keel on seetõttu PDA poolt tunnistatav. PDPAd peetakse kontekstivaba keeltestide kompleksuslikult sobivaks tööriistaks; deterministlikud kontekstivabad keeled (DCFL) on nende hulga rangemal alamkorpusel. Näide klassikalises keelees L = { a^n b^n | n ≥ 0 } on kontekstivaba ning seda saab tunnistada PDA-ga, ka deterministlikult.