Autómata determinista

En informática , un autómata determinista es un concepto de la teoría de autómatas donde 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 (AFD), que es una máquina de estados finitos, donde para cada par de estado y símbolo de entrada existe una y solo una transición al siguiente estado. Los AFD reconocen el conjunto de lenguajes regulares y ningún otro lenguaje. ^{[ 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 del conjunto potencia . ^{[ 1 ]}^{: 44}

Referencias

1 2 3 Anderson, James A. (2006). Teoría de autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . ISBN 0-521-61324-8. Zbl 1127.68049 .

[Anderson-1] 1 2 3 Anderson, James A. (2006). Teoría de autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . ISBN 0-521-61324-8. Zbl 1127.68049 .

[ 1 ]