Automato Finito- MaildesNS-LarissaOP

Prévia do material em texto

1 de 3
Autômatos Finitos
Larissa de O. Pinheiro, Maildes N. Silva
Faculdade Ruy Barbosa
Salvador/BA, Brasil
Resumo – este trabalho apresenta o conceito de autômatos finitos, 
definindo e comparando autômatos finitos determinísticos com 
autômatos finitos não-determinísticos. Tendo como objeto de adquirir 
conhecimentos sobre um dos assuntos considerados mais importante 
para o estudo da disciplina Teoria da Computação. 
I. INTRODUÇÃO
Os autômatos finitos são “máquinas” de transição de 
estados que podem ter quantidade limitada de memória. Eles 
podem ser utilizados no processamento de texto, 
compiladores e projeto de hardware. [1, 2]
Um exemplo de um autômato finito é uma porta 
automática. Elas possuem um controlador que tem dois 
estados, um denominado aberto e o outro chamado fechado. 
Neste exemplo, também deve ser levado em consideração as 
quatro condições de entrada possíveis, são elas: atrás 
(significando que uma pessoa está pisando atrás da porta); 
frente (significando que uma pessoa está pisando na frente da 
porta); ambos (significando que duas ou mais pessoa estão 
pisando em tanto na frente quanto atrás da porta); nenhum 
(significando que não há pessoas na direção da porta). 
Esses estados serão alterados dependendo da entrada que o 
controlador recebe, por exemplo, se receber a entrada 
nenhum ou atrás ele irá para o estado fechado, porém 
recebendo a entrada frente, o estado será aberto. Estando 
nesse estado aberto, se a próxima entrada recebida for frente, 
atrás ou ambos ela permanecerá aberta, até a entrada nenhum 
chegar.
Esse controlador precisa do estado que indique o início 
dessa transição entre estados. Definindo o estado fechado 
como o inicial e recebendo os seguintes sinais de entrada: 
frente, atrás, nenhum, frente, ambos, nenhum, atrás e 
nenhum. Então ele passaria pelos estados: fechado (inicial), 
aberto, aberto, fechado, aberto, aberto, fechado, fechado, 
fechado.
Os autômatos finitos podem ser definidos como 
determinísticos (AFD) ou não-determinísticos (AFND). No 
autômato finito determinístico, ao ler a condição de entrada o 
estado atual reconhece apenas um próximo estado possível. 
Já o não-determinístico, tem como característica de para um 
determinado estado atual pode haver mais de uma escolha 
para o próximo estado, a partir do momento que o estado 
atual ler novamente a mesma condição de entrada. [3]
II. AUTÔMATOS FINITOS
Nesta seção, haverá a abordagem sobre os tipos de 
autômatos: o autômato finito determinístico (AFD) e o 
autômato finito não determinístico (AFND).
A. Autômatos Finitos Determinístico
O autômato é denominado finito quando possui um 
conjunto finito de possíveis estados, e considerado 
determinístico quando o estado atual, ao ler um símbolo de 
entrada, a transição será realizada apenas para um próximo 
estado possível. [3]
Pode-se compreender que o autômato finito determinístico 
(AFD) possui uma lista de cinco objetos, são eles: alfabeto 
de entrada, conjunto de estados, regras para movimentação, 
estado inicial e estados de aceitação(ou estados finais).
Em linguagem matemática uma lista de cinco elementos é 
denominada de 5-upla. [1] Para um AFD M sobre um 
alfabeto ∑, há uma 5-upla M = (Q, ∑, δ, s, F) onde:
• Q é um conjunto finito não vazio de estados; 
• ∑ é o alfabeto de entrada;
• s K é o estado inicial; 
• F K é o conjunto de estados finais;
• δ : K × ∑ → K é a função de transição, que associa 
a um estado e a um símbolo lido o novo estado do 
autômato [2]
2 de 3
Fig. 1 – Autômato Finito Determinístico
Na figura acima é um exemplo de um AFD. Ela mostra o 
conjunto de estados finitos (Q): s0, s1, s2 com o alfabeto de 
entrada (∑) 0 e 1. A seta start indica s0 como estado inicial 
(s). As transições são representadas por setas entre os estados 
ou setas que apontam para o próprio estado (loop). Neste 
exemplo, a função de transição (δ) é representada por:
• δ , 1: indica a transição do estado s0 para o s1, s1 
para s0 e do loop do s2.
• δ , 0: representa a transição dos estados s1 para s2, 
s2 para s1 e do loop de s0.
E o estado final (F) é o s0 e é representado por círculo 
duplo.
Ao fornecer uma sentença a um autômato, ele é capaz de 
responder se a sentença pertence ou não à linguagem que ele 
representa. Diz-se que se uma sentença só pertence à 
linguagem que ela representa se, após seu processamento, o 
autômato para em seu estado final. Porém se ocorrer uma 
situação indefinida durante o processamento dessa sentença o 
autômato para e a sentença não é aceita. [1]
B. Autômatos Finitos Não Determinístico
O autômato finito não-determinístico (AFND) é similar a 
um o AFD, porém ele difere na função de transição. Como 
visto na Fig. 2 ele permite que o estado atual, após ler um 
símbolo de entrada, possa fazer uma transição mais de uma 
vez além disso é a existência de uma seta para o rótulo Ɛ, 
onde as transações são feitas a partir da palavra vazia, o que 
significa que o autômato pode alterar seu estado sem ler 
nenhum símbolo. [3]
Fig. 2 – Autômato Finito Não Determinístico
Um AFND M sobre um alfabeto ∑ é uma 5-upla M = (Q, ∑, 
δ, s, F) onde:
• Q é um conjunto finito de estados; 
• ∑ é o alfabeto de entrada;
• s Q é o estado inicial; 
• F Q é o conjunto de estados finais;
• δ : Q × ∑Ɛ → P(Q) é a função de transição para o 
conjunto de partes Q. [2]
O que acontece com o AFND é quando um estado possui 
múltiplas maneiras de prosseguir a máquina divide em 
diversas cópias de si mesma e segue todas as possibilidades 
em paralelo. Caso existam escolhas subsequentes, a máquina 
deverá fazer a divisão novamente. A cópia e suas 
ramificações morrem quando um símbolo de entrada não 
possui uma seta saída do estado ocupado por uma cópia da 
máquina. Mas se isso não ocorrer e qualquer uma dessas 
cópias estiverem no estado de aceitação no final da entrada, o 
AFN aceita a cadeia de entrada. [2]
Existem duas formas de podermos associar um AFND 
como múltiplos e independentes processos ou threads que 
podem estar sendo executadas concorrentemente. Ou 
podemos pensar em uma árvore de possibilidades. A raiz da 
árvore corresponde ao início da computação, as ramificações 
representariam as múltiplas escolhas, e a máquina aceita pelo 
menos um dos ramos que termina em um estado de 
aceitação. [2]
Além das características citadas anteriormente o AFND 
pode construir um AFD e isso é chamado de equivalência. 
Construir AFND é às vezes mais fácil que construir 
diretamente AFD, pois um AFND pode ser muito menor que 
3 de 3
sua contrapartida determinística, ou seu funcionalmente ser 
mais fácil de entender. [2]
III. CONCLUSÃO
Visto que é um assunto considerado fácil de aprendizagem 
e é uma das áreas mais importante da teoria da computação, 
o autômato finito é uma máquina de transição de estados com 
intuito de validar se uma palavra pertence ou não a 
linguagem em questão.
Também pode-se destacar os dois tipos de autômatos 
finitos: os determinísticos e os não-determinísticos. Os 
determinísticos possuem como propriedade exclusiva de 
fazer a transição para um estado determinado enquanto os 
não-determinísticos podem haver várias possibilidades de 
estados possíveis.
REFERÊNCIAS
 [1] A. M. de A. Prince e S. S. Toscani. “Implementação de 
Linguagens de Programação: Compiladores”. Editora Sagra, 
2001.
[2] M. Sipser. “Introdução à Teoria da Computação”. Editora 
Thomson, 2007.
[3] R. Silva. “Teoria da Computação”. 2007.