PROFILPELAJAR.COM

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 ₀, 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₀ ∈ 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₁,..., q_k tal que q₁ = 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₁a₂ ... a_n uma palavra sobre o alfabeto Σ. O autômato M aceita a palavra w se uma seqüência de estados, r₀,r₁, ..., r_n, existe em Q com as seguintes condições:

r₀ ∈ E(q₀),
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₀ 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₀, s₁, s₂, s₃, s₄}, {0, 1}, Δ, s₀, {s₁, s₃}) onde a função de transição Δ é definida pela tabela de transição de estados abaixo:

	0	1	ε
S₀	{}	{}	{S₁, S₃}
S₁	{S₂}	{S₁}	{}
S₂	{S₁}	{S₂}	{}
S₃	{S₃}	{S₄}	{}
S₄	{S₄}	{S₃}	{}

M pode ser visto como a união de dois AFDs: um com os estados {S₁, S₂} e o outro com os estados {S₃, S₄}. 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₀, F) um AFN-ε. O AFN A' = (Q, Σ, Δ', E(q₀), 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: