1
Os autômatos são uma representação formal muito útil que permite
modelar o comportamento de diferentes dispositivos, máquinas,
programas, etc.
• Máquinas de venda automática de refrigerantes
• O comportamento de um programa (software)
• O comportamento dos semáforos
A ideia geral é modelar um sistema que:
• Recebe um conjunto de elementos de entrada (estímulos)
• Realiza algum processo (computação)
• Ocorre uma saída
2
Introdução aos autômatos finitos
Os autômatos finitos são um modelo útil para muitos tipos de hardware e
software. Por enquanto, listaremos apenas alguns dos tipos mais
importantes:
1. Software para projetar e testar o comportamento de circuitos digitais.
2. 2. O “analisador léxico” de um compilador típico, ou seja, o
componente do compilador que separa o texto entrada em unidades
lógicas, como identificadores, palavras-chave e sinais de pontuação.
3. 3. Software para digitalizar longos corpos de texto, como coleções de
páginas da web, ou para determinar o número de ocorrências de
palavras, frases ou outros padrões.
4. 4. Software para verificação de sistemas de todos os tipos que
possuem um número finito de estados diferentes, como como
protocolos de comunicação ou protocolos para a troca segura de
informações
Um autômato finito tem um conjunto de estados, alguns dos quais são denominados
estados finais. À medida que caracteres da string de entrada são lidos, o controle da
máquina passa de um estado a outro, segundo um conjunto de regras de
transição especificadas para o autômato. Se após o último carácter o autômato encontra-
se em um dos estados finais, a string foi reconhecida (ou seja, pertence à linguagem).
Caso contrário, a string não pertence à linguagem aceita pelo autômato.
4
Um autômato é um modelo matemático para uma máquina de
estados finitos, no qual, dada uma entrada de símbolos, ela “salta”
através de uma série de estados de acordo com uma função de
transição (que pode ser expressa como uma tabela). Esta função
de transição indica para qual estado mudar, dado o estado atual e
o símbolo lido.
Ejemplo
Considere um sistema composto por uma lâmpada e um interruptor. A lâmpada pode
estar ligada ou desligada. O sistema só pode receber um estímulo externo: pressionar
o botão. O funcionamento é normal: se o interruptor for pressionado e a lâmpada
estiver off, ela passa para o estado on e se estiver em on, pasa o estado off.
Queremos que a lâmpada esteja inicialmente em off.
• Considere que 0: ligado, 1: desligado e a única entrada possível (pressione o
interruptor) é “p”
Como seria o autômato que representa este sistema?
Modelo de autômato finito para o
reconhecimento da palavra then
6
Q É um conjunto finito de estados
É um alfabeto
É o estado inicia q0 є Q
É o conjunto de estados finais F
É uma função de transição
7
8
9
10
11
ababababa
abb
abbbaa
aabbbabb
12
*
13
15
16
17
18
Ababa
aaa
aba
aba
bbb
a,b a,b a,b
q0 q1 q2 q3
a,b
a,b a,b a,b
q0 q1 q2 q3 q4
19
a,b
a a
q0 q1 q2
q4
q0
a,b a,b
a,b a,b q2
q1
20
1 1
0 0
q0 q1 q3
1 1
q2
21
22
a
q0
b
a
b
q2 b q1
a
b q3
a
23
24
25
26
27
28
29
ER=(1+0)(0*1+)+
ER= (a+b) c*(a+b)
30
31