Pushdownautomaatit

Pushdown automaatti, tunnetaan myös nimellä pinokannettava automaatti, on laskettavuuden teorian malli, joka laajentaa äärellisiä automaatteja lisäämällä pino-muistitoiminnon. Äärellinen automaatti voi siirtyä tilasta toiseen syötteen perusteella, mutta pushdown automaatilla on lisäksi pino, johon se voi tallentaa ja josta se voi poimia tietoa. Tämä pino mahdollistaa automaatin muistaa rajattomasti tietoa, toisin kuin äärellinen automaatti, jonka muisti on rajallinen. Pushdown automaatit ovat tyypillisesti epädeterministisiä, jolloin sama syöte voi johtaa useisiin eri pino- ja tilakombinaatioihin.

Pushdown automaatin toiminta perustuu tilansiirtosääntöihin, jotka määrittävät, miten automaatti reagoi syötteeseen ja pinon tilaan. Sääntö voi esimerkiksi sanoa, että jos automaatti on tilassa A ja lukee symbolin 'x', se voi siirtyä tilaan B ja samalla työntää symbolin 'y' pinoon. Pinosta poimiminen tapahtuu vastaavasti, kun tietty symboli löytyy pinon päältä. Pushdown automaatin hyväksyntä voi perustua kahteen eri ehtoon: joko siihen, että syöte on luettu loppuun ja automaatti on jossain hyväksyvässä tilassa, tai siihen, että pino on tyhjä syötteen lukemisen jälkeen.

Pushdown automaateilla on merkitystä tietojenkäsittelytieteessä, erityisesti ohjelmointikielten syntaksin jäsentämisessä. Ne pystyvät tunnistamaan kieliä, joita äärelliset automaatit eivät pysty käsittelemään, kuten kieliä, joissa esiintyy sulkulausekkeiden tasapainoa. Vaikka pushdown automaatit ovat tehokkaampia kuin äärelliset automaatit, ne ovat edelleen rajallisia, eivätkä ne pysty tunnistamaan kaikkia laskettavia kieliä. Ne muodostavat kuitenkin tärkeän välimaaston äärellisten automaattien ja Turingin koneiden välillä.