Na Ciência da computação, teoria dos autômatos é o estudo dos objetos matemáticos chamados máquinas abstratas, ou autômatos, e os problemas computacionais que podem ser resolvidos usando esses objetos. Autômato vem da palavra grega a?t?µata que significa “ação sem influência externa; automático”.
Dentre os autômatos, temos a máquina de estados finitos que consiste em estados (geralmente representados por círculos), e transições (representadas por setas). Quando o autômato recebe um símbolo de entrada, ele faz uma transição (ou salto) para outro estado, de acordo com sua função de transição (que tem como entradas o estado atual e o símbolo recente).
Um autômato finito determinístico — também chamado máquina de estados finita determinística (AFD) — é uma Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação para cada cadeia de entrada.
Definição Formal
Um Autômato Finito Determinístico (AFD) é definido por uma quíntupla M = (S , Q, d, q0, F), onde:
• S : alfabeto de símbolos finitos de entrada
• Q: conjunto finito de estados possíveis para M
• d: função transição ou função programa definida em Q x S ? Q
• q0: estado inicial de M, sendo q0 ?Q
• F: conjunto de estados finais, tal que F? Q
A figura acima representa um autômato finito determinístico através de um Diagrama de Transição de Estados. Nesse autômato há três estados: S0, S1 e S2 . A entrada é constituída por uma sequência finita de caracteres 1s e 0s. Para cada estado da máquina, existe um arco de transição levando a um outro estado para ambos caracteres do alfabeto de entrada.
Isso significa que, em um dado estado, após a leitura de cada símbolo, a máquina determinística transita para um único estado referente à aresta associada ao símbolo. Por exemplo, esteja o autômato atualmente no estado S0 e o símbolo de entrada para aquela instância um '1', então ele salta deterministicamente para o estado S1. Todo AFD possui um estado inicial (denotado graficamente por uma seta de origem anônima) onde a sua computação começa e um conjunto de estados finais (denotados graficamente por um círculo de borda dupla) o qual indica a aceitação da cadeia de entrada.
AFDs são utilizados para modelar softwares que validam entradas de usuário tal como um e-mail em um servidor de correio eletrônico, reconhecem exatamente o conjunto de Linguagens Regulares que são, dentre outras coisas, úteis para a realização de Análise lexica e reconhecimento de padrões.
Finito. O autômato é dito finito porque o conjunto de estados possíveis (Q) é finito.
Determinístico. O autômato é determinístico quando dado o estado atual de M, ao ler
um determinado símbolo na finita de entrada existe apenas um próximo estado
possível.
Autômatos Finitos Não-determinísticos (AFN)
Um AFN, similarmente a um AFD, lê uma cadeia de símbolos de entrada. Para cada símbolo da entrada há uma transição para um novo estado, até que todos os símbolos de entrada sejam lidos, porém existe pelo menos um estado tal que ao ler um mesmo símbolo há mais de uma possibilidade de estado destino. Assim, o próximo estado é um elemento do conjunto das partes dos estados.
No autômato acima, existem duas transições de estado possíveis ao ler o símbolo
a estando o autômato no estado q0.
Aceitação. Uma cadeia é aceita por um AFN se testando-se todas as transições
possíveis à medida que se lê a cadeia, o AFN pára em um estado final após ler toda a
cadeia para algum caminho das transições. Assim, o não-determinismo do próximo
estado pode ser interpretado como um teste de todas as possibilidades.
Rejeição. Uma cadeia é rejeita por um AFN se nenhum caminho de transições leva o autômato a um estado final após ler toda a cadeia.
Definição Formal
O AFN é definido como uma 5-upla, M = (S , Q, d, q0, F), onde:
• S : alfabeto de símbolos finito de entrada
• Q: conjunto finito de estados possíveis para M
• d: função transição ou função programa definida em Q x S ? P(Q)
• q0: estado inicial de M, sendo q0 ?Q
• F: conjunto de estados finais, tal que F? Q
P(Q) representa o conjunto das partes de Q.
O AFN com transições e (também conhecido como AFN-epsilon ou AFN-lambda) é definido por uma 5-upla extremamente semelhante, porém, a função de transição é substituída por uma que permite a cadeia vazia e como uma entrada possível. Desse modo, sua função de transição é dada por:
d: Q x (S U {e}) ? P(Q)
A máquina começa no estado inicial especificado e lê uma cadeia de símbolos do seu alfabeto. O autômato usa a função de transição de estado para determinar o próximo estado usando o estado atual e o símbolo que acabou de ser lido. Entretanto, "o próximo estado de um AFN não depende somente do evento atual, mas também de um número arbitrário de eventos subsequentes de entradas. Até esses eventos subsequentes ocorrerem, não é possível determinar onde a máquina de estados está".
Para todo AFN pode ser encontrada um AFD que aceite a mesma linguagem. Portanto, é possível converter um AFN existente em um AFD, a maquina AFD terá 2n estados, onde n é o número de estados da máquina AFN.
Vantagens e Desvantagens
AFDs são equivalentes em poder de expressão a Autômatos finitos não determinísticos (NFDs). Isso se dá porque, primeiramente qualquer AFD é também um AFN, então AFNs podem expressar o que AFDs expressam. Além disso, dado um AFN, através de uma Construção do conjunto das partes é possível construir um AFD que reconhece a mesma linguagem que um determinado AFN, apesar de o AFD poder precisar de um número muito maior de estados que o AFN . Por outro lado, autômatos de estado finito de potência são estritamente limitados nas linguagens que podem reconhecer. Muitas linguagens simples, incluindo qualquer problema que requeira mais que espaço constante para resolver, não podem ser reconhecidos por um AFD.
Para resolver: Questão 41 POSCOMP 2012
Como relatado acima, na conversão de AFN para AFD, se o AFN possui n estados, ao fazer a conversão para AFD o autômato passa a ter 2^n estados.
Portanto, como o AFN na questão tem 6 estados, o AFD resultante da conversão terá 26 estados que é igual a 64.
Resposta certa: letra C
Referências:
http://pt.wikipedia.org/wiki/M%C3%A1quina_de_estados_finitos_n%C3%A3o_determin%C3%ADstica
http://www.dainf.ct.utfpr.edu.br/~fabro/LFA/TeoriaComputacaoNovo.pdf
http://www.dei.isep.ipp.pt/~goreti/ficha4.pdf
http://www.li.facens.br/~tiemi/Tc1/afn.pdf
Grupo PET Computação UFCG, 2013. All rights reserved.
