Как стек расширяет возможности конечного автомата

Магазинный автомат сочетает конечное управление со стеком, доступным по принципу «последним пришёл — первым вышел». Недетерминированные магазинные автоматы распознают контекстно-свободные языки; детерминированная разновидность обладает более ограниченными возможностями.