Описание тега pushdown-automaton
Автомат выталкивания (КПК) - это конечный автомат с добавленной стековой памятью. Это математическое описание алгоритма разбора контекстно-свободных языков.
КПК расширяют конечные автоматы через стековую память, а переходы могут выталкивать / выталкивать символы в / из стека. Детерминированные КПК (для которых существует только один законный переход в любой момент времени) строго слабее недетерминированных; это не относится к конечным автоматам (КПК более мощные) или машинам Тьюринга (КПК более слабые).