One-turn pushdown automata (Jednoobrátkový zásobníkový automat)
Horní obrátka: Bod v čase (konfigurace automatu), kdy se místo prodlužování délky zásobníku začne zásobník zkracovat.
Dolní obrátka: Bod v čase (konfigurace automatu), kdy se místo zkracování délky zásobníku začne zásobník prodlužovat.
Jednoobrátkový zásobníkový automat obsahuje pouze jednu a to horní obrátku.
Harrison, 1978 (pracovně, z přednášky o RPDA): L(JednoobrátkovýPDA) = LIN
Link to this Page