# Autômato finito não determinístico com transições ε

Na teoria dos autômatos, um autômato finito não-determinístico com transições ε (AFN-ε) (também conhecido como AFN-λ), é uma extensão (variação) de um autômato finito não-determinístico (AFND), que permite a transição para um novo estado sem consumir qualquer caractere da entrada. As transições que não consomem nenhum caractere de entrada são chamadas de transições ε ou transições λ. No diagrama de estados, essas transições são normalmente representadas pelas letras gregas ε ou λ.
Transições ε fornecem uma maneira conveniente de modelagem de sistemas cujos estados atuais não são conhecidos com precisão. Transições ε não acrescentam qualquer capacidade extra de reconhecimento de linguagens formais. Os AFN-ε e os AFNs reconhecem a mesma classe de linguagens formais, que são as linguagens regulares. Os AFN-ε se mostram úteis porque existem certas propriedades que podem ser mais facilmente comprovadas sobre eles, em comparação com os AFNs tradicionais. Uma vez que um AFN-ε sempre pode ser transformado em um AFN, as propriedades testadas nos AFN-ε são igualmente válidas para AFNs.

## Introdução informal

Por exemplo, vamos supor que um AFN-ε contém dois estados, 1 e 2, e há uma transição para o estado 2 sem consumir nenhum caractere da entrada (transição ε). Se ele está no estado 1, com o próximo símbolo de entrada sendo a, então há uma ambiguidade: O sistema está no estado 1 ou no estado 2 antes de consumir a letra a? Por causa desta ambiguidade, é mais conveniente falar de um conjunto de estados possíveis que o sistema pode estar. Assim, antes de consumir a letra a, o AFN-ε pode estar em qualquer um dos estados do conjunto {1,2}. De forma equivalente, pode-se imaginar que o AFN está nos estados 1 e 2 'ao mesmo tempo'.

## Definição formal

Um AFN-ε é representado formalmente por uma 5-upla, ( Q, Σ, Δ, q $_0$, F), que consiste em:
* Um conjunto finito dos estados Q
* Um conjunto finito que representa um alfabeto Σ
* Uma função de transição Δ: Q × (Σ ∪ {ε}) → P ( Q)
* Um estado inicial q$_0$ ∈ Q
* Um conjunto de estados de aceitação F, F ⊆ Q.
Aqui, P(Q) denota o conjunto de partes de Q e ε denota vazio.
Para um q ∈ Q, temos que E(q) denota o conjunto de estados que são acessíveis a partir do estado q, seguindo ε-transições na relação de transição Δ, ou seja, p ∈ E(q) se e somente se existe uma seqüência de estados q$_1$,..., q$_k$ tal que q$_1$ = q, (q$_i$, ε, q$_{i+1}$) ∈ Δ para cada 1 ≤ i <k, e q $_k$ = p. E(q) é conhecido como ε-fechamento de q. O ε-fechamento de um subconjunto dos estados também é definido da seguinte maneira: Para P ⊆ Q, E(P) = ∪$_{q∈P}$E(q).
Seja w = a$_1$a$_2$ ... a$_n$ uma palavra sobre o alfabeto Σ. O autômato M aceita a palavra w se uma seqüência de estados, r$_0$,r$_1$, ..., r$_n$, existe em Q com as seguintes condições:
* r$_0$ ∈ E(q$_0$),
* r' ∈ Δ(r$_i$, a$_{i+1}$ e r$_{i+1}$ ∈ E(r') para cada i = 0, ..., n-1, e
* r$_n$ ∈ F.
Em palavras, a primeira condição diz que a máquina começa no estado que é acessível a partir do estado inicial q$_0$ via transições ε. A segunda condição diz que, depois de ler a$_i$, a máquina tem uma transição a partir de Δ de r$_i$ a r', e, em seguida, usa um número qualquer de transições ε de acordo com Δ para se deslocar de r' a r$_{i+1}$. A última condição diz que a máquina aceita w se a última configuração de w (ao entrar o último caractere) faz com que a máquina chegue num dos estados de aceitação. Caso contrário, diz-se que o autômato rejeita a cadeia. Se M é o conjunto das cadeias aceitas pelo autômato, a linguagem formal que esse autômato reconhece é denotada por L(H).
É provado que o AFN normal e o AFN-ε são equivalentes, uma vez que, dado qualquer um, pode-se construir o outro, que reconhece a mesma linguagem.
Para uma introdução mais abrangente da definição formal ver teoria dos autômatos.

## Exemplo

Seja M um AFN-ε, com um alfabeto binário, que determina se a entrada contém um número par de 0s ou um número par de 1s. Note-se que 0 ocorrências é um número par de ocorrências.
Em notação formal, seja M = ({s$_0$, s$_1$, s$_2$, s$_3$, s$_4$}, {0, 1}, Δ, s$_0$, {s$_1$, s$_3$}) onde a função de transição Δ é definida pela tabela de transição de estados abaixo:
| | 0 | 1 | ε |
| S$_0$ | | | {S$_1$, S$_3$} |
| S$_1$ | {S$_2$} | {S$_1$} | |
| S$_2$ | {S$_1$} | {S$_2$} | |
| S$_3$ | {S$_3$} | {S$_4$} | |
| S$_4$ | {S$_4$} | {S$_3$} | |
M pode ser visto como a união de dois AFDs: um com os estados {S$_1$, S$_2$} e o outro com os estados {S$_3$, S$_4$}. A linguagem de M pode ser descrita pela linguagem regular dada pela expressão regular (1*(01*01*)*) ∪ (0*(10*10*)*). Nós definimos M usando transições ε, mas M pode ser definido sem o uso delas.

## Equivalência de AFN e AFD

Seja A = (Q, Σ,Δ, q$_0$, F) um AFN-ε. O AFN A' = (Q, Σ, Δ', E(q$_0$), F) é equivalente a A, onde para cada a ∈ Σ e q ∈ Q, Δ'(q,a) = E(Δ(q,a)). Posteriormente, o AFN pode ser traduzido em AFD usando a construção do conjunto das partes.

## Propriedades de fechamento

Se um AFN-ε reconhecer as linguagens que são obtidas através da aplicação de uma operação no próprio AFN-ε, então o AFN-ε seria fechado sob esta operação. Os AFN-ε estão fechados sob as seguintes operações:
* União
* Interseção
* concatenação
* Negação
* Fecho de Kleene (estrela)