Revisão Autômatos
Teoria da Computação
2008-2
Sandra de Amo
Exemplo
0
q1
q0
1
0
1
1
1
0
q3
q2
0
Definição Formal
M = (Q, S, δ, q0, F)
ESTADOS
SIMBOLOS
DE INPUT
TRANSICAO ESTADO
DE ESTADOS INICIAL
ESTADOS
FINAIS
Exemplo
M = (Q, S, δ, q0, F)
Q = {q0,q1,q2,q3}
0
q1
q0
1
S = {0,1}
0
1
1
1
0
1
q0 q1 q3
q1 q0 q2
0
q3
q2
0
q2 q3 q0
q3 q2 q0
F = {q0}
String aceito por um autômato
0
q1
q0
1
0
1
1
1
CASA VAZIA
0
q3
q2
0
0
1
0
0
0 1
q0
q1
q2
q3
q2 q3
q0
String aceito por um autômato
0
q1
q0
1
0
1
1
1
CASA VAZIA
0
q3
q2
0
0
1
0
0
0 0
q0
q1
q2
q3
q2 q3
q2
Linguagem Aceita por um
Autômato
• L = conjunto de todas as palavras
aceitas pelo autômato
L(A) = linguagem aceita pelo autômato A
L(A) = {w | w é aceita por A}
Exemplo
0
q1
q0
1
0
1
1
1
0
q3
q2
0
L(A) = conjunto de todos os strings com numero par
de zeros e numero par de 1’s
Exemplo
0
q1
q0
1
0
1
1
1
0
q3
q2
0
L(A) = conjunto de todos os strings com numero impar
de zeros e numero impar de 1’s
Exemplo
0
q1
q0
1
0
1
1
1
0
q3
q2
0
L(A) = conjunto de todos os strings com numero par
de zeros e numero impar de 1’s
Exemplo
0
q1
q0
1
0
1
1
1
0
q3
q2
0
L(A) = conjunto de todos os strings com numero impar
de zeros e numero par de 1’s