Aký jazyk akceptuje PDA na vstup a spracovanie?

Pushown Automaton (PDA) prijíma jazyk, ktorý je jazykom bez kontextu (CFL) .

Tu je dôvod:

* Formálna definícia: PDA je teoretické výpočtové zariadenie, ktoré používa zásobník na ukladanie a načítanie informácií, okrem toho, že má konečné ovládanie stavu a vstupnú pásku. Táto schopnosť priamo zodpovedá výraznej sile potrebnej na rozpoznávanie CFL.

* rovnocennosť s gramatickými gramatikami: PDA sú rovnocenné s právomocami bez kontextov. To znamená, že:

* Pre akýkoľvek CFL môžete navrhnúť PDA, ktorá ho akceptuje.

* Pre akúkoľvek PDA môžete zostaviť gramatiku bez kontextu, ktorá generuje jazyk, ktorý prijíma.

* Obmedzenia: PDA nedokážu rozpoznať všetky jazyky. Nemôžu * rozpoznať jazyky, ktoré si vyžadujú zložitejšiu pamäť alebo výpočtové schopnosti mimo stohu, napríklad kontextové jazyky (ktoré by vyžadovali niečo silnejšie ako Turingov stroj).

• Predchádzajúca strana: Čo je príklad skriptovacieho jazyka? 
• Ďalšia strana: Aké sú rôzne opcody MIPS používané na vykonávanie aritmetických a logických operácií v procesore?