В чём отличие детерминированного конечного автомата от недетерминированного?

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

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

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

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

Пользователь

Время добавления