Детерминированный автомат

В информатике детерминированный автомат - это концепция теории автоматов, в которой результат перехода из одного состояния в другое определяется входными данными. ^[1]^{: 41}

Обычный детерминированный автомат - это детерминированный конечный автомат (DFA), который представляет собой конечный автомат, в котором для каждой пары состояния и входного символа существует один и только один переход в следующее состояние. DFA распознают набор обычных языков и никакие другие языки. ^[1]^{: 52}

Стандартный способ построить детерминированный конечный автомат из недетерминированного конечного автомата - это конструкция powerset . ^[1]^{: 44}

Ссылки [ править ]

^ ^a ^b ^c Андерсон, Джеймс А. (2006). Теория автоматов в современных приложениях . При участии Тома Хеда. Кембридж: Издательство Кембриджского университета . ISBN 0-521-61324-8. Zbl 1127.68049 .

P ≟ NP

Эта статья по теоретической информатике незавершена . Вы можете помочь Википедии, расширив ее .

[Anderson-1] Андерсон, Джеймс А. (2006). Теория автоматов в современных приложениях . При участии Тома Хеда. Кембридж: Издательство Кембриджского университета . ISBN 0-521-61324-8. Zbl 1127.68049 .

[1]