Autômato finito determinístico

Um Autômato Finito Determinístico (AFD) é formalmente definido como uma quíntupla (Q, Σ, δ, q0, F), onde cada elemento tem um papel específico no seu funcionamento. Para uma cadeia de entrada w = a1a2 ... an, o AFD a aceita se uma sequência de estados r0, r1, ..., rn em Q satisfaz três condições: inicia no estado q0, transita de estado conforme a função δ para cada símbolo, e termina em um estado f que pertence ao conjunto de estados de aceitação F. Caso contrário, a cadeia é rejeitada. O conjunto de todas as cadeias aceitas por um AFD M é chamado de Linguagem reconhecida por M, simbolizada por L(M). Um AFD sem estado inicial ou de aceitação é conhecido como Sistema de Transições ou Semiautômato.

Considere um AFD M com um alfabeto binário que aceita apenas cadeias com um número par de zeros. O estado S1 indica que um número par de zeros foi lido até o momento, enquanto S2 indica um número ímpar. O símbolo '1' não altera o estado atual. Ao final da leitura da entrada, se o AFD estiver em S1 (um estado de aceitação), a cadeia é aceita; se estiver em S2, é rejeitada. A linguagem reconhecida por M é uma Linguagem Regular, descrita pela Expressão Regular 1*( 0 (1*) 0 (1*) )*, onde '*' representa 'zero ou mais' ocorrências (Kleene star).

Os AFDs possuem propriedades de fechamento importantes, o que significa que se uma linguagem é obtida aplicando certas operações sobre uma ou mais linguagens reconhecidas por AFDs, a linguagem resultante também pode ser reconhecida por um AFD. Essas operações incluem união, concatenação, estrela de Kleene, interseção e complemento. A equivalência entre AFDs e Autômatos Finitos Não Determinísticos (AFNs) permite que essas propriedades de fechamento sejam demonstradas utilizando as características dos AFNs.

Um AFD que representa uma linguagem regular pode operar de duas maneiras: no modo de aceitação ou no modo de geração. No modo de aceitação, o autômato valida se uma cadeia de entrada pertence a uma linguagem L. Ele processa a cadeia símbolo por símbolo, da esquerda para a direita, começando no estado inicial e seguindo as transições. A computação termina quando todos os símbolos são lidos. Se o estado final for um estado de aceitação, a cadeia é aceita e pertence a L; caso contrário, é rejeitada. No modo de geração, o AFD pode ser usado para listar todas as cadeias que pertencem à linguagem L.

Expressões Regulares e Autômatos Finitos Determinísticos (AFDs) possuem o mesmo poder descritivo, ou seja, ambos são capazes de descrever exatamente a classe das linguagens regulares. Para provar essa equivalência, é necessário demonstrar que um AFD pode ser convertido em uma Expressão Regular e vice-versa. O processo de conversão de AFD para Expressão Regular envolve um autômato intermediário, o Autômato Finito Não Determinístico Generalizado (AFNG), que pode ler blocos de símbolos de entrada, diferentemente de um AFD ou AFN que leem apenas um símbolo por vez.

AFDs são equivalentes em poder de expressão aos Autômatos Finitos Não Determinísticos (AFNs). Qualquer AFD é também um AFN, e é possível construir um AFD equivalente a qualquer AFN através da 'Construção do Conjunto das Partes', embora o AFD resultante possa ter um número exponencialmente maior de estados. Contudo, AFDs possuem limitações estritas: eles não podem reconhecer linguagens que exigem mais do que espaço constante para serem resolvidas. Exemplos clássicos incluem a linguagem de colchetes devidamente emparelhados (como '(()())') e a linguagem de cadeias na forma 'anbn' (um número 'n' de 'a's seguido por 'n' 'b's). Essas linguagens demandariam um número infinito de estados para serem reconhecidas, o que é inviável para um autômato finito.