¿Cuál es la diferencia entre autómatas finitos y máquinas de estados finitos?

16

He usado FSM en diseños de circuitos secuenciales digitales. Pero no estoy familiarizado con Autómatas finitos. ¿Alguien puede ayudarme a comprender la diferencia 'básica' entre los dos?

terminology automata finite-automata gpuguy
fuente
55
De Wikipedia : "... En la teoría de autómatas, una rama de la informática teórica, un autómata determinista finito (DFA), también conocido como máquina de estados finitos deterministas , es una máquina de estados finitos que acepta / rechaza cadenas finitas de símbolos y solo produce un cálculo único (o ejecución) del autómata para cada cadena de entrada ... ". DFA es el término preferido utilizado en la teoría de autómatas, FSM es el término preferido utilizado en aplicaciones prácticas.
Vor
44
Creo que FSM es más inclusivo, incluidos también los autómatas Mealy y Moore. NFA son un modelo específico.
Raphael
@Raphael: Estoy de acuerdo con usted, FSM parece más amplio (incluso Wikipedia hace la distinción entre Transductores, Aceptores, Clasificadores y Secuenciadores). "DFA" ~ "Aceptadores de FSM" (FSM con solo salida sí / no) ... además, FSM en diseños de circuitos, generalmente utilizan salidas ... Quizás pueda convertir su comentario en una respuesta.
Vor
Personalmente, uso FSM como un término amplio que incluye máquinas DFA, NFA, Mealy y Moore, transductores (de estado finito), etc. simplemente todo con un espacio de estado finito y sin memoria auxiliar.
Dan
1
@Raphael En la teoría formal (o teoría de la computación) preferimos usar la palabra "Autómatas" - para enfatizar que nuestra máquina es una máquina 'automática' (auto-movible, como su computadora) - "automática" en el sentido de que una vez se le han definido reglas de transición, no es necesario que aplique ninguna cadena inteligente inteligente explícita para procesar / clasificar (solo necesita consultar las reglas de transición en cada paso). - Considerando que el término máquina se prefiere en el contexto del dispositivo (en lugar del modelo), aunque ambos son sinónimos entre sí.
Grijesh Chauhan

Respuestas:

12

Según tengo entendido, ambos tienen "estados" y "acciones" que hacen que la máquina se mueva de un estado a otro con una señal de entrada. Por lo tanto, las ideas conceptuales son las mismas. Hay alguna diferencia en los detalles.

En FSM para diseños de circuitos, se supone que la señal de entrada es principalmente un bit (binario), mientras que en autómatas de estado finito se puede tener un alfabeto general "abstracto" de símbolos de entrada. En segundo lugar, un FSM también genera una salida, asociada al estado alcanzado, también binario. En terminología de autómatas, esta 'extensión' se llama máquina Moore. Sin embargo, los autómatas tienen estados finales (o de aceptación) que indican una lectura de entrada favorable. Finalmente, los FSM son en su mayoría deterministas, es decir, para cada entrada en un determinado estado hay un estado siguiente. En la teoría de autómatas, también se considera la variante no determinista en la que uno podría elegir dónde moverse.

Hendrik Jan
fuente
6

Según mi experiencia y el artículo de Wikipedia, hay varios tipos de máquinas de estados finitos , que incluyen

Algunas de las nociones que vuelan difieren principalmente en la motivación; algunos surgieron de la teoría del lenguaje y / o computabilidad, otros de la arquitectura de computadoras.

Tenga en cuenta que también puede cambiar varios paradigmas para obtener autómatas que son, posiblemente, autómatas de estado finito, por ejemplo

Como puede ver, los autómatas finitos de vainilla como se enseña en TCS 101 no son más que uno de los muchos, cada uno con su propia definición (más o menos formal).

Rafael
fuente
2

Aunque la idea principal en la que ambos confían es la misma. Ambos usan estados finitos y saltan a otro estado como alimentación de entrada. Sin embargo, FSM es una máquina, como Full adder o SR flipflop tiene bits como entrada y salida. Sí, la FSA también tiene salida de bits, 0 para el estado sin terminación y 1 para el estado final, pero es un mecanismo abstracto y no se ve. Hay una diferencia en los dígrafos que se dibujan para representarlos. Además de que FSA es un dispositivo lógico y de computación, mientras que FSM es un dispositivo lógico digital.

Saryan Sandeep
fuente