Índice da seção
Autômatos Finitos Determinísticos (AFDs)
Um Autômato Finito Determinístico (AFD) é uma quintupla onde:
- é um conjunto não-vazio e finito de estados internos.
- é um alfabeto de entrada.
- é uma função total de transição.
- é o estado inicial.
- é o conjunto de estados finais ou de aceitação.
O termo "determinístico" se refere ao fato de que, para cada entrada, existe apenas um estado ao qual o autômato pode transitar a partir de seu estado atual (HOPCROFT; MOTWANI; ULLMAN, 2003, p. 48). Isto, os AFD's são autômatos finitos que podem estar em apenas um estado em cada instante de tempo.
A função de transição pode ser interpretada semanticamente como sendo o programa que o autômato executa, assim uma aplicação qualquer de é uma instrução do programa do autômato. Por exemplo, a aplicação significa que, o AFD muda do estado atual para o estado quando o mecanismo de leitura lê o símbolo na memória.
Funcionamento de um AFD
Observe que , em sua definição básica, não processa cadeias completas, mas apenas símbolos individualmente. Para que o AFD seja capaz de manipular palavras inteiras, precisamos estender a função de transição, de modo que ela represente a execução completa do “programa” sobre uma sequência de símbolos.
Seja um AFD , a função estentida de , denotada por , é , tal que:
A partir da definição da função de transição estendida, podemos compreender partir para a compreensão do funcionamento de AFDs. Formalizaremos tais conceitos a seguir.
Seja um AFD e seja , uma computação de em corresponde a aplicação de .
Seja um AFD e seja é dito que é reconhecida por sempre que .
Seja um AFD, a linguagem reconhecida (computada) , denotada por , corresponde ao conjunto:
Isto é, a linguagem de um AFD é o conjunto de todas as palavras reconhecidas por .
Classes Formais
Com a compreensão mais consolidade de autômatos finitos determinísticos, já somos capazes de formalizar a primeira classe de linguagens formais, sendo esta a classe das linguagens regulares.
Seja uma linguagem qualquer, é dita linguagem regular se, e somente se, existe um AFD tal que . A classe de todas as linguagens regulares é denotada por .