Autômatos finitos determinísticos

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.

Definição formal

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 = x₀x₁ ... x_n seja uma string contida no alfabeto Σ. M aceita a string X se numa seqüência de estados, r₀,r₁, ..., r_n, existe em S com as seguintes condições:

1. r₀ = s
2. r_i+1 = T(r_i, x_i), para i = 0, ..., n-1
3. r_n ∈ 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 = {S₁, S₂},
• s = S₁,
• A = {S₁}, e
• 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 S₁ representa que havia realmente um número par de 0's, enquanto S₂ 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^*)^* \,\!$

Softwares

• Auger - Software brasileiro com interface gráfica para construção e simulação de autômatos finitos e conversão para outros modelos formais.
• Simulador de Autômatos - Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
• SCTMF - Software para Criação e Teste de Modelos Formais.
• JFlap - Software americano para testes com interface gráfica.