CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Autômatos Finitos Determinísticos

Autômato Finito (AF) é um tipo de modelo computacional que modela uma forma de executar tarefas. Outros exemplos de modelos computacionais seria a Maquina de Turing e λ-cálculo.

Os Autômatos Finitos também são conhecidas como máquina de estados finita, pois necessitam "lembrar" apenas uma quantidade finita de estados e a tabela de regras para transição entre esses estados. Eles são adequados à modelar dispositivos com baixíssima quantidade de memória, como sistemas embarcados.

Um exemplo de aplicação de um AF seria o seguinte sistema de uma porta basculante automática para entrada de pessoas:

A porta possui dois estados: aberta e fechada, e inicialmente está fechada;
A porta detecta quando há pessoas na sua parte frontal (frente) e posterior (atrás);
Se não houver ninguém ao seu redor, ela deve permanecer fechada;
Se houver alguém na sua parte posterior, a porta não deve mudar de estado;
Caso contrário, ela deve permanecer aberta.

Podemos ver um AF como uma máquina que processa cadeias sobre um alfabeto Σ. Nesse caso, ele aceita ou rejeita cada cadeia que processa, possui um estado inicial e um ou mais estados de aceitação e todo estado possui uma transição para cada símbolo em Σ.

Processamento de cadeias:

O autômato recebe uma cadeia em Σ e a lê da esquerda para a direita;
Dependendo do estado que está e do símbolo que está lendo, ele faz a transição (ou não) para outro estado;
Ao finalizar a leitura da cadeia, se ele se encontra em um estado de aceitação, dizemos que a cadeia é aceita pelo autômato. Se não, dizemos que a cadeia é rejeitada pelo autômato;
A linguagem de uma AF M, denotada por L(M), é o conjunto de todas as cadeias aceitas por M;
Uma linguagem é dita regular se existe um AF que a aceita.

Definição Formal

Um Autômato Finito é uma 5-upla (Q, Σ, δ, q0, F), onde:

Q é um conjunto finito de estados do AF;
Σ é o alfabeto;
δ: Q x Σ → Q é a função de transição;
q0 ∈ Q é o estado inicial; e
F ⊆ Q é o conjunto de estados de aceitação (ou finais).