Automat z zagnieżdżonym stosem

Automat z zagnieżdżonym stosem (ang. nested stack automaton) – jest automatem skończonym, który może wykorzystywać stos zawierający dane, które mogą być dodatkowymi stosami. Podobnie jak automat ze stosem, automat ze stosem zagnieżdżonym może wchodzić w górę lub w dół stosu i odczytywać bieżący symbol. Ponadto może w dowolnym miejscu utworzyć nowy stos, działać na nim, ostatecznie go zniszczyć i kontynuować działanie na starym stosie. W ten sposób stosy można zagnieżdżać rekurencyjnie na dowolnej głębokości. Jednak automat zawsze działa tylko na najbardziej wewnętrznym stosie.

Atomat ze stosem zagnieżdżonym ma te same urządzenia co automat ze stosem, ale mniej restrykcji w używaniu ich.