МПА называется недетерминированным, если из одного и того же состояния и при одинаковом верхнем символе стека и входном символе возможен более чем один следующий переход.

Недетерминированный МПА  - не что иное, как устройство, реализующее перебор с возвратами, то есть неэффективный механизм распознавания языка.

Первый вариант предполагает запоминание на каждом шаге работы всех возможных следующих состояний. Алгоритм моделирует работу автомата по одному из возможных переходов до тех пор, пока либо не будет достигнуто конечное состояние  автомата, либо возникнет ситуация, когда следующий переход  не определен. В последнем случае происходит возврат на несколько шагов назад в то состояние, из которого был возможен альтернативный переход, и моделирование продолжается. Если какая-то из последовательностей шагов приводит к заключительному состоянию, то цепочка считается принятой, а автомат заканчивает работу. Если все варианты работы перебраны, а конечное состояние не достигнуто, то алгоритм завершается с ошибкой.

Во втором варианте алгоритм моделирования МПА на каждом шаге работы при возникновении неоднозначности с несколькими возможными следующими состояниями должен запускать свою новую копию для обработки каждого из этих состояний. Если хотя бы одна из копий приводит в заключительное состояние, то цепочка распознана и работа всех остальных копий также завершается. Если ни одна из копий не достигнет конечной конфигурации, алгоритм завершается с ошибкой и цепочка не принимается.

Во втором варианте различные копии алгоритма должны выполняться параллельно, следовательно, необходимо наличие механизма управления параллельными процессами. Кроме того, количество копий алгоритма заранее неизвестно, их может быть много, в то время как количество одновременно выполняющихся процессов ограничено. Этим объясняется то, что большее распространение получил первый вариант алгоритма, который называется «разбором с возвратами».