Autômato finito determinístico

Um Autômato Finito Determinístico A é uma 5-tuple (ou quíntupla), (Q, Σ, δ, q0, F) consistindo de: Seja w = a1a2 ... an uma cadeia de símbolos sobre o alfabeto Σ, O autômato M aceita a cadeia w se somente se existe uma sequência de estados, r0,r1, ..., rn, em Q com as seguintes condições: Em outras palavras, a primeira condição afirma que a máquina se inicia no estado inicial q0. A segunda condição diz que, dado cada símbolo da entrada w, a máquina transita de estado em estado de acordo com a função de transição δ. A terceira e última condição diz que a máquina aceita w se somente se o último símbolo da entrada leva o autômato a parar em um estado f tal que f ∈ F. Caso contrário, diz-se que a máquina rejeita a entrada. O conjunto de cadeias que M aceita é chamado Linguagem reconhecida por M e é simbolicamente representado por L(M). Um autômato finito determinístico que não possui estado inicial ou estados de aceitação é conhecido como um Sistema de Transições ou Semiautômato.

O exemplo a seguir representa um AFD M, com um alfabeto binário, que requer que sua entrada contenha um número par de 0s. O estado S1 indica que houve um número par de ocorrências do símbolo 0 até então na entrada, enquanto que S2 significa que esse valor foi impar. Um 1 na entrada não altera o estado atual do autômato. Quando a entrada é completamente lida, o estado atual vai indicar se a cadeia de entrada possui um número par de 0s ou não. Caso a cadeia possua de fato uma quantidade par, M vai encerrar-se no estado S1, um estado de aceitação, tal que a entrada vai ser aceita. Caso contrário, se o autômato encontrar-se no estado S2, a máquina rejeita a cadeia. A linguagem reconhecida por M é a Linguagem regular dada pela Expressão regular 1*( 0 (1*) 0 (1*) )*, tal que "*" é uma Kleene star, e.g., 1* indica que há "zero ou mais" ocorrências de 1s nesse trecho da expressão.

AFDs são fechadas sob as seguintes operações (o que implica que se uma linguagem for obtida através da aplicação de uma dessas funções sobre uma ou mais linguagens, existe uma AFD que reconhece a linguagem resultante): Sendo AFDs equivalentes a Autômatos finitos não determinísticos (AFN), essas operações de fechamento podem ser provadas através do uso das propriedades dos AFNs.

Uma AFD que representa uma dada linguagem regular pode ser usada tanto em um modo de aceitação para validar que uma cadeia de entrada pertence a uma linguagem L como em Modo de geração para gerar uma lista de todas as linguagens que pertencem a L. No modo de aceitação, o autômato processa uma cadeia de entrada do caractere mais à esquerda ao mais à direita, lendo um símbolo por vez. A computação da entrada se inicia no estado inicial e continua ao ler-se o primeiro símbolo da cadeia de entrada, seguindo o estado de transição que corresponde àquele símbolo (de acordo com a função de transição do autômato). O sistema segue as transições até que todos os símbolos da entrada tenham sido lidos, o que indica o final da computação. Se após o processamento da entrada a máquina encontrar-se em um estado de aceitação, a cadeia é aceita e diz-se que ela pertence a L. Ao contrário, a cadeia não pertence a L e diz-se que ela foi rejeitada pelo autômato.

Expressões regulares e autômatos finitos determinísticos (AFD) são equivalentes em poder de descrição. Ambas representações descrevem exatamente a classe de linguagens regulares. É possível, a partir de um autômato finito determinístico, obter a expressão regular que o autômato descreve. De forma a provar a equivalência entre AFDs e expressões regulares, é preciso demonstrar que é possível converter um AFD em uma expressão regular e que também é possível converter uma expressão regular em um AFD. O procedimento que converte autômatos finitos determinísticos utiliza outro tipo de autômato, denominado autômato finito não determinístico generalizado. O procedimento é constituído em duas etapas, a conversão de autômato finito determinístico para um autômato finito não determinístico generalizado (AFNG), e enfim, de um AFNG para uma expressão regular. Um AFNG é extremamente semelhante a um autômato finito não determinístico (AFN), no entanto, a diferença consiste principalmente em que o AFNG é capaz de ler blocos de símbolos de entrada, ao invés de apenas um único símbolo de entrada. A função de transição de um AFNG caracteriza-se da seguinte forma:

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 (mais precisamente, o número de estados de um AFD construído a partir de um AFN equivale ao conjunto das partes dos estados do AFN que o gerou). 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. O exemplo clássico de uma linguagem simplesmente descrita que nenhum AFD reconhece é a linguagem de colchetes, ou seja, linguagem que consiste em colchetes devidamente emparelhados como a palavra "(()())". Nenhum DFA pode reconhecer a linguagem de colchetes porque não há um limite para a recursividade, ou seja, sempre se pode incorporar outro par de suportes dentro. Seria necessária uma quantidade infinita de estados para reconhecê-la. Outro exemplo mais simples é a linguagem consistindo de cadeias de símbolos da forma anbn— um número finito de a's, seguido por um número igual de b's.