Automatos

Autômatos Finitos
Luiz Alberto Freire Gonçalves Júnior

UESB – Universidade Estadual do Sudoeste da Bahia
DCET – Departamento de Ciências Exatas e Tecnológicas
Cx. Postal 95 – CEP 45.083-900 Vitória da Conquista (BA) [e-mail] Resumo: Um autômato finito é um sistema de estados finitos (portanto possui um número finito e predefinido de estados) e seu “controle” se desloca de estado para estado em resposta a “entradas” externas. Ele constitui um modelo computacional do tipo sequencial muito comum em vários estudos teórico-formais da Computação e Informática e trata-se de um formalismo operacional ou reconhecedor, o qual pode ser: determinístico, não determinístico ou com movimentos vazios. São também uma forma matemática de descrever tipos particulares de algoritmos. Um Autômato Finito é denominado Determinístico quando dependendo do estado corrente e do símbolo lido, o sistema pode assumir um único estado bem determinado.
Um Autômato Finito Não-Determinístico diferente do Determinístico, tem o poder de estar em vários estados ao mesmo tempo, ou seja, o Não-Determinismo permite um conjunto de diferentes movimentos possíveis em cada situação.
Movimentos vazios constituem uma generalização dos AFN e são transições que ocorrem sem que haja a leitura de símbolo algum

Palavras Chaves: Autômato, finito, deterministico, não-determinístico, vazio.

1 Introdução
Neste artigo estudaremos uma máquina (um procedimento aceitador, ou reconhecedor), chamada autômato finito.
Autômato vem da palavra grega αὐτόματα que significa “ação sem influência externa; automático”. Um autômato finito é um formalismo operacional ou reconhecedor, sendo, basicamente, um sistema de estados finitos.
Um sistema de estados finitos, nada mais é, que um modelo matemático de um sistema que contém entradas e saídas discretas. Eles podem assumir um número finito e predefinido de estados, isto significa que todos os estados possíveis do sistema podem ser