Wikipédia

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 editar

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 editar

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 q0 ∈ 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 q1,..., qk tal que q1 = q, (qi, ε, qi+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 = a1a2 ... an uma palavra sobre o alfabeto Σ. O autômato M aceita a palavra w se uma seqüência de estados, r0,r1, ..., rn, existe em Q com as seguintes condições:

  1. r0 ∈ E(q0),
  2. r' ∈ Δ(ri, ai+1 e ri+1 ∈ E(r') para cada i = 0, ..., n-1, e
  3. rn ∈ F.

Em palavras, a primeira condição diz que a máquina começa no estado que é acessível a partir do estado inicial q0 via transições ε. A segunda condição diz que, depois de ler ai, a máquina tem uma transição a partir de Δ de ri a r', e, em seguida, usa um número qualquer de transições ε de acordo com Δ para se deslocar de r' a ri+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 editar

 
O diagrama de estados para M

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 = ({s0, s1, s2, s3, s4}, {0, 1}, Δ, s0, {s1, s3}) onde a função de transição Δ é definida pela tabela de transição de estados abaixo:

0
1
ε
S0
{}
{}
{S1, S3}
S1
{S2}
{S1}
{}
S2
{S1}
{S2}
{}
S3
{S3}
{S4}
{}
S4
{S4}
{S3}
{}

M pode ser visto como a união de dois AFDs: um com os estados {S1, S2} e o outro com os estados {S3, S4}. 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 editar

Seja A = (Q, Σ,Δ, q0, F) um AFN-ε. O AFN A' = (Q, Σ, Δ', E(q0), 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 editar

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:

Obtida de "https://pt.wikipedia.org/w/index.php?title=Autômato_finito_não_determinístico_com_transições_ε&oldid=45913855"