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
Pushdown automaateilla on merkitystä tietojenkäsittelytieteessä, erityisesti ohjelmointikielten syntaksin jäsentämisessä. Ne pystyvät tunnistamaan kieliä, joita äärelliset automaatit