Pushdown

Pushdown

Pushdown on tyyppi automaatti tietojenkäsittelyssä. Se koostuu pinoista (stacks) ja tapahtumista, jotka ovat riippuvaisia pinosta. Pushdown-automaatti voi olla hyödyllinen monissa erilaisissa laskennallisissa ongelmissa, kuten kontekstivapaan kielen tunnistamisessa.

Pushdown-automaatissa on kolme komponenttia: tilat (states), aakkosto (alphabet) ja siirtymäfunktiot (transition functions). Kun pushdown-automaatti lukee syötettä, se voi tehdä siirtymän tilasta toiseen käyttämällä siirtymäfunktiota. Lisäksi pushdown-automaatti voi lisätä tai poistaa symboleja pinoistaan siirtymien aikana.

Esimerkiksi, jos haluamme tunnistaa kielen, joka koostuu sanoista, jotka alkavat ja loppuvat samalla kirjaimella, voimme käyttää pushdown-automaattia. Jokainen symboli lisätään pinoon, kunnes saavutetaan lopputila, jossa tarkistetaan, onko pinossa sama symboli kuin alussa. Jos näin on, kieli hyväksytään.

Pushdown-automaatti on siis hyödyllinen työkalu monimutkaisten kielioppien tunnistamisessa ja laskennallisissa ongelmissa.

Lähteet