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.