Autômato Finito Determinístico

23/02/2010 12:20

Dentro da Teoria da Computação, uma máquina de estados finitos determinística ou autômato finito determinístico é uma máquina de estados finitos onde, para cada par de estados e símbolo de entrada, existe um próximo estado determinístico.

 

Um autômato finito determinístico é uma quíntupla, (S, Σ, T, s, A), que consiste de

  • um conjunto finito de estados (S)
  • um conjunto finito de símbolos chamado de alfabeto (Σ)
  • uma função de transição (T : S × Σ → S)
  • um estado inicial (s ∈ S)
  • um conjunto de estados finais(A ⊆ S)

Considere que M seja um AFD (ou DFA) tal que M = (S, Σ, T, s, A), e X = x0x1 ... xn seja uma string contida no alfabeto Σ. M aceita a string X se numa seqüência de estados, r0,r1, ..., rn, existe em S com as seguintes condições:

  1. r0 = s
  2. ri+1 = T(ri, xi), para i = 0, ..., n-1
  3. rn ∈ A.

Conforme mostrado na primeira condição, a máquina inicia no estado inicial s. A segunda condição diz que, dado cada caracter de uma string X, a máquina passará de estado a estado de acordo com a definição de uma função de transição T. A última condição diz que a máquina aceita uma string se a última entrada de X faz com que a máquina passe para um dos estados de aceitação. Caso contrário, dizemos que a máquina rejeitou a string. O conjunto de strings que ela aceita forma uma linguagem, a qual é a linguagem que um AFD reconhece.

Exemplo

O exemplo a seguir é um autômato finito determinístico M, que possui um alfabeto binário, o qual determina se a entrada contém um número par de 0's.

M = (S, Σ, T, s, A) onde

  • Σ = {0, 1},
  • S = {S1, S2},
  • s = S1,
  • A = {S1}, and
  • T é definido pela seguinte tabela de transição de estados:
 
0
1
S1 S2 S1
S2 S1 S2

Considerando o autômato de maneira simplificada, o estado S1 representa que havia realmente um número par de 0's, enquanto S2 significa um número ímpar. Um '1' na entrada não muda o estado do autômato. Quando a entrada é consumida, o estado irá indicar se a entrada continha ou não um número par de 0's.

A linguagem de M pode ser descrita pela linguagem regular dada por essa expressão regular:

1^*(01^*01^*)^* \,\!

 

Voltar