En informática, un autómata determinista es un concepto de teoría de autómatas en el que el resultado de una transición de un estado a otro está determinado por la entrada. [1] : 41
Un autómata determinista común es un autómata finito determinista (DFA) que es una máquina de estados finitos donde para cada par de estado y símbolo de entrada hay una y solo una transición al siguiente estado. Los DFA reconocen el conjunto de idiomas regulares y ningún otro idioma. [1] : 52
Una forma estándar de construir un autómata finito determinista a partir de un autómata finito no determinista es la construcción de conjuntos de potencias . [1] : 44
Referencias
- ↑ a b c Anderson, James A. (2006). Teoría de los autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . ISBN 0-521-61324-8. Zbl 1127.68049 .