Qual é a diferença entre autômatos finitos e máquinas de estados finitos?

16

Eu usei o FSM em projetos de circuitos sequenciais digitais. Mas não estou familiarizado com o Finite Automata. Alguém pode me ajudar a entender a diferença "básica" entre os dois?

terminology automata finite-automata gpuguy
fonte
5
Da Wikipedia : "... Na teoria dos autômatos, um ramo da ciência da computação teórica, um autômato finito determinístico (DFA) - também conhecido como máquina de estados finitos determinísticos - é uma máquina de estados finitos que aceita / rejeita seqüências finitas de símbolos e produz apenas um cálculo exclusivo (ou execução) do autômato para cada sequência de entrada ... ". DFA é o termo preferido usado na teoria de autômatos, FSM é o termo preferido usado em aplicações práticas.
Vor
4
Acho que o FSM é mais inclusivo, incluindo também os autômatos de Mealy e Moore. Os NFA são um modelo específico.
Raphael
@Raphael: Eu concordo com você, o FSM parece mais amplo (até a wikipedia faz a distinção entre transdutores, aceitadores, classificadores e seqüenciadores). "DFA" ~ "FSM acceptors" (FSM com saída apenas sim / não) ... além disso, o FSM em projetos de circuitos, geralmente utiliza saídas ... Talvez você possa converter seu comentário em resposta.
Vor
Pessoalmente, uso FSM como um termo amplo que inclui máquinas DFA, NFA, Mealy e Moore, transdutores (estado finito) etc. simplesmente tudo com um espaço de estados finito e sem memória auxiliar.
Dan
1
@Raphael In Na teoria formal (ou teoria da computação), preferimos usar a palavra "Autômatos" - para enfatizar que nossa máquina é uma máquina 'automática' (que se move como o seu computador) - "automática" no sentido de que uma vez você definiu regras de transição, não precisa aplicar nenhum inteligente explícito para processar / classificar cadeias (você só precisa consultar regras de transição a cada etapa). - enquanto o termo máquina é preferido no contexto do dispositivo (em vez do modelo) - embora ambos sejam sinônimos um do outro.
Grijesh Chauhan

Respostas:

12

Tanto quanto eu entendo, ambos têm "estados" e "ações" que fazem a máquina passar de um estado para outro mediante um sinal de entrada. Assim, as idéias conceituais são as mesmas. Há alguma diferença nos detalhes.

No FSM para projetos de circuitos, o sinal de entrada é geralmente considerado um bit (binário), enquanto no autômato de estado finito pode-se ter um alfabeto "abstrato" geral dos símbolos de entrada. Segundo, um FSM também gera uma saída, associada ao estado atingido, também binário. Na terminologia dos autômatos, essa 'extensão' é chamada de máquina de Moore. Os autômatos, no entanto, têm estados finais (ou aceitos), que sinalizam uma leitura de entrada favorável. Finalmente, o FSM é principalmente determinístico, ou seja, para cada entrada em um determinado estado, existe um próximo estado. Na teoria dos autômatos, também se considera a variante não determinística para onde se pode escolher onde se mover.

Hendrik Jan
fonte
6

Com base na minha experiência e no artigo da Wikipedia, existem vários tipos de máquinas de estados finitos , incluindo

Algumas das noções que circulam diferem principalmente na motivação; alguns surgiram da linguagem e / ou teoria da computabilidade, outros da arquitetura de computadores.

Observe que você também pode alterar vários paradigmas para obter autômatos que são, sem dúvida, ainda autômatos de estado finito, por exemplo

Como você pode ver, os autômatos finitos de baunilha, conforme ensinado no TCS 101, são apenas um sabor de muitos, cada um com sua própria definição (mais ou menos formal).

Rafael
fonte
2

Embora a idéia principal em que ambos confiam seja a mesma. Ambos usam estados finitos e pulam para outro estado como o feed de entrada. No entanto, o FSM sendo uma máquina, como o Full Adder ou o SR flipflop, tem bits como entrada e saída. Sim, o FSA também possui saída de bits, 0 para o estado não terminal e 1 para o estado terminal, mas é um mecanismo abstrato e não é visto. Há diferença nos dígrafos desenhados para representá-los. Além disso, o FSA é um dispositivo lógico e computacional, enquanto o FSM é um dispositivo lógico digital.

Saryan Sandeep
fonte