¿Qué es DeFine (DFA)?

Definición de Dfa en toc

Ejemplo de autómata finito determinista que sólo acepta números binarios múltiplos de 3. El estado S0 es a la vez el estado inicial y un estado de aceptación. Por ejemplo, la cadena “1001” conduce a la secuencia de estados S0, S1, S2, S1, S0, y por lo tanto es aceptada.

En la teoría de la computación, una rama de la informática teórica, un autómata finito determinista (AFD) -también conocido como aceptor finito determinista (AFD), máquina de estados finitos determinista (MEFD) o autómata de estados finitos determinista (AEFD)- es una máquina de estados finitos que acepta o rechaza una cadena de símbolos dada, recorriendo una secuencia de estados determinada de forma única por la cadena[1]. En busca de los modelos más sencillos para capturar las máquinas de estado finito, Warren McCulloch y Walter Pitts fueron de los primeros investigadores en introducir un concepto similar al de autómata finito en 1943[2][3].

La figura ilustra un autómata finito determinista utilizando un diagrama de estados. En este autómata de ejemplo, hay tres estados: S0, S1 y S2 (representados gráficamente por círculos). El autómata toma una secuencia finita de 0 y 1 como entrada. Para cada estado, hay una flecha de transición que lleva al siguiente estado tanto para 0 como para 1. Al leer un símbolo, un DFA salta determinísticamente de un estado a otro siguiendo la flecha de transición. Por ejemplo, si el autómata está actualmente en el estado S0 y el símbolo de entrada actual es 1, entonces salta determinísticamente al estado S1. Un DFA tiene un estado de inicio (denotado gráficamente por una flecha que viene de ninguna parte) donde comienzan los cálculos, y un conjunto de estados de aceptación (denotados gráficamente por un círculo doble) que ayudan a definir cuando un cálculo tiene éxito.

Ejemplos de ADF

Un DFA es un modelo matemático de un dispositivo computacional simple que lee una cadena de símbolos sobre el alfabeto de entrada Σ, y acepta o rechaza la cadena de entrada. Nos gustaría convertir esta definición matemática en un programa de trabajo, para que podamos ejecutar DFAs en nuestro ordenador.

Ya está. Veamos como este tipo de datos corresponde a la definición matemática. La primera línea define State como un tipo sinónimo de Int, el tipo estándar de haskell para números enteros. Así, siempre que digamos que una variable q toma un valor de tipo State, haskell entenderá que q es un valor entero. Dar un nombre definido por el usuario al tipo de los estados es útil para hacer nuestros programas más legibles. La segunda línea introduce otro sinónimo de tipo, DFA, el tipo que usaremos para representar DFAs. La definición de tipo simplemente dice que un DFA es una 5-tupla, y especifica el tipo de cada componente de la tupla:

Para hacer algo con esta definición, definamos un autómata de ejemplo, por ejemplo, un autómata con 2 estados que acepta cadenas sobre el alfabeto {a, b} de longitud par. El autómata se define fácilmente como un valor de tipo DFA.

Autómatas finitos no deterministas

Ejemplo de autómata finito determinista que sólo acepta números binarios múltiplos de 3. El estado S0 es a la vez el estado inicial y un estado de aceptación. Por ejemplo, la cadena “1001” conduce a la secuencia de estados S0, S1, S2, S1, S0 y, por tanto, es aceptada.

En la teoría de la computación, una rama de la informática teórica, un autómata finito determinista (AFD) -también conocido como aceptor finito determinista (AFD), máquina de estados finitos determinista (MEFD) o autómata de estados finitos determinista (AEFD)- es una máquina de estados finitos que acepta o rechaza una cadena de símbolos dada, ejecutándose a través de una secuencia de estados determinada de forma única por la cadena[1] Determinista se refiere a la unicidad de la ejecución del cálculo. En busca de los modelos más sencillos para capturar las máquinas de estado finito, Warren McCulloch y Walter Pitts fueron de los primeros investigadores en introducir un concepto similar al de autómata finito en 1943[2][3].

La figura ilustra un autómata finito determinista utilizando un diagrama de estados. En este autómata de ejemplo, hay tres estados: S0, S1 y S2 (representados gráficamente por círculos). El autómata toma una secuencia finita de 0 y 1 como entrada. Para cada estado, hay una flecha de transición que lleva al siguiente estado tanto para 0 como para 1. Al leer un símbolo, un DFA salta determinísticamente de un estado a otro siguiendo la flecha de transición. Por ejemplo, si el autómata está actualmente en el estado S0 y el símbolo de entrada actual es 1, entonces salta determinísticamente al estado S1. Un DFA tiene un estado de inicio (denotado gráficamente por una flecha que viene de ninguna parte) donde comienzan los cálculos, y un conjunto de estados de aceptación (denotados gráficamente por un círculo doble) que ayudan a definir cuando un cálculo tiene éxito.

Qué es dfa en autómatas

NFA es un autómata finito no determinista. DFA es un autómata finito determinista. El DFA puede describirse y entenderse mejor como una máquina. NFA es como múltiples máquinas pequeñas que realizan actividades computacionales al mismo tiempo. Todos los DFAs derivan de los NFAs. La principal diferencia entre DFA y NFA, las dos clases que manejan las funciones de transición de la teoría de autómatas finitos/ autómatas finitos, afecta a su comportamiento de muchas maneras.

NFA se refiere a Autómata Finito No Determinista. El término no determinista en NFA significa que el NFA puede existir en, o puede hacer la transición a, muchos estados diferentes en el mismo punto del tiempo para entradas dadas.

DFA se refiere a Autómata Finito Determinista. El término determinista en DFA significa que el DFA puede existir en, o puede hacer la transición a, sólo un estado en un punto dado del tiempo para entradas dadas. Esto explica la unicidad de la computación.

Los párrafos anteriores te ayudan a entender la diferencia en la transición de DFA a NFA y de NFA a DFA. Las diferencias NFA DFA son profundas y muy útiles para permitir su uso correcto en la teoría de autómatas finitos/ autómatas finitos.