• Pushdown-automaatti on tapa toteuttaa CFG samalla tavalla kuin suunnittelemme DFA:ta tavalliselle kieliopille. DFA voi muistaa rajallisen määrän tietoa, mutta PDA voi muistaa äärettömän määrän tietoa.
• Pushdown-automaatti on yksinkertaisesti NFA, jota on täydennetty 'ulkoisella pinomuistilla'. Pinon lisäämistä käytetään antamaan Pushdown-automaateille viimeinen ensimmäiseksi ulos -muistinhallintaominaisuus. Pushdown-automaatit voivat tallentaa pinoon rajattoman määrän tietoa. Se voi käyttää rajoitettua määrää pinon tietoja. PDA voi työntää elementin pinon yläosaan ja irrottaa elementin pinon yläosasta. Jotta elementti voidaan lukea pinoon, ylimmät elementit on poistettava ja ne menetetään.
• PDA on tehokkaampi kuin FA. Mikä tahansa kieli, jonka FA voi hyväksyä, voi olla myös PDA:n hyväksymä. PDA hyväksyy myös kieliluokan, jota FA ei edes voi hyväksyä. Siten PDA on paljon parempi kuin FA.

PDA-komponentit:

Syötenauha: Syöttönauha on jaettu useisiin soluihin tai symboleihin. Syöttöpää on vain luku -tilassa ja voi liikkua vain vasemmalta oikealle, yksi symboli kerrallaan.

Rajallinen ohjaus: Äärillisellä ohjauksella on jokin osoitin, joka osoittaa sen hetkisen luettavan symbolin.

Pino: Pino on rakenne, jossa voimme työntää ja poistaa esineitä vain toisesta päästä. Sillä on ääretön koko. PDA:ssa pinoa käytetään kohteiden väliaikaiseen tallentamiseen.

PDA:n virallinen määritelmä:

PDA voidaan määritellä 7 komponentin kokoelmaksi:

K: äärellinen joukko tiloja

∑: tulosarja

C: pinon symboli, joka voidaan työntää ja ponnahtaa pinosta

q0: alkutila

int tuplata

KANSSA: aloitussymboli, joka on Γ:ssä.

F: joukko lopputiloja

d: kartoitustoiminto, jota käytetään siirtymiseen nykyisestä tilasta seuraavaan tilaan.

Välitön kuvaus (ID)

ID on epävirallinen merkintä siitä, kuinka PDA laskee syötemerkkijonon ja tekee päätöksen, että merkkijono hyväksytään tai hylätään.

Välitön kuvaus on kolmio (q, w, α), jossa:

q kuvaa nykyistä tilaa.

Sisään kuvaa jäljellä olevan tulon.

java-taulukko luetteloon

a kuvailee pinon sisältöä, ylhäällä vasemmalla.

Kääntöportin merkintä:

⊢ merkki kuvaa kääntöportin merkintää ja edustaa yhtä liikettä.

⊢*-merkki kuvaa liikesarjaa.

Esimerkiksi,

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

Yllä olevassa esimerkissä siirryttäessä tilasta p tilaan q, syötesymboli 'b' kulutetaan ja pinon 'T' yläosaa edustaa uusi merkkijono α.

Esimerkki 1:

Suunnittele PDA kielen hyväksymistä varten aⁿb²ⁿ.

Ratkaisu: Tässä kielessä n-luvun a:n perässä tulisi olla 2n:tä b:tä. Tästä syystä käytämme hyvin yksinkertaista logiikkaa, eli jos luemme yhden 'a', työnnämme kaksi a:ta pinoon. Heti kun luemme 'b':n, jokaisesta yksittäisestä 'b':stä vain yksi 'a' pitäisi saada pinosta.

yhdistämisalgoritmi

Tunnus voidaan muodostaa seuraavasti:

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

Nyt kun luemme b, muutamme tilan q0:sta q1:een ja alamme ponnahtaa vastaavaa 'a':ta. Siten,

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

Siten tämä 'b':n poksahdusprosessi toistetaan, ellei kaikkia symboleja lueta. Huomaa, että ponnahdustoiminto tapahtuu vain tilassa q1.

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

Kun olet lukenut kaikki b:t, kaikki vastaavat a:t pitäisi poksahtaa. Siksi kun luemme ε:n syötesymboliksi, pinossa ei pitäisi olla mitään. Siirto tulee siis olemaan:

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

Missä

konstruktori javassa

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

Voimme tiivistää tunnuksen seuraavasti:

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

Nyt simuloimme tätä PDA:ta syötemerkkijonolle '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 

Esimerkki 2:

Suunnittele PDA kielen 0 hyväksymistä vartenⁿ1^m0ⁿ.

Ratkaisu: Tässä PDA:ssa n lukumäärää nollia seuraa mikä tahansa määrä 1:tä, jota seuraa n määrä nollia. Siksi tällaisen PDA:n suunnittelun logiikka on seuraava:

Työnnä kaikki 0:t pinoon, kun kohtaat ensimmäiset 0:t. Sitten jos luemme 1, älä tee mitään. Lue sitten 0 ja jokaisessa lukemassa 0, ponna yksi 0 pinosta.

Esimerkiksi:

Tämä skenaario voidaan kirjoittaa tunnuslomakkeeseen seuraavasti:

 δ(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) 

Nyt simuloimme tätä PDA:ta syötemerkkijonolle '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