Основное отличие детерминированного конечного автомата (ДКА) от недетерминированного (НКА) заключается в том, как определяется следующее состояние автомата. 12

Детерминированный конечный автомат — это автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. 3 Каждый переход строго регламентирован: при поступлении входного воздействия однозначно определяется следующее состояние. 4

Недетерминированный конечный автомат — это автомат, в котором по одному входному воздействию могут произойти переходы в различные состояния. 4 При появлении входного воздействия такой автомат «размножается» — создаются копии автомата, в каждой из которых выполняется соответствующий переход из рассматриваемого состояния. 4 Считается, что недетерминированный конечный автомат достигает конечного состояния, если хотя бы одна из его «копий» перейдёт в своё конечное состояние. 4

Таким образом, детерминированный конечный автомат предсказуем, так как выход зависит только от текущего состояния и текущего входа, в то время как недетерминированный конечный автомат обладает свойством находиться в нескольких состояниях одновременно, пытаясь «догадаться», каковы его входные данные. 3