En pushdown-automaton (PDA) accepterar ett språk som är ett
kontextfritt språk (CFL) .
Här är varför:
* Formell definition: En PDA är en teoretisk datoranordning som använder en bunt för att lagra och hämta information, förutom att ha en ändlig tillståndskontroll och ett ingångstejp. Denna kapacitet motsvarar direkt den uttrycksfulla kraft som behövs för att känna igen CFL:er.
* ekvivalens till kontextfria grammatik: PDA:er är likvärdiga i makten till kontextfria grammatik. Detta betyder att:
* För alla CFL kan du designa en PDA som accepterar den.
* För alla PDA kan du konstruera en kontextfri grammatik som genererar det språk den accepterar.
* Begränsningar: PDA:er kan inte känna igen alla språk. De * kan inte * känna igen språk som kräver mer komplexa minne eller beräkningsfunktioner utöver stacken, till exempel kontextkänsliga språk (vilket skulle kräva något mer kraftfullt som en Turing-maskin).
