Máquina de estados finitos determinística

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Mergefrom 2.svg
O artigo ou secção Autômatos finitos determinísticos deverá ser fundido aqui. (desde janeiro de 2012)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Cheque ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).
Searchtool.svg
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor verifique e melhore a consistência e o rigor deste artigo. Pode encontrar ajuda no WikiProjeto Ciência da computação.

Se existir um WikiProjeto mais adequado, por favor corrija esta predefinição. Este artigo está para revisão desde julho de 2009.

Na teoria dos autômatos, uma máquina de estados finita determinística ou autômato finito determinístico (AFD) é uma máquina de estados finitos onde, dado uma configuração e um símbolo da cadeia de entrada existe somente um estado para o qual a máquina pode transitar. Em outras palavras, em um AFD, o estado sucessor é definido unicamente pelo seu estado atual e pela condição de transição.

Definição formal[editar | editar código-fonte]

Um autômato finito determinístico é formalmente definido por uma quintúpla:

M=(Q,\  \Sigma,\  \delta,\ q_{0},\ F)

Onde:

  • \, Q é um conjunto finito de estados.
  • \,\Sigma é um conjunto finito de símbolos, denominado alfabeto de entrada.
  • \,\delta:Q \times \Sigma \to Q é a função de transição.
  • \,q_{0}\in\, Q é o estado inicial.
  • F\subseteq Q é o conjunto de estados finais (ou de aceitação).

Nesta formulação do AFD, a condição de que as todos os estados tenham apenas uma transição para cada símbolo do alfabeto é garantida pela relação de transição que está definida como uma função de Q e \Sigma. Como uma função mapeia, para cada elemento do domínio, apenas um elemento do contra-domínio, a função \delta mapeia, para cada par estado-símbolo, apenas um estado destino.

A princípio, a função \delta é injetora, no entanto, em algumas definições é possível observar que transições indesejadas são removidas a fim de tornar a descrição do AFD mais simples. Neste caso, caso não haja uma transição definida para um determinado símbolo do alfabeto, fica subentendido que o autômato termina sua execução, rejeitando a cadeia de entrada.

Esta generalização da definição não modifica o funcionamento base do autômato nem sua característica determinística, uma vez que é possível tornar a função injetora incluindo um estado adicional q_{erro} e substituir a função \delta_{ant} pela função \delta_{novo}, respeitando as especificações abaixo:

q_{erro} \in Q
q_{erro} \notin F
\mbox{se } (q_i,\sigma,q_j) \notin \delta_{ant} \Rightarrow (q_i,\sigma,q_{erro}) \in \delta_{novo} \qquad \forall q_i, q_j \in Q-\left\{q_{erro} \right\} \mbox{ e } \forall \sigma \in \Sigma
(q_{erro},\sigma,q_{erro}) \in \delta_{novo} \qquad \forall \sigma \in \Sigma

Com isso, todas transições não existentes são incluídas, fazendo com que o autômato transite para um estado não terminal que "aprisiona" o mesmo até que a cadeia seja completamente consumida.

Softwares[editar | editar código-fonte]

  • Simulador de Autômatos - Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
  • SCTMF - Software para Criação e Teste de Modelos Formais.
  • JFlap - Software americano para testes com interface gráfica.

Ver também[editar | editar código-fonte]

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito


Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.